Two-machine group scheduling problem with blocking and anticipatory setups

The authors investigate a realistic two-machine group scheduling problem for determining the group sequence which minimizes the makespan when several jobs are sequenced. Two factors incorporated into the problem make it more realistic than those reported previously. First, a job upon completion of its run on the first machine is blocked if the second machine is busy processing a job. This, the authors believe, is in line with the current trend twoard just-in-time manufacturing where buffer inventories are usually not allowed. Second, the setup on machines 1 and 2 can be performed in anticipation of an arriving job, called anticipatory setup. The problem is proven to be NP-hard in the strong sense by showing an existing hard problem is polynomially reducible to our problem. A heuristic algorithm is presented and is analyzed in the worst-case performance context by considering two different cases. As the optimal solution could not be found conveniently, an average case analysis is perfromed to compare the performance of the proposed heuristic with that of a randomly determined schedule on several test problems. The results obtained show a superior performance by the proposed heuristic on all of the test problems attempted under both cases.