Scheduling Jobs On A Single Machine Subject To Breakdowns

The jobs are subject to melioration, which are expressed as linear decrement of the processing requirements. The machine is subject to preemptive-resume break-downs with exponentially distributed uptimes and downtimes. It has been well known in the classical models that the expectation and variance of the makespan of meliorations jobs can be minimized analytically by an index policy if no machine breakdowns are involved. Such basic features, however, change dramatically when breakdowns and deteriorations are presented together. In this paper, we derive the characteristics of the time that a job occupies the machine. We further find that the expected makespan can still be minimized by a simple index policy that is in-dependent of the breakdown process, but this is no longer the case for the variance of the makespan.