Parallel batch scheduling has many applications in the industrial sector, such as material and chemical treatments, components creation through mold or additive manufacturing, and so on. The number of jobs that can be processed on a machine mostly depends on the shape and dimension of the jobs and of the machine. Literature provides many researches on the topic with several batching criteria however, to the authors knowledge, there is no study that considers batching jobs with multiple size constraints. The work investigates this problem, by considering that the batch capacity cannot exceed the sum of sizes of the jobs composing it, for each dimension (e.g., height and volume). A solution to the problem is generated by a column generation based heuristic. The heuristic first generates a set of the most promising batches through column generation by exploiting dynamic programming for the pricing procedure; then an integer optimal solution is built with the commercial solver CPLEX. The algorithm is further improved with a variable fixing procedure that speeds up the integer solution generation. Experiments are run on instances with several combinations of parameters and results show the impact of the number and type of sizes on computational times and quality of solutions. Some considerations are extended to the problem that also considers incompatible job families.

Parallel batching with multi-size jobs

Alessandro Druetto;
2021-01-01

Abstract

Parallel batch scheduling has many applications in the industrial sector, such as material and chemical treatments, components creation through mold or additive manufacturing, and so on. The number of jobs that can be processed on a machine mostly depends on the shape and dimension of the jobs and of the machine. Literature provides many researches on the topic with several batching criteria however, to the authors knowledge, there is no study that considers batching jobs with multiple size constraints. The work investigates this problem, by considering that the batch capacity cannot exceed the sum of sizes of the jobs composing it, for each dimension (e.g., height and volume). A solution to the problem is generated by a column generation based heuristic. The heuristic first generates a set of the most promising batches through column generation by exploiting dynamic programming for the pricing procedure; then an integer optimal solution is built with the commercial solver CPLEX. The algorithm is further improved with a variable fixing procedure that speeds up the integer solution generation. Experiments are run on instances with several combinations of parameters and results show the impact of the number and type of sizes on computational times and quality of solutions. Some considerations are extended to the problem that also considers incompatible job families.
31st European Conference on Operational Research
Atene
11/07/2021 - 14/07/2021
31st European Conference on Operational Research
Rudolf Vetschera
25
25
https://www.euro-online.org/media_site/reports/EURO31_AB.pdf
Scheduling, Mixed-Integer Programming, Column Generation
Alessandro Druetto, Elena Rener, Erica Pastore
File in questo prodotto:
File Dimensione Formato  
EURO31_AB.pdf

Accesso aperto

Descrizione: Book of Abstracts
Tipo di file: MATERIALE NON BIBLIOGRAFICO
Dimensione 2.92 MB
Formato Adobe PDF
2.92 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/1795395
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact