Scheduling a single parallel-batching machine with non-identical job sizes and incompatible job families

We study the scheduling of jobs on a single parallel-batching machine with non-identical job sizes and incompatible job families. Jobs from the same family have the same processing time and can be loaded into a batch, as long as the batch size respects the machine capacity. The objective is to minimize the total weighted completion time; this common scheduling objective is equivalent with the minimization of in-process inventory when all jobs have the same release date. Our problem combines two classic combinatorial problems, namely bin packing and single machine scheduling. We develop three new mixed integer linear-programming formulations, namely an assignment-based formulation, a time-indexed formulation (TIF), and a set-partitioning formulation (SPF). We also propose a column generation (CG) algorithm for the SPF, a branch-and-price (B&P) algorithm and a CG-based heuristic. A heuristic framework based on proximity search is also developed using the TIF. We examine how to reduce the size (number of variables) of the formulations in a preprocessing step. The SPF and B&P can solve instances with non unit and unit job durations to optimality with up to 80 and 150 jobs within reasonable runtime limits, respectively. The proposed heuristics perform better than the methods available in the literature for the same problem.(c) 2022 Elsevier B.V. All rights reserved.

Automated summary

This article studies the scheduling problem of jobs with non-identical sizes and incompatible families on a single parallel-batching machine. By developing new linear programming formulations and heuristic algorithms, the objective of minimizing the total weighted completion time can be achieved.