An Optimal Single-Machine Scheduling with Linear Deterioration Rate and Rate-Modifying Activities

摘要

This paper considers a single-machine scheduling with linear deterioration rate of processing speed and multiple rate-modifying activities simultaneously. A rate-modifying activity can change the processing rate of machine under consideration, which means after each rate-modifying activity the speed of the machine is fully recovered. The integration of these two concept is motivated by human operators and semi-automatic systems that experience performance degradation over time and require rate-modifying activities for recovery. The objective is to minimize the makespan. We need to decide the sequence of jobs and when to schedule the rate-modifying activities. An optimal schedule is proposed, which can solve the problem in O(n log n) time where n is the number of jobs.