#### Degree

Doctor of Philosophy

#### Program

Computer Science

#### Supervisor

Solis-Oba, Roberto

#### Abstract

A fundamental problem in scheduling is makespan minimization on unrelated parallel machines (R||C_{max}). Let there be a set J of jobs and a set M of parallel machines, where every job J_{j} ∈ J has processing time or length p_{i,j} ∈ ℚ^{+} on machine M_{i} ∈ M. The goal in R||C_{max} is to schedule the jobs non-preemptively on the machines so as to minimize the length of the schedule, the makespan. A ρ-approximation algorithm produces in polynomial time a feasible solution such that its objective value is within a multiplicative factor ρ of the optimum, where ρ is called its approximation ratio. The best-known approximation algorithms for R||C_{max} have approximation ratio 2, but there is no ρ-approximation algorithm with ρ < 3/2 for R||C_{max} unless P=NP. A longstanding open problem in approximation algorithms is to reconcile this hardness gap. We take a two-pronged approach to learn more about the hardness gap of R||C_{max}: (1) find approximation algorithms for special cases of R||C_{max} whose approximation ratios are tight (unless P=NP); (2) identify special cases of R||C_{max} that have the same 3/2-hardness bound of R||C_{max}, but where the approximation barrier of 2 can be broken.

This thesis is divided into four parts. The first two parts investigate a special case of R||C_{max} called the graph balancing problem when every job has one of two lengths and the machines may have one of two speeds. First, we present 3/2-approximation algorithms for the graph balancing problem with one speed and two job lengths. In the second part of this thesis we give an approximation algorithm for the graph balancing problem with two speeds and two job lengths with approximation ratio (√65+7)/8 ≈ 1.88278. In the third part of the thesis we present approximation algorithms and hardness of approximation results for two problems called R||C_{max} with simple job-intersection structure and R||C_{max} with bounded job assignments. We conclude this thesis by presenting algorithmic and computational complexity results for a generalization of R||C_{max} where J is partitioned into sets called bags, and it must be that no two jobs belonging to the same bag are scheduled on the same machine.

#### Recommended Citation

Page, Daniel R., "Approximation Algorithms for Problems in Makespan Minimization on Unrelated Parallel Machines" (2019). *Electronic Thesis and Dissertation Repository*. 6109.

https://ir.lib.uwo.ca/etd/6109