Modelling batch processing machines problems with symmetry breaking and arc flow formulation

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 problems addressed in this work consist of grouping jobs in batches and scheduling this 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 higher processing time of all the jobs assigned to it. Jobs can also consider non-identical release times; in this case, the batch can only be processed after the job with the longest release time is available. This thesis discusses four different batch scheduling problems, which consider different characteristics: single processing machine 1|sj , B|Cmax, parallel processing machines Pm|sj , B|Cmax, single processing machine and non-identical release times 1|rj , sj , B|Cmax, parallel processing machines and non-identical release times Pm|rj , sj , B|Cmax. New mathematical formulations are proposed exploiting the treatment of symmetry for these problems. In addition, an arc-flow-based model is presented for problems 1|sj , B|Cmax and Pm|sj , B|Cmax. The mathematical models are solved using CPLEX, and computational results show that the proposed models have a better performance than other models in the literature.