A co-evolutionary genetic algorithm for the two-machine flow shop group scheduling problem with job-related blocking and transportation times

摘要

This study investigates a new two-machine flow shop group scheduling problem with job-related blocking and transportation times, which is derived from the realistic pipe-making process of steel pipe products in the modern steel manufacturing industry. In contrast to the traditional blocking constraint, the attributes of jobs, not the quantity of jobs in the buffer area, are used to determine the need for a blocking feature. The objective is to minimize the makespan. We present a mixed integer linear programming model and prove that the problem is strongly NP-hard. As the problem is a joint decision of two sub-problems, namely group scheduling and job scheduling within each group, a co-evolutionary genetic algorithm (CGA) is proposed to solve it. In the proposed CGA, the two sub-problems are synergistically evolved via a co-evolutionary framework. A block-mining-based artificial chromosome construction strategy is designed to speed up the convergence process. Computational experiments based on actual production data are carried out. The results indicate that the proposed CGA is effective for the considered problem. (C) 2020 Elsevier Ltd. All rights reserved.