In this paper, we present a new lower bound for the open-shop problem. In shop problems, a classical lower bound LB is the maximum of job durations and 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 problem 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 processing route of k, OSk boils down to subset-sum problems which can quickly be solved via dynamic programming. From this property, we define a branch-and-bound method for solving OSk which explores the possible processing routes of k. The resulting optimal makespan gives the desired bound for the initial 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 LB and improves it typically by 4%, which is remarkable for a shop problem known for its rather small gaps between LB and the optimal makespan. Moreover, the computational times on a PC are quite small on average. As a by-product 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 up to 30%.
