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

DOI10.1016/0166-218X(93)E0156-SMaRDI QIDQ1804876zbMATH OpenOpenAlexWikidataFDO

Authors 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) Deterministic scheduling theory in operations research (90B35) Abstract computational complexity for mathematical programming problems (90C60)

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
• scientific article; zbMATH DE number 2109433
• scientific article; zbMATH DE number 894721
• A polynomial algorithm for \(P | p_j = 1,r_j, outtree\,| \sum C_j\)

Cites work

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

Cited in

(7)

• Open shop problems with unit time operations
• Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
• 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
• Polynomial time algorithms for special open shop problems with precedence constraints and unit processing times
• scientific article; zbMATH DE number 2109433 (Why is no real title available?)
• 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)