Approximating schedules

MaRDI QIDQ2711195zbMATH OpenFDO

Authors P. Schuurman

Publication date 6 May 2001

zbMATH Keywords

approximation algorithmsNP-completenessoptimal algorithmspipelined operator tree problempreemptive schedulingschedulingsingle-machine problem

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Deterministic scheduling theory in operations research (90B35)

Review text

This book is the Ph.D. thesis of the author. It is written quite well and can be used for a good introductory reading reference about scheduling, an important research topic in combinatorial optimization. The book consists of four parts.NEWLINENEWLINENEWLINEThe first part is an introduction, which contains some interesting examples in the real world, explaining the applications in various areas, such as transportations.NEWLINENEWLINENEWLINEThe second part contains positive results, that is, algorithms (optimal algorithms and approximation algorithms) found for various scheduling problems, including a single-machine problem, a pipelined operator tree problem, preemptive scheduling with job-dependent setup times, and scheduling with controllable processing times. Not all included algorithms belong to the work of the author. But, in each scheduling problem presented in this thesis, the author has a certain contribution. This is the main part of this thesis.NEWLINENEWLINENEWLINEThe third part contains negative results, including NP-completeness and non-approximability of some scheduling problems.NEWLINENEWLINENEWLINEFinally, some open problems are provided in the last part.NEWLINENEWLINENEWLINEOverall, this is really a nice piece of Ph. D work. It is an excellent reference for graduate students in computer science and operations research as well as applied mathematics.

Recommendations

• scientific article; zbMATH DE number 830382
• scientific article; zbMATH DE number 724323
• scientific article; zbMATH DE number 1167865
• Models and algorithms of time-dependent scheduling
• Polynomial time approximation algorithms for machine scheduling: Ten open problems

Cited in

(1)

• Optimal scheduling combinatorics

This page was built for publication: Approximating schedules

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