Job lateness in a two-machine flowshop with setup times separated (Q1184446)

The paper deals with the two-machine flowshop problem the objective of which is to find such a sequence of jobs so that the maximum positive difference between the time of job completion and its due date over all jobs of the problem is as small as possible. Each job is supposed to be processed first on machine 1 and then on machine 2. The processing of each job in any machine consists of two parts. The first part, the so called setup, must immediately precede the second, when the job is actually processed in the machine. The first part is assumed to be separable from the second. It means that the setup operation on machine 2 for the given job may be performed parallely to the processing of the job in machine 1. The first part of the paper contains a proof that the objective function \(L(S)\) of the schedule \(S\) is less than or equal to \(L(S')\) of the schedule \(S'\) which is constructed from \(S\) by inversion of one pair of immediately consecutive jobs \((i,j)\) if the following conditions hold: (i) \(d_ i\leq d_ j\) when \(d_ i\), \(d_ j\) are the due dates of the jobs \(i\), \(j\); (ii) \(\min\{t_{i1}+s_{i1}- s_{i2},t_{j2}\}\leq\min\{t_{j1}+s_{j1}-s_{i2},t_{i2}\}\). In the second part of the paper the theorem is used to construct a branch-and-bound algorithm and to develop two heuristics. Computational results including a comparison of the optimal solution with the heuristic solutions are presented. Unfortunately the description of the algorithm is rather vague and it seems to contain some mistakes. E.g. \(\max\{q_ 1+t_{r1}+s_{r1}, t_{*1}+s_{*1}+q_ 2\}\) need not be the earliest start time for job \(r\) in machine 2 because the second term of the expression includes all setup times of \(S'\) in spite of the fact that the first job setup time can run parallely to \(t_{*1}+s_{*1}\). Further, the relation (ii) does not meet the transitivity condition and thus the attempt of ordering the jobs according to this relation in Johnson's heuristic may be questionable.