This paper deals with the 1 | p- batch , sj≤ b| ∑ Cj scheduling problem, where jobs are scheduled in batches on a single machine in order to minimize the total completion time. A size is given for each job, such that the total size of each batch cannot exceed a fixed capacity b. A graph-based model is proposed for computing a very effective lower bound based on linear programming; the model, with an exponential number of variables, is solved by column generation and embedded into both a heuristic price and branch algorithm and an exact branch and price algorithm. The same model is able to handle parallel-machine problems like Pm| p- batch , sj≤ b| ∑ Cj very efficiently. Computational results show that the new lower bound strongly dominates the bounds currently available in the literature, and the proposed heuristic algorithm is able to achieve high-quality solutions on large problems in a reasonable computation time. For the single-machine case, the exact branch and price algorithm is able to solve all the tested instances with 30 jobs and a good amount of 40-job examples.
Column generation for minimizing total completion time in a parallel-batching environment / Alfieri, A.; Druetto, A.; Grosso, A.; Salassa, F.. - In: JOURNAL OF SCHEDULING. - ISSN 1094-6136. - ELETTRONICO. - 24:(2021), pp. 569-588. [10.1007/s10951-021-00703-9]
Column generation for minimizing total completion time in a parallel-batching environment
Alfieri A.;Salassa F.
2021
Abstract
This paper deals with the 1 | p- batch , sj≤ b| ∑ Cj scheduling problem, where jobs are scheduled in batches on a single machine in order to minimize the total completion time. A size is given for each job, such that the total size of each batch cannot exceed a fixed capacity b. A graph-based model is proposed for computing a very effective lower bound based on linear programming; the model, with an exponential number of variables, is solved by column generation and embedded into both a heuristic price and branch algorithm and an exact branch and price algorithm. The same model is able to handle parallel-machine problems like Pm| p- batch , sj≤ b| ∑ Cj very efficiently. Computational results show that the new lower bound strongly dominates the bounds currently available in the literature, and the proposed heuristic algorithm is able to achieve high-quality solutions on large problems in a reasonable computation time. For the single-machine case, the exact branch and price algorithm is able to solve all the tested instances with 30 jobs and a good amount of 40-job examples.File | Dimensione | Formato | |
---|---|---|---|
Alfieri2021_Article_ColumnGenerationForMinimizingT.pdf
accesso aperto
Tipologia:
2a Post-print versione editoriale / Version of Record
Licenza:
Creative commons
Dimensione
644.13 kB
Formato
Adobe PDF
|
644.13 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11583/2929750