A polynomial algorithm for an open shop problem with unit processing times and tree constraints

DOI10.1016/0166-218X(93)E0156-SzbMath0833.90066WikidataQ57634009 ScholiaQ57634009MaRDI QIDQ1804876

Heidemarie Bräsel, Dagmar Kluge, Frank Werner

Publication date: 17 May 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(93)e0156-s

zbMATH Keywords

polynomial algorithm; unit processing times; open shop problem; tree constraints

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C60: Abstract computational complexity for mathematical programming problems

90B35: Deterministic scheduling theory in operations research

Related Items

Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity, The representation of partially-concurrent open shop problems, Open shop problems with unit time operations

Cites Work

• Openshop and flowshop scheduling to minimize sum of completion times
• A polynomial algorithm for the \([n/m/0,\;t_{ij}=1,\text{ tree}/C_{\max}\) open shop problem]
• Scheduling with Deadlines and Loss Functions
• Scheduling Open Shops with Unit Execution Times to Minimize Functions of Due Dates
• Unit Execution Time Shop Problems
• Open shop problems with unit time operations
• Unnamed Item
• Unnamed Item