Shop problems with two machines and time lags

We consider Job-Shop and Flow-Shop scheduling problems with two machines, no more than two operations per job, and Time Lags, i.e., a minimum time interval between the completion time of the first operation and the starting time of the second one. We give complexity results for the preemptive and nonpreemptive cases and study the relationship between the two problems. For the Flow-Shop problem we give lower bounds and upper bounds and analyze their worst-case performances. Finally we define a Tabu Search algorithm and prove the effectiveness of the proposed bounds through extensive computational results.