선형으로 감소하는 준비시간을 갖는 작업들의단일설비 일정계획

This study considers single machine scheduling problems for jobs with linear decreasing setup times, where the setup times decrease according to either the total amount of processing or setups already. Even though many studies have taken the learning effect into account, very few studies have reported the scheduling problems with the learning effect on the setup times. This work presents new problems with the learning effect on the setup times to minimize the makespan, mean flow time, or total absolute differences in completion times (TADC). We derive the range of possible values of the learning constant and characterize the optimal schedules of the problems. We show that the problems with makespan or TADC are solvable in time. For the mean flow time, this research develops an algorithm with time complexity when the learning results from the total amount of the processing time of jobs already processed. We suggest another algorithm using the assignment problem model for the mean flow time with learning according to the sum of existing setup times. We demonstrate that our algorithms are useful for environments with learning effects on setup times by using numerical examples.