An effective new heuristic algorithm for solving permutation flow shop scheduling problem
Publish place: Transactions on Combinatorics، Vol: 11، Issue: 1
Publish Year: 1401
نوع سند: مقاله ژورنالی
زبان: English
View: 206
This Paper With 13 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
JR_COMB-11-1_002
تاریخ نمایه سازی: 17 آبان 1400
Abstract:
The deterministic permutation flow shop scheduling problem with makespan criterion is not solvable in polynomial time. Therefore, researchers have thought about heuristic algorithms. There are many heuristic algorithms for solving it that is a very important combinatorial optimization problem. In this paper, a new algorithm is proposed for solving the mentioned problem. The presented algorithm chooses the weighted path that starts from the up-left corner and reaches the down-right in the matrix of jobs processing times and calculates the biggest sum of the times in the footprints of this path. The row with the biggest sum permutes among all the rows of the matrix for locating the minimum of makespan. This method was run on Taillard’s standard benchmark and the solutions were compared with the optimum or the best ones as well as ۱۴ famous heuristics. The validity and effectiveness of the algorithm are shown with tables and statistical evaluation.
Keywords:
Authors
Shahriar Farahmand rad
Department of Mathematics, Payame Noor University of ABCD, P.O.Box ۱۹۳۹۵-۳۶۹۷, Tehran, Iran