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.
Emde, Simon, Lysgaard, Jens. Branch-cut-and-price for open-shop scheduling problems with any regular minsum objective. // Journal of Scheduling. – 2026. – DOI: 10.1007/s10951-026-00874-3. – URL: http://link.springer.com/openurl/fulltext?id=doi:10.1007/s10951-026-00874-3
Emde, Simon, Lysgaard, & Jens (2026). Branch-cut-and-price for open-shop scheduling problems with any regular minsum objective. Journal of Scheduling. https://doi.org/10.1007/s10951-026-00874-3
Emde, et al. “Branch-cut-and-price for open-shop scheduling problems with any regular minsum objective.” Journal of Scheduling, 2026. doi:10.1007/s10951-026-00874-3.
@article{Emde2026,
title = {Branch-cut-and-price for open-shop scheduling problems with any regular minsum objective},
author = {Emde and Simon and Lysgaard and Jens},
journal = {Journal of Scheduling},
year = {2026},
doi = {10.1007/s10951-026-00874-3},
url = {http://link.springer.com/openurl/fulltext?id=doi:10.1007/s10951-026-00874-3}
}
In this paper, we consider cost-sharing problems defined on rooted trees. We refer to these problems as cost-tree problems and to the induced transferable utility cooperative games as irrigation games. We introduce a formal notion of...
In this paper, we focus on nonlinear programming problems with cardinality constraints that restrict the number of nonzero components of the decision vector. We start with a straightforward mixed-integer programming reformulation....
Portfolio selection is a critical issue in financial management under uncertainty. In this paper, we propose a complex approach for portfolio selection with quantile return approximation. In particular, we propose a practical workflow...
The transcendental logarithmic (translog) production function is recognised as a flexible functional form for modelling production processes. It accommodates varying elasticities of input substitution and diverse types of...
This study investigates mothership-drone route determination using two optimization approaches: a Mixed Integer Linear Programming (MILP) model based on a discrete hexagonal grid, and a Mixed Integer Nonlinear Programming (MINLP) model...