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

DOI10.1287/moor.18.1.12zbMath0779.90045OpenAlexW2044451514MaRDI QIDQ4697081

Marc E. Posner, Lu Lu

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

makespanworst-case complexitylinear time algorithmsaverage-case complexityrolling horizontwo machinesNP-hard open shop schedulingtwo distinct release datesweighted sum of machine completion times

Mathematics Subject Classification ID

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

Related Items (4)

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 ⋮ 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