M.Sc Student | Kones Ishai |
---|---|

Subject | An EPTAS for Vector Assignment Problems over a Small Number of Machine Types |

Department | Department of Industrial Engineering and Management |

Supervisor | ASSOCIATE PROF. Asaf Levin |

Full Thesis text |

We
investigate a general class of vector scheduling problems over unrelated
machines, used for modelling problems such as processor scheduling and
transmitting video streams. In particular, each machine can be activated to one
of a subset of types associated with it. Activating a machine to a given type
incurs an activation cost and any activation of machines to types must obey a
bound on the total activation cost. When a job is scheduled to a machine of a
given type, it takes on a processing time vector unique to itself and the type.
For each machine we sum these processing time vectors to get a machine's work
vector. The machines each have a speed and dividing a machine's work vector by
its speed we get the machine's load vector. Then the objective of our problem
is to minimize a multidimensional function, which generalizes the l_{p}
norm and makespan, over these load vectors.

This problem (as well as many of its special cases) is strongly NP-hard and so neither an optimal solution nor a fully polynomial time approximation scheme can be given for it (assuming P is not equal to NP). Instead, we provide an efficient polynomial time approximation scheme. This scheme mainly relies on an approximate representation of the problem as a mixed integer linear program (MILP), with a constant number of integer variables, where each possible machine's configuration is assigned a variable. We develop a number of counting and rounding techniques to construct the MILP and transform its solution to a feasible near optimal solution to the original problem.