EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Branch-cut-and-price for open-shop scheduling problems with any regular minsum objective

Simon Emde, Jens Lysgaard

Journal of Scheduling · 2026-08 · 29 (4) · 279-298

DOI: 10.1007/s10951-026-00874-3 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Scheduling, online erschienen am 22.05.2026. Verfasst von Simon Emde und 1 weiteren Autor:innen. Die Arbeit nennt 52 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Friedrich-Schiller-Universität Jena.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

This paper deals with a general open-shop scheduling problem where jobs have release and due dates, transferring between machines incurs a machine–pair-dependent delay, and any regular objective defined over job completion times is minimized. Such problems are widely encountered in practice, e.g., in industrial testing and maintenance processes and just-in-time logistics. Despite its relevance, exact solution methods from the literature have so far focused on the makespan objective or very specific special cases. We hence present the first exact method for the general open-shop scheduling problem with any regular minsum objective with respect to job completion times. Moreover, we demonstrate how branch-cut-and-price methods can be applied to the open shop. Finally, we also adapt the famous subset-row inequalities, originally proposed for the vehicle routing problem, to the open shop. Our computational study on both newly generated instances as well as those from the literature demonstrates good performance on a broad set of different objective functions, finding tight bounds even for the largest problems.

Förderung

  • Friedrich-Schiller-Universität Jena

Zitieren

APA

Emde, S., & Lysgaard, J. (2026). Branch-cut-and-price for open-shop scheduling problems with any regular minsum objective. Journal of Scheduling, 29(4), 279-298. https://doi.org/10.1007/s10951-026-00874-3

Vancouver

Emde S, Lysgaard J. Branch-cut-and-price for open-shop scheduling problems with any regular minsum objective. Journal of Scheduling. 2026;29(4):279-298. doi:10.1007/s10951-026-00874-3

BibTeX
@article{Emde2026,
  author = {Emde, Simon and Lysgaard, Jens},
  title = {Branch-cut-and-price for open-shop scheduling problems with any regular minsum objective},
  journal = {Journal of Scheduling},
  year = {2026},
  volume = {29},
  number = {4},
  pages = {279--298},
  doi = {10.1007/s10951-026-00874-3}
}
Kostenlos starten →