A Hybrid Large Neighborhood Search Method for Minimizing Makespan on Unrelated Parallel Batch Processing Machines with Incompatible Job Families

Bin Ji (), Xin Xiao, Samson S. Yu and Guohua Wu
Additional contact information
Bin Ji: School of Traffic & Transportation Engineering, Central South University, Changsha 410075, China
Xin Xiao: School of Traffic & Transportation Engineering, Central South University, Changsha 410075, China
Samson S. Yu: School of Engineering, Deakin University, Geelong, VIC 3216, Australia
Guohua Wu: School of Traffic & Transportation Engineering, Central South University, Changsha 410075, China

Sustainability, 2023, vol. 15, issue 5, 1-25

Abstract: This paper studies a scheduling problem with non-identical job sizes, arbitrary job ready times, and incompatible family constraints for unrelated parallel batch processing machines, where the batches are limited to the jobs from the same family. The scheduling objective is to minimize the maximum completion time (makespan). The problem is important and has wide applications in the semiconductor manufacturing industries. This study proposes a mixed integer programming (MIP) model, which can be efficiently and optimally solved by commercial solvers for small-scale instances. Since the problem is known to be NP-hard, a hybrid large neighborhood search (HLNS) combined with tabu strategy and local search is proposed to solve large-scale problems, and a lower bound is proposed to evaluate the effectiveness of the proposed algorithm. The proposed algorithm is evaluated on numerous compatible benchmark instances and newly generated incompatible instances. The results of computational experiments indicate that the HLNS outperforms the commercial solver and the lower bound for incompatible problems, while for compatible problems, the HLNS outperforms the existing algorithm. Meanwhile, the comparison results indicate the effectiveness of the tabu and local search strategies.

Keywords: unrelated parallel machines; batch processing; incompatible job families; hybrid large neighborhood search; tabu search; local search (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: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2071-1050/15/5/3934/pdf (application/pdf)
https://www.mdpi.com/2071-1050/15/5/3934/ (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:5:p:3934-:d:1075951

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 ().