Makespan minimization in open shops: A polynomial time approximation scheme
From MaRDI portal
Publication:1290641
DOI10.1007/BF01585871zbMath0920.90075MaRDI QIDQ1290641
Gerhard J. Woeginger, Sergey Sevast'janov
Publication date: 3 June 1999
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)
Related Items (40)
A PTAS for non-resumable open shop scheduling with an availability constraint ⋮ Rectangle packing with one-dimensional resource augmentation ⋮ Some positive news on the proportionate open shop problem ⋮ The three-machine proportionate open shop and mixed shop minimum makespan problems ⋮ Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches ⋮ Open shop scheduling problem with a non-resumable flexible maintenance period ⋮ A study on several combination problems of classic shop scheduling and shortest path ⋮ Combinations of Some Shop Scheduling Problems and the Shortest Path Problem: Complexity and Approximation Algorithms ⋮ Makespan minimization in preemptive two machine job shops ⋮ A fluid approach to large volume job shop scheduling ⋮ The Open Shop Scheduling Problem ⋮ A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops ⋮ A complexity analysis and algorithms for two-machine shop scheduling problems under linear constraints ⋮ Open-shop dense schedules: properties and worst-case performance ratio ⋮ Approximability of two-machine no-wait flowshop scheduling with availability constraints. ⋮ Approximating a two-machine flow shop scheduling under discrete scenario uncertainty ⋮ 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 ⋮ A tabu search approach for proportionate multiprocessor open shop scheduling ⋮ Metaheuristics for order scheduling problem with unequal ready times ⋮ Grouping techniques for scheduling problems: simpler and faster ⋮ Four decades of research on the open-shop scheduling problem to minimize the makespan ⋮ Irreducible bin packing and normality in routing open shop ⋮ Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms ⋮ Approximation Algorithms for Generalized Path Scheduling ⋮ Approximation results for flow shop scheduling problems with machine availability constraints ⋮ Inapproximability results for no-wait job shop scheduling. ⋮ 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 ⋮ A genetic algorithm for the proportionate multiprocessor open shop ⋮ Open-shop scheduling for unit jobs under precedence constraints ⋮ Three-machine open shop with a bottleneck machine revisited ⋮ Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop ⋮ Polynomial time approximation algorithms for proportionate open‐shop scheduling ⋮ Moderate exponential-time algorithms for scheduling problems ⋮ Approximation algorithms for the multiprocessor open shop scheduling problem ⋮ Two-stage open shop scheduling with a bottleneck machine ⋮ A linear time approximation scheme for makespan minimization in an open shop with release dates ⋮ Scheduling parallel dedicated machines under a single non-shared resource
Cites Work
This page was built for publication: Makespan minimization in open shops: A polynomial time approximation scheme
