Arc-flow approach for parallel batch processing machine scheduling with non-identical job sizes

Renan Spencer Trindade, Olinto César Bassi de Araújo, Marcia Fampa

Lecture Notes in Computer Science book series (LNCS, volume 12176).

Abstract

Problems of minimizing makespan in scheduling batch processing machines are widely exploited by academic literature, mainly motivated by burn-in tests in the semiconductor industry. The problem addressed in this work consists of grouping jobs into batches and scheduling them in parallel machines. The jobs have non-identical size and processing times. The total size of the batch cannot exceed the capacity of the machine. The processing time of each batch will be equal to the longest processing time among all the jobs assigned to it. This paper proposes an arc-flow based model for minimizing makespan on parallel processing machines 𝑃𝑚|𝑠𝑗,𝐵|𝐶𝑚𝑎𝑥 . The mathematical model is solved using CPLEX, and computational results show that the proposed models have a better performance than other models in the literature.

Citation:

Trindade R.S., de Araújo O.C.B., Fampa M. (2020) Arc-Flow Approach for Parallel Batch Processing Machine Scheduling with Non-identical Job Sizes. In: Baïou M., Gendron B., Günlük O., Mahjoub A.R. (eds) Combinatorial Optimization. ISCO 2020. Lecture Notes in Computer Science, vol 12176. Springer, Cham. https://doi.org/10.1007/978-3-030-53262-8_15