.png){kind=icon}
Return
Single batch processing machine scheduling with two-dimensional bin packing constraints
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ijpe.2017.11.015.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
10
Papers:
8.0K
Citations:
3.6W
Organization
Cited Papers
.png){kind=icon}
ShareSaveOn the Impact of Formative Assessment on Student Motivation, Achievement, and Conceptual Change
PREAI
ShareSaveShareSaveA Randomized Trial Comparing a Brief Meditation Retreat to a Vacation: Effects on Daily Well-Being
PREAI
ShareSave
ShareSaveShareSave
View more