2-MACHINE GROUP SCHEDULING PROBLEM WITH BLOCKING AND ANTICIPATORY SETUPS

We investigate a realistic two-machine group scheduling problem for de termining 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 comp letion of its run on the first machine is blocked if the second machin e is busy processing a job. This, we believe, is in line with the curr ent trend toward just-in-time manufacturing where buffer inventories a re usually not allowed. Second, the setup on machines 1 and 2 can be p erformed in anticipation of an arriving job, called anticipatory setup . The problem is proven to be NP-hard in the strong sense by showing a n existing hard problem is polynomially reducible to our problem. A he uristic algorithm is presented and is analyzed in the worst-case perfo rmance context by considering two different cases. As the optimal solu tion could not be found conveniently, an average case analysis is perf ormed to compare the performance of the proposed heuristic with that o f 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.