A new lower bound for the open-shop problem

In this paper, we present a new lower bound for the open-shop problem. In s hop problems, a classical lower bound LB is the maximum of job durations an d machine loads. Contrary to the flow-shop and job-shop problems, the open- shop lacks tighter bounds. For the general open-shop problem OS, we propose an improved bound defined as the optimal makespan of a relaxed open-shop p roblem OSk. In OSk, the tasks of any job may be simultaneous, except for a selected job k. We prove the NP-hardness of OSk. However, for a fixed proce ssing route of k, OSk boils down to subset-sum problems which can quickly b e solved via dynamic programming. From this property, we define a branch-an d-bound method for solving OSk which explores the possible processing route s of k. The resulting optimal makespan gives the desired bound for the init ial problem OS. We evaluate the method on difficult instances created by a special random generator, in which all job durations and all machine loads are equal to a given constant. Our new lower bound is at least as good as L B and improves it typically by 4%, which is remarkable for a shop problem k nown for its rather small gaps between LB and the optimal makespan. Moreove r, the computational times on a PC are quite small on average. As a by-prod uct of the study, we determined and propose to the research community a set of very hard open-shop instances, for which the new bound improves LB by u p to 30%.