Polynomial time approximation algorithms for machine scheduling: Ten open problems

DOI10.1002/(SICI)1099-1425(199909/10)2:5%3C203::AID-JOS26%3E3.0.CO;2-5zbMATH Open0938.90032MaRDI QIDQ1806342FDOQ1806342

Gerhard J. Woeginger, P. Schuurman

Publication date: 29 June 2000

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

Recommendations

• scientific article; zbMATH DE number 2156264
• scientific article; zbMATH DE number 1820024
• scientific article
• Non-approximability results for scheduling problems with minsum criteria
• scientific article; zbMATH DE number 3873052

zbMATH Keywords

approximation algorithmsworst case analysisopen problemsscheduling problemsdeterministic 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)

Cites Work

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

Cited In (52)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1806342)