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.