טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentIshai Kones
SubjectAn EPTAS for Vector Assignment Problems over a Small
Number of Machine Types
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Levin Asaf
Full Thesis textFull thesis text - English Version


Abstract

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 lp 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.