Scheduling tasks with preemptions and precedence constraints on identical parallel machines to minimise the maximum lateness
- Publication Type:
- Issue Date:
This work examines in depth a collection of related scheduling problems. The problems considered all relate to the processing of tasks on machines over time, with the goal of minimising some function of the tasks’ completion times. The tasks being scheduled are subject to preemptions, that is they may be interrupted during their processing and resumed later on the same or a different set of machines. The tasks are subject to precedence constraints, meaning some tasks cannot be processed until others have been completed. The machines on which the tasks are processed are identical, meaning they have the same speed and functionality, and parallel, in contrast to scheduling models where tasks must be processed on multiple machines sequentially. This is a thoroughly investigated area of research in the literature. Due to the computational complexity of the problems considered, approximation algorithms for these problems are presented and are analysed in several ways. Several well known results are expanded to apply to more general scheduling problems, and a completely new class of results is described. In particular, the solvable cases of some approximation algorithms – i.e. the situations under which the algorithms provide an optimal solution to the considered problem – are examined in more detail than heretofore. Bounds on the worst case of the considered algorithms are also presented, as are results regarding the computational complexity of certain subproblems. The goal of this work is to advance the understanding of this focused but significant area of research, and present a wide variety of results relating to it.
Please use this identifier to cite or link to this item: