Skip to content

Departmental Seminar: Daniel R. Page

Tuesday, 23rd May 2017 1:00 pm
Where: EITC E2-165

Title: Approximation Algorithms for Scheduling Unrelated Parallel Machines
Consider the following parallel machine scheduling problem. Let m and n be the number of parallel machines and jobs, respectively. In addition, if job j is scheduled on machine i, job j takes p_{i,j} time units on machine i. Given n jobs, the goal is to schedule each job on a parallel machine non-preemptively so that the schedule containing all n jobs has minimum makespan. This is a classic NP-hard problem in Scheduling Theory called the makespan minimization problem on unrelated parallel machines, commonly abbreviated as R||C_{max}. Currently the best approximation algorithms for R||C_{max} have approximation ratio 2. Despite over 25 years of being intensively studied in the literature, finding an approximation algorithm with approximation ratio better than 2 for R||C_{max} still remains an open problem. In response, researchers have focused on NP-hard special cases of R||C_{max} that share the same inapproximability bounds in the hopes to better understand the problem and provide approximation algorithms with improved approximation ratios. Two such problems are the graph balancing problem and the restricted assignment problem. In this talk we discuss recent developments in our research for these two problems, with a focus on when the parallel machines are uniform i.e. every parallel machine has a speed.
Complete Seminar List
© 2011 University of Manitoba Department of Computer Science
Back to top