Automatic design of constructive heuristics for a reconfigurable distributed flowshop group scheduling problem

• Published in: Computers & operations research 2024-01, Vol.161, p.106432, Article 106432
• Main Authors: Zhang, Biao, Meng, Lei-lei, Lu, Chao, Han, Yu-yan, Sang, Hong-yan
• Format: Article
• Language: English
• Subjects: automatic algorithm design; constructive heuristic; distributed flowshop scheduling; group scheduling; reconfigurability
• ISSN: 0305-0548
• DOI: 10.1016/j.cor.2023.106432

•Proposing a meta-algorithm of constructive heuristics for the RDFGSP.•Designing specific values for configurable parameters in meta-algorithm.•Designing an AAD method to conceive constructive heuristics automatically. This study addresses a reconfigurable distributed flowshop group scheduling problem (RDFGSP), the characteristics of which lie in the reconfigurability of the flowlines, and the families with grouped jobs. Given its NP-hard property, we are committed to developing constructive heuristics to meet real-time requirements. By combining different algorithm components, a large number of constructive heuristics can be obtained, rendering the identification of the best heuristic through artificial experimental design quite difficult. To take full advantage of the problem domain knowledge, the iterated F-Race (I/F-Race), an automatic algorithm design (AAD) methodology, is employed to automatically conceive constructive heuristics with minimum human intervention. Initially, a general and configurable meta-algorithm is developed by considering the problem-specific characteristics, which integrates the configurable routing rule, sequencing rule, dispatching rule, and non-delay factor. Subsequently, by using the AAD, the meta-algorithm can be instantiated to a complete constructive heuristic, which can generate active, non-delay, or hybrid schedules. In the experimental study, compared with the full factorial design, the AAD can conceive a much more effective automated heuristic by tuning a much smaller number of configurations. Furthermore, the solution accuracy and efficiency of the generated heuristic are validated in solving small-scale problems by comparison with the commercial solver and other heuristics. The generated heuristic substantiates an advancement of approximately 28-fold in contrast to the best compared heuristic at a very small cost when solving large-scale problems.