טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentShusterman Tal
SubjectWeighted Throughput in a Single Machine preemptive
Scheduling with Continuous Controllable
Processing Times
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Asaf Levin
Full Thesis textFull thesis text - English Version


Abstract

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.