IMPACT OF INPUT SEQUENCE ON N-NEH+ ALGORITHM

1 PUKA Radosław
Co-authors:
1 ŁAMASZ Bartosz
Institution:
1 AGH University of Science and Technology, Cracow, Poland, EU, rpuka@zarz.agh.edu.plblamasz@zarz.agh.edu.pl
Conference:
10th Carpathial Logistics Congress, Hotel Pod Zámkom, Bojnice, Slovakia, EU, June 15 - 17, 2022
Proceedings:
Proceedings 10th Carpathial Logistics Congress
Pages:
191-196
ISBN:
978-80-88365-08-2
ISSN:
2694-9318
Published:
31st October 2022
Proceedings of the conference have been sent to Web of Science and Scopus for evaluation and potential indexing.
Metrics:
273 views / 103 downloads
Abstract

The job scheduling problem is one of the biggest optimization challenges for manufacturing companies. A properly performed planning can reduce both cost and production time. A scheduling problem that has been the subject of research in numerous research papers is the permutation flow shop scheduling problem (PFSP) with makespan as optimization (minimization) criterion. Frequently used algorithms to solve PFSP is the constructive deterministic heuristic algorithm NEH. Many researchers have analyzed the effectiveness of the NEH algorithm. An example of the issues studied is the importance of the order of input data on the results obtained by the NEH algorithm. In the literature, a number of variants of NEH-based algorithms can be found. The N-NEH+ algorithm is considered to be one of the most efficient. Therefore, this paper focuses on analyzing the influence of the input sequence on the results obtained by the N-NEH+ algorithm. Two most popular benchmarks were used to analyze the influence of the input sequence: the Taillard's benchmark and the VRF benchmark. The results obtained confirm that the input sequence has a significant impact on the results obtained by the N-NEH+ algorithm. However, this influence is less than that of the NEH algorithm.

Keywords: PFSP, N-list technique, N-NEH+ algorithm, scheduling, input sequence

© This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Scroll to Top