Scheduling ordered open shops
From MaRDI portal
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.
Recommendations
Cites work
- A new polynomial-time algorithm for linear programming
- A Note on Open Shop Preemptive Schedules
- An Algorithm for the Open-Shop Problem
- scientific article; zbMATH DE number 3644821 (Why is no real title available?)
- Minimizing Maximum Lateness in a Two-Machine Open Shop
- On the complexity of preemptive open-shop scheduling problems
- Open Shop Scheduling to Minimize Finish Time
- Open-shop scheduling problems with dominated machines
- Openshop and flowshop scheduling to minimize sum of completion times
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Preemptive Scheduling of Independent Jobs with Release and Due Times on Open, Flow and Job Shops
- Scheduling Open Shops with Unit Execution Times to Minimize Functions of Due Dates
- Scheduling the Open Shop to Minimize Mean Flow Time
- Unit Execution Time Shop Problems
Cited in
(27)- Lot streaming in open shops
- On the complexity of preemptive openshop scheduling problems
- Open shop scheduling with maximal machines
- An efficient tabu search approach for the two-machine preemptive open shop scheduling problem.
- Flow shop and open shop scheduling with a critical machine and two operations per job
- Scheduling two-machine preemptive open shops to minimize total completion time
- Exponential tightness for integral-type functionals of centered independent differently distributed random variables
- 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
- Approximation algorithms for the three-machine proportionate mixed shop scheduling
- Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop
- Some positive news on the proportionate open shop problem
- Characteristics of machine order matrix of open shop scheduling problems
- The two-machine no-wait general and proportionate open shop makespan problem
- Two-machine open shop scheduling with secondary criteria
- The three-machine proportionate open shop and mixed shop minimum makespan problems
- The open shop scheduling problem
- scientific article; zbMATH DE number 3860868 (Why is no real title available?)
- Nonpreemptive open shop with restricted processing times
- Minimization of open orders: application of a re-distribution coordination policy
- OSGA: genetic-based open-shop scheduling with consideration of machine maintenance in small and medium enterprises
- Proportionate flow shop: new complexity results and models with due date assignment
- The LPT heuristic for minimizing total load on a proportionate openshop
- Approximation algorithms for two-machine proportionate routing open shop on a tree
- On the open-shop problem with preemption and minimizing the average completion time
- Scheduling preemptive open shops to minimize total tardiness
- A multi-level genetic algorithm for a multi-stage space allocation problem
This page was built for publication: Scheduling ordered open shops
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q580167)
