Single batch processing machine scheduling with two-dimensional bin packing constraints

Xueping Li and Kaike Zhang

International Journal of Production Economics, 2018, vol. 196, issue C, 113-121

Abstract: We study the problem of minimizing the makespan for jobs on a single batch processing machine (BPM). A BMP can process several jobs as a batch simultaneously. Unlike the classic batch processing machine scheduling problems in which the capacity of a machine is modeled as one-dimensional knapsack constraints, in this research, the machine's capacity is represented by a two-dimensional rectangle and a job occupies a rectangle of its dimensions, i.e., width and height, while being processed on the machine. The processing time and the dimensions of the jobs are non-identical. A batch's processing time equals to the longest processing time of jobs in the batch. A batch is feasible only if the jobs can be placed in the machine without overlapping with each other. Arising from practical industrial applications such as advanced manufacturing and wafer fabrication, this problem is a generalization of both the classic single BPM scheduling problem and the two-dimensional bin packing problem (2D-BPP), which are both proven to be NP-hard. Thus, it is NP-hard as well. We present a mixed integer programming (MIP) model for this problem. We also develop heuristic algorithms to tackle this problem, including four single-sequence based heuristics, a biased random-key genetic algorithm (BRKGA), and a hybrid bin loading (HBL) algorithm. The performances of the MIP model and proposed algorithms are compared based on a set of random generated instances.

Keywords: Scheduling; Batch processing machine (BPM); Two-dimensional bin packing problem (2D-BPP); Biased random-key genetic algorithm (BRKGA); Bin loading problem (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0925527317303997
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:proeco:v:196:y:2018:i:c:p:113-121

DOI: 10.1016/j.ijpe.2017.11.015

Access Statistics for this article

International Journal of Production Economics is currently edited by Stefan Minner

More articles in International Journal of Production Economics from Elsevier
Bibliographic data for series maintained by Catherine Liu ().