from the conferences organized by TANGER Ltd.
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.