Scheduling ordered open shops (Q580167): Difference between revisions

This paper examines special cases of the open shop problem in an attempt to define the boundary between easy and apparently hard, i.e. NP- complete, problems. The top result is: the minimizing makespan in an ordered three-machine open shop is NP-complete. This implies that many other open shop problems are also NP-complete. However, the authors show that a slight change in the assumptions of the problem may render a difficult problem easy to solve.

0 references

reviewed by

V.Peteanu

0 references

zbMATH Keywords

open shop

0 references

makespan

0 references

NP-complete

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/0305-0548(87)90029-3

0 references

cites work

Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

0 references

Open Shop Scheduling to Minimize Finish Time

0 references

Scheduling the Open Shop to Minimize Mean Flow Time

0 references

Open-shop scheduling problems with dominated machines

0 references

Openshop and flowshop scheduling to minimize sum of completion times

0 references

Unit Execution Time Shop Problems

0 references

Scheduling Open Shops with Unit Execution Times to Minimize Functions of Due Dates

0 references

An Algorithm for the Open-Shop Problem

0 references

On the complexity of preemptive open-shop scheduling problems

0 references

Minimizing Maximum Lateness in a Two-Machine Open Shop

0 references

A Note on Open Shop Preemptive Schedules

0 references

Preemptive Scheduling of Independent Jobs with Release and Due Times on Open, Flow and Job Shops

0 references

A new polynomial-time algorithm for linear programming

0 references

Q3050157

0 references

Identifiers

zbMATH Open document ID

0625.90045

0 references

DOI

10.1016/0305-0548(87)90029-3

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:580167

@@ Property / author @@
-Q580166
@@ Property / author: Q580166 / rank @@
-Normal rank
@@ Property / author @@
+Robert L. Bulfin
@@ Property / author: Robert L. Bulfin / rank @@
+Normal rank
@@ Property / review text @@
+This paper examines special cases of the open shop problem in an attempt to define the boundary between easy and apparently hard, i.e. NP- complete, problems. The top result is: the minimizing makespan in an ordered three-machine open shop is NP-complete. This implies that many other open shop problems are also NP-complete.    However, the authors show that a slight change in the assumptions of the problem may render a difficult problem easy to solve.
+Normal rank
@@ Property / reviewed by @@
+V.Peteanu
@@ Property / reviewed by: V.Peteanu / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+B35
@@ Property / Mathematics Subject Classification ID: 90B35 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q25
@@ Property / Mathematics Subject Classification ID: 68Q25 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+4016583
@@ Property / zbMATH DE Number: 4016583 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+open shop
@@ Property / zbMATH Keywords: open shop / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+makespan
@@ Property / zbMATH Keywords: makespan / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+NP-complete
@@ Property / zbMATH Keywords: NP-complete / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0305-0548(87)90029-3
+Normal rank
@@ Property / OpenAlex ID @@
+W2040889502
@@ Property / OpenAlex ID: W2040889502 / rank @@
+Normal rank
@@ Property / cites work @@
+Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
+Normal rank
@@ Property / cites work @@
+Open Shop Scheduling to Minimize Finish Time
@@ Property / cites work: Open Shop Scheduling to Minimize Finish Time / rank @@
+Normal rank
@@ Property / cites work @@
+Scheduling the Open Shop to Minimize Mean Flow Time
+Normal rank
@@ Property / cites work @@
+Open-shop scheduling problems with dominated machines
+Normal rank
@@ Property / cites work @@
+Openshop and flowshop scheduling to minimize sum of completion times
+Normal rank
@@ Property / cites work @@
+Unit Execution Time Shop Problems
@@ Property / cites work: Unit Execution Time Shop Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Scheduling Open Shops with Unit Execution Times to Minimize Functions of Due Dates
+Normal rank
@@ Property / cites work @@
+An Algorithm for the Open-Shop Problem
@@ Property / cites work: An Algorithm for the Open-Shop Problem / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of preemptive open-shop scheduling problems
+Normal rank
@@ Property / cites work @@
+Minimizing Maximum Lateness in a Two-Machine Open Shop
+Normal rank
@@ Property / cites work @@
+A Note on Open Shop Preemptive Schedules
@@ Property / cites work: A Note on Open Shop Preemptive Schedules / rank @@
+Normal rank
@@ Property / cites work @@
+Preemptive Scheduling of Independent Jobs with Release and Due Times on Open, Flow and Job Shops
+Normal rank
@@ Property / cites work @@
+A new polynomial-time algorithm for linear programming
+Normal rank
@@ Property / cites work @@
+Q3050157
@@ Property / cites work: Q3050157 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:580167