Decomposition heuristics for parallel-machine multiple orders per job scheduling problems with a common due date

Jens Rocholl and Lars Mönch

Journal of the Operational Research Society, 2021, vol. 72, issue 8, 1737-1753

Abstract: Scheduling problems for identical parallel machines with earliness-tardiness objective are studied that are motivated by manufacturing processes in 300-mm wafer fabs. Wafers are transferred by front opening unified pods (FOUPs) in such fabs. Only a limited number of FOUPs is allowed since a large number of FOUPs results in a highly congested automated material handling system. A FOUP can contain a group of orders. A nonrestrictive common due date is assumed for all orders. Only orders of the same family can be grouped together in a FOUP. The lot and the item processing mode are differentiated in this article. Mixed integer linear programming (MILP) models are provided for both modes. It is shown that the two scheduling problems are NP-hard. Simple decomposition heuristics based on list scheduling and bin packing procedures are proposed. Biased random-key genetic algorithm (BRKGA)-based decomposition schemes are designed for the two scheduling problems. The BRKGAs are hybridised with the simple heuristics and an integer programming-based job formation approach in the lot processing mode. Results of computational experiments based on randomly generated problem instances are analysed and discussed for both scheduling problems. The results show that the proposed heuristics perform well with respect to solution quality and computing time. The BRKGA-type approaches clearly outperform the other heuristics.

Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2019.1640589 (text/html)
Access to full text is restricted to subscribers.

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:taf:tjorxx:v:72:y:2021:i:8:p:1737-1753

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1080/01605682.2019.1640589

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().