Lower bounding schemes for flowshops with blocking in-process

While there is a considerable amount of research that deals with a flowshop with no storage constraints, few works have addressed the flowshop with blocking in-process. Scheduling problems with blocking arise in serial manufacturing processes where no intermediate buffer storage is available. This paper proposes a lower bound, which exploits the occurrence of blocking, on the total tardiness of the jobs. Its efficiency is evaluated using a branch-and-bound algorithm on several problems. A lower bound on the makespan is also derived and computational tests are presented.