A new lower bound for the open‐shop problem

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 machineloads. Contrary tothe flow‐shop and job‐shop problems, the open‐shop lacks tighter bounds.For the generalopen‐shop problem OS, we propose an improved bound defined as theoptimal makespan ofa relaxed open‐shop problem OS k . In OS k , the tasks of any job may be simultaneous, except for a selected job k. We prove the NP-hardness of OS k .However, for a fixed processingroute of k, OS k boils down to subset‐sumproblems which can quickly be solved via dynamicprogramming. From this property, we define a branch‐and‐bound method for solvingOS k which explores the possible processing routes of k. The resultingoptimal makespan givesthe desired bound for the initial problem OS. We evaluate the method ondifficult instancescreated by a special random generator, in which all job durations and all machine loads areequal to a given constant. Our new lower bound is at least as good as LBand improves ittypically by 4%, which is remarkable for a shop problem known for its rather small gapsbetween LB and the optimal makespan. Moreover, the computational timeson a PC arequite small on average. As a by‐product of the study, we determined and propose to theresearch community a set of very hard open‐shop instances, for which the new boundimproves LB by up to 30%. Copyright Kluwer Academic Publishers 1999