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

Abstract 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.