טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentGopalakrishna Jaykrishnan
SubjectEPTAS for Load Balancing Problem on Parallel Machines with
a Non-Renewable Resource
DepartmentDepartment of Industrial Engineering and Management
Supervisor ASSOCIATE PROF. Asaf Levin


Abstract

The problem considered is the non-preemeptive scheduling of ‘n’ independent jobs that consume a resource (which is non-renewable and replenished regularly) on ‘m’ parallel machines. The input defines the speed of machines, size of jobs, the quantity of resource required by the jobs, and the replenished quantities and replenishment dates of the resource. Every job can be processed only after the required quantity of the resource is allocated to the job. The objective function is the minimization of the convex combination of the makespan and an objective that is equivalent to the lp-norm of the vector of loads of the machines.

A polynomial time approximation scheme (PTAS) for a given problem is a family of approximation algorithms such that the family has a (1ε)-approximation algorithm for any ε>0. An efficient polynomial time approximation scheme (EPTAS) is a PTAS whose time complexity is upper bounded by the form f(1/ε) poly(n) where ‘f’ is some computable (not necessarily polynomial) function and poly(n) is a polynomial of the length of the (binary) encoding of the input. We establish the existence of an EPTAS for the problem. The EPTAS will first apply rounding steps to structure the input. We characterize structural properties of near optimal solutions and use it to formulate a Mixed-integer linear program (MILP) with a constant number of integer variables. Based on the optimal solution of this MILP, a feasible solution for the scheduling problem will be computed and we show that this solution approximates the optimal solution by a factor of (1 ε).