Single-machine bicriteria scheduling. (English) Zbl 0749.90042

Eindhoven: Techn. Univ. 158 p. (1992).
This is in fact a collection of seven papers coauthored by the author. Two introductory sections give an overview of the complexity issues arising in the context of single machine scheduling when two of the scheduling criteria are combined. Then, seven papers are given. Their contents is as follows.
The first paper deals with the problem of simultaneous minimization of maximum earliness and lateness. Polynomial time algorithms are presented for some variants of the problem. In the second paper polynomial time algorithms are given for the minimization of mean flow time combined with maximum lateness, maximum earliness and an arbitrary maximum cost function, respectively. The third paper is concerned with the bicriteria scheduling problem when two arbitrary maximum cost criteria are combined. Again, a polynomial time algorithm is presented. In the fourth paper a new lower bound for single machine multicriteria scheduling problems with a linear composite objective function is presented. The fifth and the sixth paper analyze the problem of scheduling tasks subject to a minimum value of total absolute deviation from a common due date. In the seventh paper a branch-and-bound algorithm is proposed for a problem when a combination of total weighted flow time and total weighted earliness is to be minimized.


90B35 Deterministic scheduling theory in operations research