A new lower bound for the open‐shop problem

C. Guéret and C. Prins

Annals of Operations Research, 1999, vol. 92, issue 0, 165-183

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

Date: 1999
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018930613891 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:92:y:1999:i:0:p:165-183:10.1023/a:1018930613891

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018930613891

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().