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

DOI10.1016/0166-218X(93)E0156-SzbMATH Open0833.90066OpenAlexW2003459360WikidataQ57634009 ScholiaQ57634009MaRDI QIDQ1804876FDOQ1804876

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

Recommendations

• A polynomial algorithm for the \([n/m/0,\;t_{ij}=1,\text{ tree}/C_{\max}]\) open shop problem
• Polynomial time algorithms for special open shop problems with precedence constraints and unit processing times
• [[:Publication:4822050|Title not available (Why is that?)]]
• [[:Publication:4882996|Title not available (Why is that?)]]
• A polynomial algorithm for \(P | p_j = 1,r_j, outtree\,| \sum C_j\)

zbMATH Keywords

polynomial algorithmunit processing timesopen shop problemtree constraints

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

• A polynomial algorithm for the \([n/m/0,\;t_{ij}=1,\text{ tree}/C_{\max}]\) open shop problem
• Title not available (Why is that?)
• A polynomial-time open-shop problem with an arbitrary number of machines
• Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
• Open shop problems with unit time operations
• Polynomial time algorithms for special open shop problems with precedence constraints and unit processing times
• The representation of partially-concurrent open shop problems

This page was built for publication: A polynomial algorithm for an open shop problem with unit processing times and tree constraints

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