scientific article; zbMATH DE number 3850790

From MaRDI portal
Publication:3320091





This monograph is devoted to one of the central problems in deterministic sequencing theory: a number of jobs with given processing times, weights, and precedence constraints, have to be scheduled on a single machine such that the total weighted completion time is minimized. The author first reviews the previous work on this problem: polynomial- time algorithms for certain special cases, NP-hardness results for other (more general) special cases, fast approximation algorithms (mostly priority rules followed by local improvements), and enumerative optimization methods (dynamic programming and branch-and-bound). Next, he proposes a new integer programming formulation of the problem. For the associated linear program, a specialized version of the simplex method is given that exploits the structure of the coefficient matrix. A heuristic is developed which can be viewed as a modification of subgradient optimization; the approach seems to be applicable to other problems in combinatorial optimization. A report on computational experiments concludes this useful and well-written monograph. The reader who is confused by the bilingual title of this book should know that it is written in German and has an informative thirteen-page abstract in English.




Cited in
(23)








This page was built for publication:

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