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

Document Type : Original Article

Authors

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

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

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

International Journal of Industrial Engineering and Management Science
Volume 7, Issue 1 - Serial Number 1
April 2020
Pages 127-145

Files

History

  • Receive Date: 08 January 2020
  • Revise Date: 19 April 2020
  • Accept Date: 17 June 2020

Share

How to cite

Statistics