Shop Problems with two Machines and Time Lags

We consider Job-Shop and Flow-Shop scheduling problems with twomachines, no more than two operations per job and Time Lags i.e.a minimum time intervalbetween the completion time of the firstoperation and the starting time of the second one.We give complexity results for the preemptive and non preemptive casesand study the relationship between the two problems. For the Flow-Shopproblemwe give lower bounds, upper bounds and analyze their worst-caseperformances. Finally we define a Tabu Search algorithm and provethe effectiveness of the proposed bounds throughextensive computational results.