Abstract

The dissertation discusses the problems of scheduling compatible jobs on parallel machines. Some jobs are incompatible, which is modeled as a binary relation on the set of jobs; the relation is often modeled by an incompatibility graph. We consider two models of machines. The first model, more emphasized in the thesis, is a classical model of scheduling, where each machine does one job at time. The second one is a model of p-batching machines, where a machine can do many jobs at once. Precisely, the jobs have to be grouped into batches and the batches assigned to machines. In the case of the first model, no two jobs that are incompatible can be scheduled on the same machine. In the case of the second one, no two jobs that are incompatible can be scheduled in the same batch. The work analyzes problems of the scheduling with respect to two criteria of optimality, maximum completion time among the jobs and total completion time of jobs. We analyze the problem with the following types of machines: identical, uniform and unrelated. We provide further results for makespan criterion, which is quite commonly considered in the setting of classical machines. More importantly, we provide results for many classes of graphs with respect to the total completion time criterion, which has not been considered in the literature before for the classical machines in the considered setting. In particular, we provide polynomial time algorithms for identical machines; and complete partite graphs or cluster graphs. Also, for complete partite graphs and uniform machines we apply the techniques of rounding, partial exhaustive search, and linear programming to obtain 4-approximate algorithm. The algorithm demonstrates that an application of the techniques to the problems with total completion time criteria is feasible. Finally, there is presented a study of the cost coloring problem, which has direct implications for uniform p-batching machines. Hence, we also briefly consider uniform p-batching machines and weighted total completion time criterion, which is a generalization of total completion time. The study starts with an overview of recent advances in the scheduling algorithms in the context of scheduling incompatible jobs. After the overview, the results presented are: polynomial time algorithms; approximate algorithms with constant approximation ratio; inapproximability results up to some constant, and up to arbitrary constant.

Author (1)