SHOP PROBLEMS WITH 2 MACHINES AND TIME LAGS

We consider Job-Shop and Flow-Shop scheduling problems with two machin es, no more than two operations per job, and Time Lags, i.e., a minimu m time interval between the completion rime of the first operation and the starting time of the second one. We give complexity results for t he preemptive and nonpreemptive cases and study the relationship betwe en the two problems. For the Flow-Shop problem we give lower bounds an d upper bounds and analyze their worst-case performances. Finally we d efine a Tabu Search algorithm and prove the effectiveness of the propo sed bounds through extensive computational results.