The following is the schedule of upcoming department seminars. Seminars will be added to the schedule throughout the year. All seminars are free of charge and are open to all members, affiliates, and colleagues of the university community. Seminars are typically held on Tuesday or Thursday at 1:00 pm. If you would like additional information or if you might be interested in presenting a seminar, please contact Helen Cameron or the Department of Computer Science.

Departmental Seminar: Daniel R. Page
When: May 23, 2017 @ 1:00pm
Where: EITC E2165Title: Approximation Algorithms for Scheduling Unrelated Parallel Machines.Abstract: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 nonpreemptively so that the schedule containing all n jobs has minimum makespan. This is a classic NPhard problem in Scheduling Theory called the makespan minimization problem on unrelated parallel machines, commonly abbreviated as RC_{max}. Currently the best approximation algorithms for RC_{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 RC_{max} still remains an open problem. In response, researchers have focused on NPhard special cases of RC_{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.