A generalized constructive algorithm using insertion-based heuristics
Abstract
In this paper, a generalized constructive algorithm referred to as GCA is presented which makes it possible to select a wide variety of heuristics just by the selection of its arguments values. A general framework for generating permutations of integers is presented. This framework, referred to as PERMGEN, forms a link between the numbering of permutations and steps in the insertion-based heuristics. A number of arguments controlling the operation of GCA are identified. Features and benefits of the generalized algorithm are presented through the extension of the NEH heuristic, a successful heuristic solution approach of Nawaz, Enscore, and Ham for the permutation flowshop problem (PFSP). The goal of the experimental study is to improve the performance of the NEH heuristic on the PFSP. To achieve this goal, the space of algorithmic control arguments is searched for a combination of values that define an algorithm providing lower makespan solutions than NEH, in a linear increase of CPU t...ime. Computational experiments on a set of 120 benchmark problem instances, originally proposed by Taillard, are performed to establish a more robust version of the original NEH constructive heuristic. The proposed procedures outperform NEH, preserving its efficiency and simplicity.
Keywords:
Permutations numbering / NP-complete problems / NEH heuristic / Makespan / Insertion move / FlowshopSource:
Computers & Operations Research, 2016, 66, 29-43Publisher:
- Pergamon-Elsevier Science Ltd, Oxford
DOI: 10.1016/j.cor.2015.07.009
ISSN: 0305-0548
WoS: 000366779900004
Scopus: 2-s2.0-84940705319
Collections
Institution/Community
Fakultet organizacionih naukaTY - JOUR AU - Danilović, Miloš AU - Ilić, Oliver PY - 2016 UR - https://rfos.fon.bg.ac.rs/handle/123456789/1580 AB - In this paper, a generalized constructive algorithm referred to as GCA is presented which makes it possible to select a wide variety of heuristics just by the selection of its arguments values. A general framework for generating permutations of integers is presented. This framework, referred to as PERMGEN, forms a link between the numbering of permutations and steps in the insertion-based heuristics. A number of arguments controlling the operation of GCA are identified. Features and benefits of the generalized algorithm are presented through the extension of the NEH heuristic, a successful heuristic solution approach of Nawaz, Enscore, and Ham for the permutation flowshop problem (PFSP). The goal of the experimental study is to improve the performance of the NEH heuristic on the PFSP. To achieve this goal, the space of algorithmic control arguments is searched for a combination of values that define an algorithm providing lower makespan solutions than NEH, in a linear increase of CPU time. Computational experiments on a set of 120 benchmark problem instances, originally proposed by Taillard, are performed to establish a more robust version of the original NEH constructive heuristic. The proposed procedures outperform NEH, preserving its efficiency and simplicity. PB - Pergamon-Elsevier Science Ltd, Oxford T2 - Computers & Operations Research T1 - A generalized constructive algorithm using insertion-based heuristics EP - 43 SP - 29 VL - 66 DO - 10.1016/j.cor.2015.07.009 UR - conv_1772 ER -
@article{ author = "Danilović, Miloš and Ilić, Oliver", year = "2016", abstract = "In this paper, a generalized constructive algorithm referred to as GCA is presented which makes it possible to select a wide variety of heuristics just by the selection of its arguments values. A general framework for generating permutations of integers is presented. This framework, referred to as PERMGEN, forms a link between the numbering of permutations and steps in the insertion-based heuristics. A number of arguments controlling the operation of GCA are identified. Features and benefits of the generalized algorithm are presented through the extension of the NEH heuristic, a successful heuristic solution approach of Nawaz, Enscore, and Ham for the permutation flowshop problem (PFSP). The goal of the experimental study is to improve the performance of the NEH heuristic on the PFSP. To achieve this goal, the space of algorithmic control arguments is searched for a combination of values that define an algorithm providing lower makespan solutions than NEH, in a linear increase of CPU time. Computational experiments on a set of 120 benchmark problem instances, originally proposed by Taillard, are performed to establish a more robust version of the original NEH constructive heuristic. The proposed procedures outperform NEH, preserving its efficiency and simplicity.", publisher = "Pergamon-Elsevier Science Ltd, Oxford", journal = "Computers & Operations Research", title = "A generalized constructive algorithm using insertion-based heuristics", pages = "43-29", volume = "66", doi = "10.1016/j.cor.2015.07.009", url = "conv_1772" }
Danilović, M.,& Ilić, O.. (2016). A generalized constructive algorithm using insertion-based heuristics. in Computers & Operations Research Pergamon-Elsevier Science Ltd, Oxford., 66, 29-43. https://doi.org/10.1016/j.cor.2015.07.009 conv_1772
Danilović M, Ilić O. A generalized constructive algorithm using insertion-based heuristics. in Computers & Operations Research. 2016;66:29-43. doi:10.1016/j.cor.2015.07.009 conv_1772 .
Danilović, Miloš, Ilić, Oliver, "A generalized constructive algorithm using insertion-based heuristics" in Computers & Operations Research, 66 (2016):29-43, https://doi.org/10.1016/j.cor.2015.07.009 ., conv_1772 .