טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentPresburger Ron
SubjectPTAS for Minimizing Weighted Completion Time on a
Hierarchical Set Of Machines
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Asaf Levin
Full Thesis textFull thesis text - English Version


Abstract

Consider the following scheduling problem, where we need to schedule n jobs on a hierarchical set of m parallel machines, so as to minimize the weighted sum of job completion times. This problem generalizes the problem on identical machines and as such it is NP-hard in the strong sense. We present a PTAS for this problem, which to our knowledge is the first known PTAS for this problem. We do so by using techniques from previous related works, mainly geometric rounding of the jobs' weight to processing time ratios (which we later refer to as job ratios). This allows us to limit the number of different jobs, such that the number of types is independent of the input, and with a limited damage to the optimal objective function value. We then solve the problem via a dynamic programming approach.