Modelling and symmetry breaking in scheduling problems on batch processing machines

Abstract

Problems of scheduling batch-processing machines to minimize the makespan are widely exploited in the literature, mainly motivated by real-world applications, such as burn-in tests in the semiconductor industry. These problems consist of grouping jobs in batches and scheduling them on machines. We consider problems where jobs have non-identical sizes and processing times, and the total size of each batch cannot exceed the machine capacity. The processing time of a batch is defined as the longest processing time among all jobs assigned to it. Jobs can also have non-identical release times, and in this case, a batch can only be processed when all jobs assigned to it are available. This paper discusses four different versions of batch scheduling problems, considering a single processing machine or parallel processing machines and considering jobs with or without release times. New mixed-integer linear programming formulations are proposed as enhancements of formulations proposed in the literature, and symmetry breaking constraints are investigated to reduce the size of the feasible sets. Computational results show that the proposed formulations have a better performance than other models in the literature, being able to solve to optimality instances only considered before to be solved by heuristic procedures.

Citation:

Trindade, R. S., de Araújo, O. C. B., Fampa, M. H. C., Müller, F. M. (2018). Modelling and symmetry breaking in scheduling problems on batch processing machines. International Journal of Production Research, 56(22), 7031–7048. https://doi.org/10.1080/00207543.2018.1424371