Parallel Batch Processing Machine Scheduling Under Two-Dimensional Bin-Packing Constraints

doi:10.1109/TR.2022.3201333

Return

Parallel Batch Processing Machine Scheduling Under Two-Dimensional Bin-Packing Constraints

2023-09-01

PRE

张晓盼 (Xiaopan Zhang)

Mengjie Shan

Ju Zeng *

DOI：10.1109/TR.2022.3201333

Original

Original request for help

Save

Abstract

En 中文

The parallel batch processing machine scheduling problem with two-dimensional bin packing constraints (PBS-2D) has appeared in many industrial environments, but the research on this problem is still not sufficient. In this article, we use the 2-D rectangular packing constraints to describe the spatial geometric layout of jobs more accurately, and propose a mixed integer linear programming (MILP) model to minimize the makespan of PBS-2D. According to the in-depth analysis of the problem properties, PBS-2D is separated into three subproblems, which are job-machine assignment, 2-D job placement, and job sequence optimization. An improved biased random key genetic algorithm (OBRKGA) is proposed to solve job-machine assignment and job sequence optimization. This algorithm generates the initial population based on the idea of orthogonal experimental design, so that the whole solution space can be scanned evenly when generating the initial solution, making the algorithm be more likely to find better solutions for subsequent evolution. At the same time, a bin packing algorithm based on best fit is designed to handle 2-D job placement problem. Finally, the algorithms are tested on a large number of randomly generated instances, the results show that OBRKGA outperformed the original BRKGA, the classical moth-flame optimization algorithm, particle swarm optimization algorithm, gravity search algorithm, and MILP.

Keywords:

Job shop scheduling

Genetic algorithms

Optimization

Heuristic algorithms

Batch production systems

Production

Parallel machines

2-D bin packing constraints

genetic algorithm (GA)

mixed integer linear programming (MILP)

orthogonal design