MINIMIZING MAKESPAN IN A CLASS OF REENTRANT SHOPS

We study the problem of scheduling a chain-reentrant shop, in which ea ch job goes for its processing first to a machine called the primary m achine, then to a number of other machines in a fixed sequence, and fi nally back to the primary machine for its last operation. The problem is to schedule the jobs so as to minimize the makespan. This problem i s unary NP-hard for a general number of machines. We focus in particul ar on the two-machine use that is also at least binary NP-hard. We pro ve some properties that identify a specific class of optimal schedules , and then use these properties in designing an approximation algorith m and a branch-and-bound type optimization algorithm. The approximatio n algorithm, of which we present three versions, has a worst-case perf ormance guarantee of 3/2 along with an excellent empirical performance . The optimization algorithm solves large instances quickly. Finally, we identify a few well solvable special cases and present a pseudo-pol ynomial algorithm for the case in which the first and the last operati ons of any job (on the primary machine) are identical.