Intelligent optimization under the makespan constraint: Rapid evaluation mechanisms based on the critical machine for the distributed flowshop group scheduling problem

Yuhang Wang, Yuyan Han, Yuting Wang, M. Fatih Tasgetiren, Junqing Li and Kaizhou Gao

European Journal of Operational Research, 2023, vol. 311, issue 3, 816-832

Abstract: In the flowshop scheduling literature, the insertion-based neighborhood search method is often considered to obtain high-quality solutions. It will lead to expending extensive computational effort when evaluating the objective function. Rapid evaluation methods based on Taillard's acceleration can reduce the time complexity of function evaluation. However, existing rapid evaluation methods cannot be applied directly to the distributed flowshop group scheduling problem (DFGSP), especially to minimize the total tardiness time objective. Thus, we first proposed two theorems and their proofs based on the critical machine. Then, two rapid evaluation methods based on these theorems are proposed to accelerate the evaluation of the objective. Considering the multiple coupled sub-problems in the DFGSP, we proposed a cooperative iterated greedy algorithm (CIG) combining two rapid evaluation methods, in which inter-group and intra-group neighborhood search strategies are proposed to enhance the search depth and breadth. Comprehensive statistical experiments show that computational effort is extensively decreased in the calculation of total tardiness time, and the CIG algorithm significantly outperforms the eight compared algorithms.

Keywords: Scheduling; Distributed flowshop; Rapid evaluation; Critical machine; Tardiness time (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723003740
Full text for ScienceDirect subscribers only

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:eee:ejores:v:311:y:2023:i:3:p:816-832

DOI: 10.1016/j.ejor.2023.05.010

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().