Column generation for minimizing total completion time in a parallel-batching environment
Journal of Scheduling · 2021-12 · 24 (6) · 569-588
DOI: 10.1007/s10951-021-00703-9 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Scheduling, online erschienen am 01.10.2021. Verfasst von A. Alfieri und 3 weiteren Autor:innen. Die Arbeit wurde bisher 13-mal zitiert (Crossref) und nennt 27 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Università degli Studi di Torino.
Abstract (Originalsprache)
This paper deals with the $$1|{p-\text {batch}, s_j\le b}|\sum C_j$$ 1 | p - batch , s j ≤ b | ∑ C j 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-\text {batch}, s_j\le b}|\sum C_j$$ P m | p - batch , s j ≤ b | ∑ C j 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.
Förderung
- Università degli Studi di Torino
Zitieren
APA
Alfieri, A., Druetto, A., Grosso, A., & Salassa, F. (2021). Column generation for minimizing total completion time in a parallel-batching environment. Journal of Scheduling, 24(6), 569-588. https://doi.org/10.1007/s10951-021-00703-9
Vancouver
Alfieri A, Druetto A, Grosso A, Salassa F. Column generation for minimizing total completion time in a parallel-batching environment. Journal of Scheduling. 2021;24(6):569-588. doi:10.1007/s10951-021-00703-9
BibTeX
@article{Alfieri2021,
author = {Alfieri, A. and Druetto, A. and Grosso, A. and Salassa, F.},
title = {Column generation for minimizing total completion time in a parallel-batching environment},
journal = {Journal of Scheduling},
year = {2021},
volume = {24},
number = {6},
pages = {569--588},
doi = {10.1007/s10951-021-00703-9}
}
EUVIMED