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.

KEYWORDS:

• Scheduling
• two-stage flow-shop
• parallel batch
• limited waiting time
• incompatible job families

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

Yonglin Li http://orcid.org/0000-0002-0008-0843

Additional information

Funding

This work was supported by the Social Science Research Project of Shanghai [grant number 2017EGL009], the National Natural Science Foundation of China [grant numbers 71840003, 71632008] and MOE (Ministry of Education in China) Project of Humanities and Social Sciences [grant number 19YJA790028].