Technical Report MSC-2015-22

Title: Optimization and Reoptimization in Scheduling Problems
Authors: Yael Mordechai
Supervisors: Hadas Shachnai
PDFCurrently accessibly only within the Technion network
Abstract: Parallel machine scheduling has been extensively studied in the past decades, with applications ranging from production planning to job processing in large computing clusters. In this work we study some of these fundamental optimization problems, as well as their parameterized and reoptimization variants.

We first 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. In a parameterized optimization problem, each input comes with a fixed parameter. Some problems can be solved by algorithms (or approximation algorithms) that are exponential only in the size of the parameter, while polynomial in the input size. The problem is then called fixed parameter tractable (FPT), since it can be solved efficiently (by an FPT algorithm or approximation algorithm) for constant parameter values. We show that makespan minimization on unrelated machines admits a parameterized approximation scheme, where the parameter is the number of processing times that are large relative to the latest completion time of the schedule. We also present an FPT algorithm for the graph-balancing problem, which corresponds to instances of the restricted assignment problem where each job can be processed on at most two machines.

Finally, motivated by practical scenarios, we initiate the study of reoptimization in job scheduling on identical and uniform machines, with the objective of minimizing the makespan. In this model, we are given an initial schedule of jobs on the machines. The goal is to obtain a schedule that minimizes the makespan, while using the optimal transition cost from the initial schedule. We develop reapproximation algorithms that yield, for both identical and uniform machines, the best possible approximation ratio of (1+Ɛ) to the minimum makespan, for any Ɛ>0

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2015
To the main CS technical reports page

Computer science department, Technion