Mathematical Modeling and A Novel Heuristic Method for Flexible Job-Shop Batch Scheduling Problem with Incompatible Jobs

Bin Ji, Shujing Zhang, Samson S. Yu and Binqiao Zhang ()
Additional contact information
Bin Ji: School of Traffic & Transportation Engineering, Central South University, Changsha 410075, China
Shujing Zhang: School of Traffic & Transportation Engineering, Central South University, Changsha 410075, China
Samson S. Yu: School of Engineering, Deakin University, Geelong, VIC 3216, Australia
Binqiao Zhang: Hubei Provincial Key Laboratory for Operation and Control of Cascaded Hydropower Station, China Three Gorges University, Yichang 443002, China

Sustainability, 2023, vol. 15, issue 3, 1-26

Abstract: This paper investigates a novel flexible job-shop scheduling problem, where the machines have batch-processing capacity, but incompatible jobs cannot be processed in a batch (FJSPBI) simultaneously. This problem has wide applications in discrete manufacturing, especially in chemical and steel casting industries. For the first time, in this study, a 3-indexed mixed-integer linear programming (MILP) model is proposed, which can be efficiently and optimally solved by commercial solvers for small-scale problems. In addition, an improved large neighborhood search (LNS) algorithmic framework with an optimal insertion and tabu-based components (LNSIT) is proposed, which can achieve high-quality solutions for a large-scale FJSPBI in a reasonable time. A perturbation strategy and an optimal insertion strategy are then additionally embedded to improve the exploitation and exploration ability of the algorithm. The proposed model and algorithm are tested on numerous existing benchmark instances without the incompatibility characteristics, and on newly generated instances of the FJSPBI. The experimental results indicate the effectiveness of the proposed MILP model and the algorithm, including the proposed strategies, and the optimal insertion strategy can significantly reduce the computational burden of the LNS algorithm. The comparison results further verify that the proposed LNSIT can directly solve the specific flexible job-shop batch scheduling problem without incompatibility, with better results than existing methods, especially for large-scale instances. Additionally, the impacts of a wide range of characteristics, including batch capacity, incompatibility rate, instance scale, and machine processing rate, on the performance of the LNSIT and the scheduling results are analyzed and presented.

Keywords: flexible job-shop scheduling; batch processing; incompatible jobs; large neighborhood search algorithm (search for similar items in EconPapers)
JEL-codes: O13 Q Q0 Q2 Q3 Q5 Q56 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2071-1050/15/3/1954/pdf (application/pdf)
https://www.mdpi.com/2071-1050/15/3/1954/ (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:jsusta:v:15:y:2023:i:3:p:1954-:d:1041665

Access Statistics for this article

Sustainability is currently edited by Ms. Alexandra Wu

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