Single Machine Scheduling under Predictive Disruption with Linear Deteriorating Jobs

摘要

This paper considers single machine scheduling problems under predictive disruption with linear deteriorating jobs. In this model, machine has an availability constraint and the actual processing time of a job is an increasing linear function of its starting time. We assume that an optimal schedule can be obtained by using some algorithm if machine is available at all time. Because of the machine disruption the original schedule may become infeasible or too far from optimal. We want to create a new schedule that takes into account both the original objective function and a measure of deviation from the original schedule. We consider the problem in which the objective is weighted sum of total weighted completion time and total weighted tardiness. We first prove some properties of the optimal schedule then a dynamic programming algorithm is proposed.