SINGLE-MACHINE SCHEDULING WITH CHAIN STRUCTURED PRECEDENCE CONSTRAINTS AND SEPARATION TIME WINDOWS

We consider a single machine scheduling problem which we studied to im prove the efficiency of an automated medical laboratory. In this probl em, there are not only chain-structured precedence constraints, but al so minimal and maximal times separating successive jabs in the same ch ain (separation time windows), The criterion to be minimized is the ma kespan, Potential applications are not restricted to medical analysis, This problem often arises in systems where chemical processes are inv olved, Therefore the problem studied in this paper is important in pra ctice, We prove that the problem is nonpolynomial (NP)-complete, As a consequence, we propose three heuristics for large size problems and a branch and bound based algorithm for small size problems. Computation al results are reported.