Polynomial time approximation algorithms for machine scheduling: Ten open problems

DOI<203::AID-JOS26>3.0.CO;2-5 10.1002/(SICI)1099-1425(199909/10)2:5<203::AID-JOS26>3.0.CO;2-5zbMath0938.90032MaRDI QIDQ1806342

Petra Schuurman, Gerhard J. Woeginger

Publication date: 29 June 2000

Published in: Journal of Scheduling (Search for Journal in Brave)

zbMATH Keywords

scheduling problemsapproximation algorithmsopen problemsworst case analysisdeterministic machine scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Related Items (40)

Towards Tight Lower Bounds for Scheduling Problems ⋮ Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches ⋮ Unrelated Machine Scheduling with Stochastic Processing Times ⋮ Approximating total flow time on parallel machines ⋮ Reconstructing binary matrices with timetabling constraints ⋮ Partially ordered knapsack and applications to scheduling ⋮ Preemptive scheduling of independent jobs on identical parallel machines subject to migration delays ⋮ On the approximability of average completion time scheduling under precedence constraints. ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations ⋮ The \(C^{\max}\) problem of scheduling multiple groups of jobs on multiple processors at different speeds ⋮ Unnamed Item ⋮ Graph balancing: a special case of scheduling unrelated parallel machines ⋮ Approximating Single Machine Scheduling with Scenarios ⋮ Metaheuristics for order scheduling problem with unequal ready times ⋮ A Quasi-Polynomial Approximation for the Restricted Assignment Problem ⋮ Quasi-PTAS for scheduling with precedences using LP hierarchies ⋮ The feedback arc set problem with triangle inequality is a vertex cover problem ⋮ On the configuration-LP for scheduling on unrelated machines ⋮ Four decades of research on the open-shop scheduling problem to minimize the makespan ⋮ Approximability of average completion time scheduling on unrelated machines ⋮ Vertex Cover in Graphs with Locally Few Colors ⋮ Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree ⋮ Flow shops with WIP and value added costs ⋮ Designing PTASs for MIN-SUM scheduling problems ⋮ Parallel machine scheduling with nested job assignment restrictions ⋮ Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree ⋮ Minimizing flow time on a constant number of machines with preemption ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ Approximation schemes for scheduling and covering on unrelated machines ⋮ A note on graph balancing problems with restrictions ⋮ Scheduling jobs with release and delivery times subject to nested eligibility constraints ⋮ Single machine precedence constrained scheduling is a Vertex cover problem ⋮ Minimizing the total weighted completion time in a two-machine proportionate flow shop with different machine speeds ⋮ POLYNOMIAL APPROXIMATION SCHEMES FOR THE MAX-MIN ALLOCATION PROBLEM UNDER A GRADE OF SERVICE PROVISION ⋮ Online Linear Optimization for Job Scheduling Under Precedence Constraints ⋮ Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines ⋮ A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies ⋮ In memoriam: Gerhard Woeginger (1964--2022) ⋮ GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for scheduling unrelated parallel machines
• Multiprocessor scheduling with communication delays
• Efficient scheduling of tasks without full use of processor resources
• Permutation vs. non-permutation flow shop schedules
• Optimization, approximation, and complexity classes
• Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
• Three, four, five, six, or the complexity of scheduling with communication delays
• A min-sum 3/2-approximation algorithm for scheduling unrelated parallel machines
• Scheduling chain-structured tasks to minimize makespan and mean flow time
• Makespan minimization in job shops
• A PTAS for minimizing the weighted sum of job completion times on parallel machines
• Towards an Architecture-Independent Analysis of Parallel Algorithms
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• Scheduling the Open Shop to Minimize Mean Flow Time
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Open Shop Scheduling to Minimize Finish Time
• Complexity of Scheduling under Precedence Constraints
• Flowshop and Jobshop Schedules: Complexity and Approximation
• Worst Case Analysis of Two Scheduling Algorithms
• `` Strong NP-Completeness Results
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
• The Complexity of Flowshop and Jobshop Scheduling
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds
• Approximation Algorithms for Three-Machine Open Shop Scheduling
• Improved Approximation Algorithms for Shop Scheduling Problems
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Short Shop Schedules
• A Heuristic for a Scheduling Problem with Communication Delays
• Scheduling independent tasks to reduce mean finishing time
• The Two-Stage Assembly Scheduling Problem: Complexity and Approximation
• Bounds for Certain Multiprocessing Anomalies
• Optimal Sequencing of Two Equivalent Processors
• Technical Note—Minimizing Average Flow Time with Parallel Machines

This page was built for publication: Polynomial time approximation algorithms for machine scheduling: Ten open problems