Scheduling a single batch processing machine with non-identical two-dimensional job sizes

doi:10.1016/j.eswa.2022.116907

Scheduling a single batch processing machine with non-identical two-dimensional job sizes

2022-09-01

4

PRE

AI

DOI：10.1016/j.eswa.2022.116907

Original

Original request for help

Save

Abstract

En 中文

This paper considers a single batch processing machine scheduling problem with non-identical two-dimensional job sizes. Jobs may be rotated but must be placed orthogonally without overlapping in the machine. The machine can simultaneously process a batch of jobs as long as its two-dimensional capacity is not exceeded. The processing time of a batch is defined by the longest processing time of all jobs in the batch. The objective is to assign jobs to batches considering the machine capacity constraint such that the makespan is minimized. An improved mixed integer programming formulation is proposed to reduce the solution space. 16 heuristics, combining four job sequencing, two batch selection, and two job placement alternatives, are investigated. The effectiveness of the model and heuristics is analyzed through a comprehensive experimental study. The results show that the LPTBFSA heuristic outperforms the others, in which jobs are sorted in decreasing processing time, a batch is selected for each job based on the best-fit algorithm, and a job is placed in the selected batch following the as compact as possible packing principle. The LPTFFSA heuristic also works well, in which the first-fit algorithm is used to select a batch for each job.

Keywords:

Scheduling

Batch processing machines

Heuristics

Two-dimensional job sizes

Mixed integer programming

Scheduling a single batch processing machine with non-identical two-dimensional job sizes

Abstract

Journal

Organization