دانلود رایگان مقاله مسائل زمان بندی تک ماشین با تاثیر پیری ماشین و فعالیت تعمیر اختیاری

ABSTRACT

This paper considers two single-machine scheduling problems with a new type of aging effect, which is dominated by the processing speed of the machine. During the whole scheduling horizon, the machine is subject to an optional maintenance, and the duration of the maintenance depends on the length of the uptime before it. The objective is to schedule all jobs and find the location of the maintenance so as to minimize the makespan or the total completion times. The two problems are proved to be NP-complete, and two dynamic programming algorithms are proposed to solve the problems. We analyze the computation complexity of the algorithms, and show that the problems under study are solvable in polynomial time if the processing loads of all jobs are uniformly bounded.

5. Conclusions

This paper investigates single-machine scheduling problems with both aging effect, which is dominated by the processing speed of the machine, and deteriorating maintenance activities. We consider the model where the processing speed of the machine is a decreasing function of its uninterrupted running time. In addition, we assume the machine is subject to at most one maintenance activity during the scheduling horizon, and the maintenance duration is a general function of its start time. The objective is to find jointly the optimal location of the maintenance operation and the optimal job sequence to minimize the makespan and the total completion times. We prove the two problems under study are both NP-complete, and each of them has an optimal sequence subject to S-S rule. Taking the total completion times minimization problem as an example, we devise two DP algorithms to solve the problem with an optimal sequence subject to S-S rule. Furthermore, we analyze the computation complexity of the two algorithms, and show that the problem can be solved in polynomial time if the normal processing times of all jobs are uniformly bounded.