Volume 9, Issue 4 (12-2023)
mmr 2023, 9(4): 1-23 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Farahmand Rad S. Solving Permutation Flow shop Problem by the Regulations of Columnar Entries in the Processing Times Matrix. mmr 2023; 9 (4) :1-23
URL: http://mmr.khu.ac.ir/article-1-3183-en.html
URL: http://mmr.khu.ac.ir/article-1-3183-en.html
Payame Noor University, Tehran , sh_fmand@pnu.ac.ir
Abstract: (1089 Views)
Scheduling theory and permutation therein are two important subjects in discrete operation research. In this paper, a new heuristic algorithm is proposed for solving permutation flow shop problem by using regulations of columnar entries in the processing times matrix. There are 
jobs to be processed on 
machines with deterministic processing times and the object is obtaining the minimum of the total time to complete the schedule (makespan). This is not solvable in polynomial time. First, an initial suitable sequence of jobs is determined similar to many heuristics. For this, the matrix 
is made such that every 
determines the measure of the fitness for the location of the 
th old row in the 
th new position. Thereafter, the Bellman Esogbue Nabeshima theorem is used. The presented algorithm is compared with the NEH (the best well-known existing method). This comparison is made by the Taillard’s standard test problems. Computational results demonstrate that the heuristic algorithm is better than some of the proposed heuristics known so far and it is superior with respect to others in a number of Taillard instances. As a result, it is almost as good as NEH and is very promising for the problem. On the basis of the structure of the proposed algorithm, it can perform a role as meta-heuristic.
jobs to be processed on machines with deterministic processing times and the object is obtaining the minimum of the total time to complete the schedule (makespan). This is not solvable in polynomial time. First, an initial suitable sequence of jobs is determined similar to many heuristics. For this, the matrix is made such that every determines the measure of the fitness for the location of the th old row in the th new position. Thereafter, the Bellman Esogbue Nabeshima theorem is used. The presented algorithm is compared with the NEH (the best well-known existing method). This comparison is made by the Taillard’s standard test problems. Computational results demonstrate that the heuristic algorithm is better than some of the proposed heuristics known so far and it is superior with respect to others in a number of Taillard instances. As a result, it is almost as good as NEH and is very promising for the problem. On the basis of the structure of the proposed algorithm, it can perform a role as meta-heuristic.
Keywords: Scheduling, Permutation flow shop, Heuristics, Initial sequences, Time matrix, Makespan, NEH, Taillard’s benchmark
Type of Study: S |
Subject:
Network Flows- Operation Reseach
Received: 2021/03/30 | Revised: 2024/06/23 | Accepted: 2022/03/5 | Published: 2023/12/5 | ePublished: 2023/12/5
Received: 2021/03/30 | Revised: 2024/06/23 | Accepted: 2022/03/5 | Published: 2023/12/5 | ePublished: 2023/12/5
Send email to the article author
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |
