A two-stage flow-shop scheduling problem with incompatible job families and limited waiting time

Abstract

This article presents a two-stage flow-shop problem with a batch machine followed by a discrete machine to minimize makespan. Jobs from incompatible job families should be processed on the discrete machine within a limited waiting time after completion of the batch process, which deviates from the instability of intermediate products in many industries, such as semiconductor and metal-rolling industries. Tight lower bounds and three heuristics are developed based on the problem's properties. Then, a hybrid membrane computing metaheuristic called the HMC algorithm is proposed, in which a dynamic membrane structure is applied to perform effective exploration, and a variable neighbourhood search is embedded in each iteration. In addition, a problem-dependent speed-up neighbourhood is employed to improve the efficiency. Numerical experiments demonstrate that the proposed algorithms can achieve competitive performance compared with state-of-the-art algorithms.