M.Sc Student | Shusterman Tal |
---|---|

Subject | Weighted Throughput in a Single Machine preemptive Scheduling with Continuous Controllable Processing Times |

Department | Department of Industrial Engineering and Management |

Supervisor | Professor Asaf Levin |

Full Thesis text |

We consider the problem of weighted throughput in the single machine preemptive scheduling with continuous controllable processing times. A set of n tasks are to be scheduled on a single machine. Each task is associated with a non negative weight w_j, a release date, a due date, and an interval (a segment over the real line) of possible processing times. All the parameters are assumed to be non negative integers. A task can either be scheduled with a total processing time which is in the given interval, or rejected (not participating in the schedule). At most one task can be processed on the machine at each given time. The processing of a task can be preempted, that is, to be interrupted and resumed later. The reward for processing task j for a total of p_j time units (where p_j belongs to the range of possible processing times) is w_j*p_j and we are interested in constructing a feasible preemptive schedule such that the sum of rewards is maximized. First, we show that there exists an integral optimal solution for the described problem. Next, we present a dynamic programming algorithm that solves the problem in pseudo-polynomial time. Then, we propose an efficient frontier approach for improved complexity bounds.