Approximability of flow shop scheduling
From MaRDI portal
Publication:1290640
DOI10.1007/BF01585870zbMath0920.90073OpenAlexW2075846649MaRDI QIDQ1290640
Publication date: 3 June 1999
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01585870
Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)
Related Items
Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph ⋮ 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 best possible on-line algorithm for two-machine flow shop scheduling to minimize makespan ⋮ Complexity of problem \(TF2|v=1,c=2|C_{\max}\) ⋮ Optimal control of a two-server flow-shop network ⋮ A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops ⋮ Time-flexible min completion time variance in a single machine by quadratic programming ⋮ Optimal results and numerical simulations for flow shop scheduling problems ⋮ A heuristic algorithm for the hospital health examination scheduling problem ⋮ Flow shop scheduling problems with transportation constraints revisited ⋮ Flow shop scheduling problems with transportation constraints revisited ⋮ Preemptive scheduling on two identical parallel machines with a single transporter ⋮ A complexity analysis and algorithms for two-machine shop scheduling problems under linear constraints ⋮ Approximating a two-machine flow shop scheduling under discrete scenario uncertainty ⋮ Grouping techniques for scheduling problems: simpler and faster ⋮ A PTAS for the Multiple Parallel Identical Multi-stage Flow-Shops to Minimize the Makespan ⋮ An FPTAS for the parallel two-stage flowshop problem ⋮ Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms ⋮ Approximation Algorithms for Generalized Path Scheduling ⋮ Flowshop problem \(F2 \to D|v=1\), \(c\geq 1|C_{\max}\) revisited ⋮ Maximizing Throughput in Flow Shop Real-Time Scheduling ⋮ Inapproximability results for no-wait job shop scheduling. ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ Transporting jobs through a two‐machine open shop ⋮ Heuristic factory planning algorithm for advanced planning and scheduling ⋮ An empirical analysis of the optimality rate of flow shop heuristics ⋮ A linear time approximation algorithm for permutation flow shop scheduling ⋮ Heuristics for the two-stage job shop scheduling problem with a bottleneck machine ⋮ A polynomial-time approximation scheme for an arbitrary number of parallel two-stage flow-shops ⋮ Performance guarantees for flowshop heuristics to minimize makespan ⋮ Moderate exponential-time algorithms for scheduling problems ⋮ A linear time approximation scheme for makespan minimization in an open shop with release dates ⋮ A combination of flow shop scheduling and the shortest path problem ⋮ Complexity and algorithms for two-stage flexible flowshop scheduling with availability constraints
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for scheduling unrelated parallel machines
- Analysis of a linear programming heuristic for scheduling unrelated parallel machines
- Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
- Optimal two- and three-stage production schedules with setup times included
- Bounding algorithm for the routing problem with arbitrary paths and alternative servers
- PERFORMANCE ANALYSIS OF SIX APPROXIMATION ALGORITHMS FOR THE ONE-MACHINE MAXIMUM LATENESS SCHEDULING PROBLEM WITH READY TIMES
- Jackson's Rule for Single-Machine Scheduling: Making a Good Heuristic Better
- Open Shop Scheduling to Minimize Finish Time
- The Complexity of Flowshop and Jobshop Scheduling
- Improved Approximation Algorithms for Shop Scheduling Problems
- Short Shop Schedules
- Chernoff–Hoeffding Bounds for Applications with Limited Independence
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Fixed-Parameter Tractability and Completeness I: Basic Results
