A Variant Iterated Greedy Algorithm Integrating Multiple Decoding Rules for Hybrid Blocking Flow Shop Scheduling Problem

Yong Wang, Yuting Wang () and Yuyan Han ()
Additional contact information
Yong Wang: School of Computer Science, Liaocheng University, Liaocheng 252059, China
Yuting Wang: School of Computer Science, Liaocheng University, Liaocheng 252059, China
Yuyan Han: School of Computer Science, Liaocheng University, Liaocheng 252059, China

Mathematics, 2023, vol. 11, issue 11, 1-25

Abstract: This paper studies the hybrid flow shop scheduling problem with blocking constraints (BHFSP). To better understand the BHFSP, we will construct its mixed integer linear programming (MILP) model and use the Gurobi solver to demonstrate its correctness. Since the BHFSP exists parallel machines in some processing stages, different decoding strategies can obtain different makespan values for a given job sequence and multiple decoding strategies can assist the algorithm to find the optimal value. In view of this, we propose a hybrid decoding strategy that combines both forward decoding and backward decoding to select the minimal objective function value. In addition, a hybrid decoding-assisted variant iterated greedy (VIG) algorithm to solve the above MILP model. The main novelties of VIG are a new reconstruction mechanism based on the hybrid decoding strategy and a swap-based local reinforcement strategy, which can enrich the diversity of solutions and explore local neighborhoods more deeply. This evaluation is conducted against the VIG and six state-of-the-art algorithms from the literature. The 100 tests showed that the average makespan and the relative percentage increase (RPI) values of VIG are 1.00% and 89.6% better than the six comparison algorithms on average, respectively. Therefore, VIG is more suitable to solve the studied BHFSP.

Keywords: blocking; hybrid decoding; hybrid flow shop scheduling; iterated greedy (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/11/2453/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/11/2453/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:11:p:2453-:d:1155783

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().