Approximating schedules (Q2711195)

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.