The Taub Faculty of Computer Science Events and Talks

Parallel machine scheduling has been extensively studied in the past decades, with applications ranging from production planning to job processing in large computing clusters. We study some of these fundamental optimization problems, as well as their reoptimization variants. In this talk, we present improved bounds for job scheduling on unrelated parallel machines, with the objective of minimizing the latest completion time (or, makespan) of the schedule. We consider the subclass of fully-feasible instances, in which the processing time of each job, on any machine, does not exceed the minimum makespan. The problem is known to be hard to approximate within factor 4/3 already in this subclass. Although fully-feasible instances are hard to identify, we give a polynomial time algorithm that yields for such instances a schedule whose makespan is better than twice the optimal, the best known ratio for general instances. Moreover, we show that our result is robust under small violations of feasibility constraints. We further study the power of parameterization and show that makespan minimization on unrelated parallel machines admits a parameterized approximation scheme, where the parameter used is the number of processing times that are large relative to the latest completion time of the schedule.