Short Shop Schedules
From MaRDI portal
Publication:4367253
DOI10.1287/OPRE.45.2.288zbMATH Open0890.90112DBLPjournals/ior/WilliamsonHHHLS97OpenAlexW2007315235WikidataQ56390715 ScholiaQ56390715MaRDI QIDQ4367253FDOQ4367253
Authors: David P. Williamson, Leslie A. Hall, Han Hoogeveen, David B. Shmoys, Cor Hurkens, Jan Karel Lenstra, Sergey Sevastyanov 
Publication date: 6 July 1998
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/ebb732b940099aa8eb9866c9b4c3e20093b695b4
Recommendations
- The complexity of shop-scheduling problems with two or three jobs
- Combinations of some shop scheduling problems and the shortest path problem: complexity and approximation algorithms
- A complete 4-parametric complexity classification of short shop scheduling problems
- Hardness of approximating flow and job shop scheduling problems
Cited In (81)
- Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph
- Irreducible bin packing and normality in routing open shop
- Combinations of some shop scheduling problems and the shortest path problem: complexity and approximation algorithms
- Combinatorial approximation algorithms: a comparative review
- A PTAS for the Multiple Parallel Identical Multi-stage Flow-Shops to Minimize the Makespan
- A complexity analysis and algorithms for two-machine shop scheduling problems under linear constraints
- Open block scheduling in optical communication networks
- Performance analysis of rotation schedule and improved strategy for open shop problem to minimise makespan
- Experimental comparison of heuristics for flow shop scheduling
- Two-machine routing open shop on a tree: instance reduction and efficiently solvable subclass
- Complete Complexity Classification of Short Shop Scheduling
- Moderate worst-case complexity bounds for the permutation flowshop scheduling problem using inclusion-exclusion
- A Markov chain on the solution space of edge colorings of bipartite graphs
- A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops
- A polynomial-time approximation scheme for an arbitrary number of parallel identical multi-stage flow-shops
- Approximation algorithms for two-machine proportionate routing open shop on a tree
- Polynomial time approximation algorithms for machine scheduling: Ten open problems
- On the drift of short schedules.
- A polynomial-time approximation scheme for an arbitrary number of parallel two-stage flow-shops
- Bounding the running time of algorithms for scheduling and packing problems
- A worst-case analysis of the three-machine flow shop scheduling
- An approximation scheme for minimizing the makespan of the parallel identical multi-stage flow-shops
- Grouping techniques for scheduling problems: simpler and faster
- Performance guarantees for flowshop heuristics to minimize makespan
- Two-stage open-shop scheduling with a two-machine flow shop as a stage: approximation algorithms and empirical experiments
- The convergence of stochastic algorithms solving flow shop scheduling
- How good is a dense shop schedule?
- A polynomial-time algorithm for the preemptive mixed-shop problem with two unit operations per job
- Open-shop scheduling for unit jobs under precedence constraints
- Parameterized complexity of machine scheduling: 15 open problems
- Approximation schemes for scheduling jobs with chain precedence constraints
- APPROXIMATION ALGORITHMS FOR FLEXIBLE JOB SHOP PROBLEMS
- Hybrid rollout approaches for the job shop scheduling problem
- Two-machine open shop scheduling with an availability constraint
- Polynomial time approximation algorithms for proportionate open-shop scheduling
- Title not available (Why is that?)
- A linear time approximation scheme for makespan minimization in an open shop with release dates
- An extended Akers graphical method with a biased random‐key genetic algorithm for job‐shop scheduling
- Shop scheduling problems with pliable jobs
- Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches
- Chromatic scheduling in a cyclic open shop
- Four decades of research on the open-shop scheduling problem to minimize the makespan
- A heuristic for the two-machine open-shop scheduling problem with transportation times
- Linear time approximation scheme for the multiprocessor open shop problem
- Approximation results for the two-machine job shop under limited machine availability
- Inapproximability results for no-wait job shop scheduling.
- Title not available (Why is that?)
- \(O(\log m)\)-approximation for the routing open shop problem
- The open shop scheduling problem
- A study on several combination problems of classic shop scheduling and shortest path
- Makespan minimization in open shops: A polynomial time approximation scheme
- A PTAS for a particular case of the two-machine flow shop with limited machine availability
- Three-machine open shop with a bottleneck machine revisited
- A complete 4-parametric complexity classification of short shop scheduling problems
- Minimizing maximum completion time in a proportionate flow shop with one machine of different speed
- On a routing open shop problem on two nodes with unit processing times
- Linear programming-based algorithms for the minimum makespan high multiplicity jobshop problem
- Scheduling problems for parallel dedicated machines under multiple resource constraints.
- Deterministic job-shop scheduling: Past, present and future
- Approximability of flow shop scheduling
- Open-shop dense schedules: properties and worst-case performance ratio
- Dense open-shop schedules with release times
- A genetic algorithm for the proportionate multiprocessor open shop
- Scheduling jobshops with some identical or similar jobs
- Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop
- An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times
- On some properties of optimal schedules in the job shop problem with preemption and an arbitrary regular criterion
- Fast parallel heuristics for the job shop scheduling problem
- Two-stage open shop scheduling with a bottleneck machine
- Approximation algorithms for the multiprocessor open shop scheduling problem
- Worst-case analysis of heuristics for open shops with parallel machines
- An FPTAS for the parallel two-stage flowshop problem
- Exponential tightness for integral-type functionals of centered independent differently distributed random variables
- A fluid approach to large volume job shop scheduling
- A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem
- Approximation schemes for job shop scheduling problems with controllable processing times
- Heuristics for the two-stage job shop scheduling problem with a bottleneck machine
- A hybrid genetic algorithm for the job shop scheduling problem
- Better approximation guarantees for job-shop scheduling
- Hardness of approximating flow and job shop scheduling problems
- A new algorithm for the two-machine open shop and the polynomial solvability of a scheduling problem with routing
Uses Software
This page was built for publication: Short Shop Schedules
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4367253)
