Shop problems with two machines and Time Lags

The paper considers 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. It gives complexity results for the preemptive and non preemptive cases and studies the relations between the two problems. For the Flow-Shop problem the paper gives lower bounds, upper bounds and defines a Tabu Search algorithm. Extensive computational results prove the effectiveness of the proposed bounds.