An NP-Hard Open Shop Scheduling Problem with Polynomial Average Time Complexity

DOI10.1287/MOOR.18.1.12MaRDI QIDQ4697081zbMATH OpenOpenAlexFDO

Authors Lu Lu, Marc E. Posner

Publication date 29 June 1993

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/moor.18.1.12

zbMATH Keywords

average-case complexitylinear time algorithmsmakespanNP-hard open shop schedulingrolling horizontwo distinct release datestwo machinesweighted sum of machine completion timesworst-case complexity

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• A Note On The Complexity Of Openshop Scheduling Problems
• The open shop scheduling problem with a given sequence of jobs on one machine
• Open shop problem with zero-one time operations and integer release date/deadline intervals
• Minimizing Mean Flow Time in Two-Machine Open Shops and Flow Shops
• The complexity of shop-scheduling problems with two or three jobs

Cited in

(7)

• A polynomial algorithm for the \([n/m/0,\;t_{ij}=1,\text{ tree}/C_{\max}]\) open shop problem
• A polynomial-time open-shop problem with an arbitrary number of machines
• A PTAS for non-resumable open shop scheduling with an availability constraint
• Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches
• Four decades of research on the open-shop scheduling problem to minimize the makespan
• NP-hardness of compact scheduling in simplified open and flow shops.
• Two-machine open shop scheduling with an availability constraint

This page was built for publication: An NP-Hard Open Shop Scheduling Problem with Polynomial Average Time Complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4697081)