|
A fast and scalable heuristic for makespan minimization in permutation flowshop scheduling
|
A. Olalekan Olasupo   , E. Olasunkanmi , O. Ogunfuye |
| Department of Industrial and Production Engineering, University of Ibadan, Nigeria. |
|
|
Abstract: (207 Views) |
The permutation flowshop scheduling problem (PFSP) is a classical NP-hard problem in production and operations management, where the objective is to minimize the makespan across multiple machines. Although established heuristics such as NEH, Gupta, and CDS are widely applied, their performance often declines in large-scale instances due to increased computational time and reduced scalability. This study proposes a fast heuristic based on a modified Johnson’s rule applied pairwise between the first machine and each subsequent machine. For each pair, Johnson’s two-machine algorithm generates a sequence, which is then evaluated on the full set of machines, and the best-performing sequence is selected as the final solution. Computational experiments on randomly generated instances of different sizes demonstrate that the proposed method achieves competitive makespan performance while significantly reducing CPU time compared to NEH and CDS, and providing better scalability than Gupta. Statistical validation using the Wilcoxon signed-rank test confirms that the proposed heuristic outperforms Gupta in solution quality and is considerably faster than NEH and CDS in execution time. These findings establish the proposed heuristic as a computationally efficient and statistically reliable approach for solving large-scale PFSPs, providing a valuable tool for production scheduling in industrial operations.
|
|
| Keywords: Permutation Flow shop Scheduling, Makespan Minimization, Heuristic, Johnson’s Algorithm, Scalability. |
|
|
Full-Text [PDF 422 kb]
(16 Downloads)
|
Type of Study: Research |
Subject:
Special
Received: 2025/03/28 | Accepted: 2025/06/24 | Published: 2025/07/1
|
|
|
|
|
|
|
| Send email to the article author |
|
|
|
| Add your comments about this article |
|
|
|
