Polynomial time approximation algorithms for machine scheduling: Ten open problems
type: Item
instance of: scholarly article
title: Polynomial time approximation algorithms for machine scheduling: Ten open problems
zbMATH Open document ID: 0938.90032
author: P. Schuurman
author: Gerhard J. Woeginger
published in: Journal of Scheduling
publication date: 2000-06-29T00:00:00Z
review text: From the authors' prologue: In the early days of scheduling, the work of the theoretical research branch mainly consisted of classifying scheduling problems into easy (i.e. polynomially solvable) and hard (i.e. NP-hard) ones. Nowadays, researchers have become interested in a better understanding and a much finer classification of the hard problems; one very active branch of research classifies hard scheduling problems according to their approximability. The authors summarize and discuss what in their opinion are the most outstanding open questions in the approximation of scheduling problems. All scheduling problems discussed are minimization problems, where the goal is to find a feasible schedule with minimum possible cost. They consider only scheduling problems that are NP-hard and distinguish between positive results, which establish the existence of some approximation algorithm, and negative results, which disprove the existence of certain approximation results under the assumption \(P\neq NP\). 69 references are listed.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90-02
zbMATH DE Number: 1356647
zbMATH Keywords: deterministic machine scheduling
zbMATH Keywords: worst case analysis
zbMATH Keywords: approximation algorithms
zbMATH Keywords: open problems
zbMATH Keywords: scheduling problems
MaRDI profile type: Publication
cites work: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
cites work: `` Strong '' NP-Completeness Results
cites work: Optimization, approximation, and complexity classes
cites work: Bounds for Certain Multiprocessing Anomalies
cites work: Complexity of Scheduling under Precedence Constraints
cites work: Scheduling chain-structured tasks to minimize makespan and mean flow time
cites work: Optimal Sequencing of Two Equivalent Processors
cites work: Worst Case Analysis of Two Scheduling Algorithms
cites work: Efficient scheduling of tasks without full use of processor resources
cites work: Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds
cites work: Q3840373
cites work: Towards an Architecture-Independent Analysis of Parallel Algorithms
cites work: Multiprocessor scheduling with communication delays
cites work: Three, four, five, six, or the complexity of scheduling with communication delays
cites work: A Heuristic for a Scheduling Problem with Communication Delays
cites work: Approximation algorithms for scheduling unrelated parallel machines
cites work: Exact and Approximate Algorithms for Scheduling Nonidentical Processors
cites work: A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
cites work: Short Shop Schedules
cites work: Approximation Algorithms for Three-Machine Open Shop Scheduling
cites work: Open Shop Scheduling to Minimize Finish Time
cites work: The Complexity of Flowshop and Jobshop Scheduling
cites work: Improved Approximation Algorithms for Shop Scheduling Problems
cites work: Q5501839
cites work: Q4542585
cites work: Permutation vs. non-permutation flow shop schedules
cites work: Makespan minimization in job shops: a polynomial time approximation scheme
cites work: Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
cites work: The Two-Stage Assembly Scheduling Problem: Complexity and Approximation
cites work: A PTAS for minimizing the weighted sum of job completion times on parallel machines
cites work: A min-sum 3/2-approximation algorithm for scheduling unrelated parallel machines
cites work: Q4252432
cites work: Q4938773
cites work: Q3840371
cites work: On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
cites work: Q4252365
cites work: Technical Note—Minimizing Average Flow Time with Parallel Machines
cites work: Scheduling independent tasks to reduce mean finishing time
cites work: Flowshop and Jobshop Schedules: Complexity and Approximation
cites work: Scheduling the Open Shop to Minimize Mean Flow Time
cites work: Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
cites work: Q4252385
cites work: Q4526964
cites work: Q3840372
cites work: Q4228496
cites work: Q4526975
cites work: Q4250192
DOI: 10.1002/(SICI)1099-1425(199909/10)2:5%3C203::AID-JOS26%3E3.0.CO;2-5
description: scientific article; zbMATH DE number 1356647