Parallel batch scheduling has many applications in the industrial sector, like in material and chemical treatments, mold manufacturing and so on. The number of jobs that can be processed on a machine mostly depends on the shape and size of the jobs and of the machine. This work investigates the problem of batching jobs with multiple sizes and multiple incompatible families. A flow formulation of the problem is exploited to solve it through two column generation-based heuristics. First, the column generation finds the optimal solution of the continuous relaxation, then two heuristics are proposed to move from the continuous to the integer solution of the problem: one is based on the price-and-branch heuristic, the other on a variable rounding procedure. Experiments with several combinations of parameters are provided to show the impact of the number of sizes and families on computation times and quality of solutions.

Parallel batching with multi-size jobs and incompatible job families / Druetto, Alessandro; Pastore, Erica; Rener, Elena. - In: TOP. - ISSN 1134-5764. - ELETTRONICO. - 31:2(2023), pp. 440-458. [10.1007/s11750-022-00644-2]

Parallel batching with multi-size jobs and incompatible job families

Pastore, Erica;Rener, Elena
2023

Abstract

Parallel batch scheduling has many applications in the industrial sector, like in material and chemical treatments, mold manufacturing and so on. The number of jobs that can be processed on a machine mostly depends on the shape and size of the jobs and of the machine. This work investigates the problem of batching jobs with multiple sizes and multiple incompatible families. A flow formulation of the problem is exploited to solve it through two column generation-based heuristics. First, the column generation finds the optimal solution of the continuous relaxation, then two heuristics are proposed to move from the continuous to the integer solution of the problem: one is based on the price-and-branch heuristic, the other on a variable rounding procedure. Experiments with several combinations of parameters are provided to show the impact of the number of sizes and families on computation times and quality of solutions.
2023
TOP
File in questo prodotto:
File Dimensione Formato  
Batching_2022.pdf

accesso aperto

Tipologia: 2a Post-print versione editoriale / Version of Record
Licenza: Creative commons
Dimensione 1.08 MB
Formato Adobe PDF
1.08 MB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

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/11583/2971541