EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Column generation for minimizing total completion time in a parallel-batching environment

A. Alfieri, A. Druetto, A. Grosso, F. Salassa

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →