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