Discrete Mathematics and Combinatorics Commons^™

Approximation Algorithms For Problems In Makespan Minimization On Unrelated Parallel Machines, Daniel R. Page

Electronic Thesis and Dissertation Repository

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 …