Blocking flowshop scheduling problems with release dates

In a flowshop, the current stage has to remain work-in-process and cannot release any task to the downstream stage once the buffer is stuffed. This scheduling phenomenon is called blocking, and it usually occurs in an in-dustrial setting because of the buffer capacity or the product volume. This study addresses several blocking flowshop scheduling problems to individually optimize the following criteria, i.e. makespan, maximum lateness, or maximum delivery-completion time, in which the tasks are available at different release dates. Given that these scheduling problems are strongly NP-complete, exact and metaheuristic algorithms are designed for different scale instances. An effective branch and bound method is proposed to search exact solutions for small-scale instances within a given period, where well-designed branching rules and lower bounds prune considerable invalid nodes. Further, to seek high-quality feasible schedules in a short time, a discrete artificial bee colony algorithm is provided for medium-scale instances, where a dispatching-rule-based initialization, a series of efficient non-delay variable neighborhood search mechanisms, and a well-designed disturbing scheme enhance the optimization capability. Comprehensive computational tests are conducted to evaluate the effectiveness of the proposed algorithms.

Automated summary

This study addresses the blocking flowshop scheduling problems and proposes exact and metaheuristic algorithms to optimize efficiency by considering different criteria such as makespan, maximum lateness, or maximum delivery-completion time. The algorithms are designed for different scale instances and have been evaluated through comprehensive computational tests.