Handling ties in heuristics for the permutation flow shop scheduling problem
Samo za registrovane korisnike
2015
Članak u časopisu (Objavljena verzija)
Metapodaci
Prikaz svih podataka o dokumentuApstrakt
The NEH heuristic, as the most efficient procedure for the flow shop scheduling problem is based on constructing a sequence of jobs by iteratively inserting the non-scheduled jobs into a current subsequence. The initial phase of NEH, in which an initial order (priority order) of jobs is defined, and the insertion procedure, usually cause a high number of ties. Unlike the sort of ties in the insertion phase, the ties in the initial phase are not uniquely defined by the definition of NEH. This results in an inaccuracy in most of the large number of published experimental results on this topic. The experimental research, presented in this paper confirms the importance of the inclusion of the information about the sort of ties in the initial phase in any experimental result related to NEH. The conclusion, obtained by this study, is that the range of the objective values for different sorts of ties is often greater than the improvements, published in literature. This allowed us to construct... a very simple algorithm that outperforms published NEH improvements, maintaining NEH's exceptional efficiency. The proposed algorithm also uses the information about the ties in the insertion phase to improve the objective value. The permutation flow shop problem primarily concerns the makespan objective, but the main conclusions can be applied to other flow shop problems as well.
Ključne reči:
Scheduling / Permutation flow shop / NEH heuristic / Makespan / Constructive heuristicIzvor:
Journal of Manufacturing Systems, 2015, 35, 1-9Izdavač:
- Elsevier Sci Ltd, Oxford
DOI: 10.1016/j.jmsy.2014.11.011
ISSN: 0278-6125
WoS: 000354591100001
Scopus: 2-s2.0-84928726052
Institucija/grupa
Fakultet organizacionih naukaTY - JOUR AU - Vasiljević, Dragan AU - Danilović, Miloš PY - 2015 UR - https://rfos.fon.bg.ac.rs/handle/123456789/1382 AB - The NEH heuristic, as the most efficient procedure for the flow shop scheduling problem is based on constructing a sequence of jobs by iteratively inserting the non-scheduled jobs into a current subsequence. The initial phase of NEH, in which an initial order (priority order) of jobs is defined, and the insertion procedure, usually cause a high number of ties. Unlike the sort of ties in the insertion phase, the ties in the initial phase are not uniquely defined by the definition of NEH. This results in an inaccuracy in most of the large number of published experimental results on this topic. The experimental research, presented in this paper confirms the importance of the inclusion of the information about the sort of ties in the initial phase in any experimental result related to NEH. The conclusion, obtained by this study, is that the range of the objective values for different sorts of ties is often greater than the improvements, published in literature. This allowed us to construct a very simple algorithm that outperforms published NEH improvements, maintaining NEH's exceptional efficiency. The proposed algorithm also uses the information about the ties in the insertion phase to improve the objective value. The permutation flow shop problem primarily concerns the makespan objective, but the main conclusions can be applied to other flow shop problems as well. PB - Elsevier Sci Ltd, Oxford T2 - Journal of Manufacturing Systems T1 - Handling ties in heuristics for the permutation flow shop scheduling problem EP - 9 SP - 1 VL - 35 DO - 10.1016/j.jmsy.2014.11.011 UR - conv_1707 ER -
@article{ author = "Vasiljević, Dragan and Danilović, Miloš", year = "2015", abstract = "The NEH heuristic, as the most efficient procedure for the flow shop scheduling problem is based on constructing a sequence of jobs by iteratively inserting the non-scheduled jobs into a current subsequence. The initial phase of NEH, in which an initial order (priority order) of jobs is defined, and the insertion procedure, usually cause a high number of ties. Unlike the sort of ties in the insertion phase, the ties in the initial phase are not uniquely defined by the definition of NEH. This results in an inaccuracy in most of the large number of published experimental results on this topic. The experimental research, presented in this paper confirms the importance of the inclusion of the information about the sort of ties in the initial phase in any experimental result related to NEH. The conclusion, obtained by this study, is that the range of the objective values for different sorts of ties is often greater than the improvements, published in literature. This allowed us to construct a very simple algorithm that outperforms published NEH improvements, maintaining NEH's exceptional efficiency. The proposed algorithm also uses the information about the ties in the insertion phase to improve the objective value. The permutation flow shop problem primarily concerns the makespan objective, but the main conclusions can be applied to other flow shop problems as well.", publisher = "Elsevier Sci Ltd, Oxford", journal = "Journal of Manufacturing Systems", title = "Handling ties in heuristics for the permutation flow shop scheduling problem", pages = "9-1", volume = "35", doi = "10.1016/j.jmsy.2014.11.011", url = "conv_1707" }
Vasiljević, D.,& Danilović, M.. (2015). Handling ties in heuristics for the permutation flow shop scheduling problem. in Journal of Manufacturing Systems Elsevier Sci Ltd, Oxford., 35, 1-9. https://doi.org/10.1016/j.jmsy.2014.11.011 conv_1707
Vasiljević D, Danilović M. Handling ties in heuristics for the permutation flow shop scheduling problem. in Journal of Manufacturing Systems. 2015;35:1-9. doi:10.1016/j.jmsy.2014.11.011 conv_1707 .
Vasiljević, Dragan, Danilović, Miloš, "Handling ties in heuristics for the permutation flow shop scheduling problem" in Journal of Manufacturing Systems, 35 (2015):1-9, https://doi.org/10.1016/j.jmsy.2014.11.011 ., conv_1707 .