Single Machine Scheduling Problems with Actual Time-dependent Learning and Deterioration Effects

This paper considers single machine scheduling problems with learning and deterioration effects on setup and processing times of the jobs. In these problems, the setup and processing times vary according to both the total amount of actual setups and processing finished already. The learning effect leads to a decrease in the actual setup and processing times for a job, whereas the deterioration effect results in an increase in the actual setup and processing times. We present a learning and deterioration model with four parameters to represent various environments. Our objective is to find the optimal schedules that minimize the makespan or the sum of completion times for the model. Through the utilization of a pairwise interchange method, we develop the optimal scheduling rule to minimize the makespan. In the cases of the sum of completion time measure, this study characterizes the optimal schedules and derives three rules as special cases. As the paper employs four parameters to address special cases, the resulting rules are applicable across diverse environments depending on the parameter values. Moreover, all these rules are efficient because they have polynomial time-complexity, regardless of the presence of learning or deterioration effects.