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

DOI10.1016/0166-218X(93)E0156-SzbMath0833.90066OpenAlexW2003459360WikidataQ57634009 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 algorithmunit processing timesopen shop problemtree constraints

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• 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