THE 3-MACHINE FLOWSHOP PROBLEM WITH ARBITRARY PRECEDENCE RELATIONS

The scheduling problem n/3/F/C(max) with arbitrary precedence constrai nts between the jobs is studied. A branch and bound algorithm is descr ibed. Bounds are obtained by solving 2-machine subproblems which are r elaxed versions of the current 3-machine problem. These 2-machine prob lems which have precedence constraints can be quickly solved in an opt imal fashion only if the constraints are of a series-parallel (S-P) fo rm. Using methods described in [5], we find an S-P constraints subgrap h which may be solved to obtain a lower bound for each 2-machine subpr oblem. This provides the basis for the calculation of an effective low er bound for the 3-machine case. Computational experience with the alg orithm is reported.