Machine scheduling and Lagrangian relaxation. (English) Zbl 0728.90046

Amsterdam: CWI; Eindhoven: Tech Univ. Eindhoven, Thesis. 139 p. (1991).
This thesis describes how Lagrangean relaxation can be used to generate exact and approximate solutions to a variety of machine scheduling problems. A special feature is that an ascent method is proposed to tackle each Lagrangean dual problem.
The first chapter gives an introduction to machine scheduling problems and provides a thorough review of Lagrangean duality theory. The problem of scheduling jobs with precedence constraints on a single machine to minimize total weighted completion time is considered in the second chapter. Based on a Lagrangean relaxation of the precedence constraints, the problem is decomposed: an approximate solution of the original problem is obtained by solving each subproblem by dynamic programming. In each of the next three chapters, the lower bounds obtained from dual ascent procedures are incorporated into branch and bound algorithms for which extensive computational tests are performed. The third chapter deals with the problem of minimizing total completion time in a two- machine flow-shop; the precedence constraints between the operations of the jobs are dualized. The fourth chapter considers the problem of scheduling unrelated parallel machines to minimize the maximum completion time; the constraints which ensure that the maximum completion time cannot be less than the completion time of the last job on any machine are dualized. The fifth chapter studies the problem of scheduling jobs with a common due date on a single machine to minimize the total earliness plus the total tardiness; the constraint which ensures that the total processing of non-late jobs cannot exceed the due date is dualized. Finally, the problem of scheduling a single machine to minimize weighted total completion time plus weighted total earliness is considered in the sixth chapter. Various lower bounds are derived and tested in a branch and bound algorithm.


90B35 Deterministic scheduling theory in operations research
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C39 Dynamic programming