A memetic algorithm for multistage hybrid flow shop scheduling problem with multiprocessor tasks to minimize makespan

Gholami, Hadi; Rezvan, Mohammad Taghi

doi:10.22034/ijiems.2020.118105

A memetic algorithm for multistage hybrid flow shop scheduling problem with multiprocessor tasks to minimize makespan

Document Type : Original Article

Authors

Hadi Gholami ¹

Mohammad Taghi Rezvan ²

¹ Department of Computer Engineering, Ayatollah Amoli Branch, Islamic Azad University, Amol, Iran.

² Department of Industrial Engineering, Faculty of Engineering, University of Kashan, 6 Km, Ghotbravandi Blvd, Kashan 8731753153, Iran

10.22034/ijiems.2020.118105

Abstract

This paper presents an effective memetic algorithm (MA) for a hybrid flow shop scheduling problem with multiprocessor tasks (HFSMT) to minimize the makespan. The problem is modeled as deterministic by a mixed graph. This problem has at least two production stages, each of which has several machines, operating in parallel. Two sub-problems are considered for solving this problem: determining the sequence of jobs in the first stage and reducing the idle time of the processors in the next stages. The developed algorithm uses an operator called Bad Selection Operator. This operator holds the worst chromosomes of each generation and uses them to search in the space of other problems at predetermined timescales. Besides, this algorithm uses a dynamic adjustment structure to improve the ratio of crossover and mutation operators that could reduce the execution time. The efficiency of the proposed MA is investigated by testing it on well-known benchmark instances and also compared with other algorithms introduced in the literature. Computational results show that this algorithm has a good performance on problems which have more than two stages.

Keywords

Multistage hybrid flow shop

Multiprocessor tasks

Memetic algorithm

Makspan