M.Sc Student | Presburger Ron |
---|---|

Subject | PTAS for Minimizing Weighted Completion Time on a Hierarchical Set Of Machines |

Department | Department of Industrial Engineering and Management |

Supervisor | Professor Asaf Levin |

Full Thesis text |

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.