M.Sc Student | Mordechai Yael |
---|---|

Subject | Optimization and Reoptimization in Scheduling Problems |

Department | Department of Computer Science |

Supervisor | Professor Hadas Shachnai |

Full Thesis text |

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.