A constraint programming approach for a batch processing problem with non-identical job sizes

This paper presents a constraint programming approach for a batch processing machine on which a finite number of jobs of non-identical sizes must be scheduled. A parallel batch processing machine can process several jobs simultaneously and the objective is to minimize the maximal lateness. The constraint programming formulation proposed relies on the decomposition of the problem into finding an assignment of the jobs to the batches, and then minimizing the lateness of the batches on a single machine. This formulation is enhanced by a new optimization constraint which is based on a relaxed problem and applies cost-based domain filtering techniques. Experimental results demonstrate the efficiency of cost-based domain filtering techniques. Comparisons to other exact approaches clearly show the benefits of the proposed approach: it can optimally solve problems that are one order of magnitude greater than those solved by a mathematical formulation or by a branch-and-price.

► We schedule jobs with non-identical sizes on a batch processing machine.
► We examine a constraint programming model minimizing the maximal lateness.
► A new optimization constraint applies cost-based domain filtering techniques.
► A classical bin packing search algorithm applies a new value selection heuristic.
► Our approach outperforms a mathematical formulation and a branch-and-price.