Exact and metaheuristic algorithms for flow-shop scheduling problems with release dates. Issue 11 (2nd November 2022)

• Record Type: Journal Article
• Authors: Ren, Tao; Wang, Xinyue; Liu, Tianyi; Wu, Chin-Chia; Bai, Danyu; Lin, Lin; Guo, Meiting
• Is Part Of: Engineering optimization. Volume 54:Issue 11(2022)
• Page Start: 1853
• Page End: 1869
• Publication Date: 2022-11-02
• Subjects: Flow-shop scheduling -- discrete differential evolution -- branch and bound -- release date; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2021.1961763
• Languages: English
• ISSNs: 0305-215X

Abstract

Abstract : Flow-shop scheduling is an extremely popular optimization model in industrial production, where each job must be scheduled on a series of machines following an identical process. The optimal criteria, makespan and maximum delivery–completion time, are investigated separately. A mixed integer programming model is built to evaluate the exact algorithm in simulation experiments. Given that these problems are NP hard and cannot be solved in polynomial time, exact and metaheuristic methods are proposed for different problem sizes. For small-scale instances, optimal schedules are achieved using an effective branch-and-bound algorithm, in which elaborately designed lower bound and branching rules significantly improve computational efficiency. For medium-scale instances, satisfactory solutions are obtained using a hybrid discrete differential evolution algorithm with improvement schemes to promote its performance. The experimental results show the effectiveness of the proposed algorithms.