دانلود رایگان مقاله برنامه ریزی موازی با فعالیت های تعمیر و نگهداری

Abstract

This paper considers a problem of scheduling on parallel machines where each machine requires maintenance activity once over a given time window. The objective is to find a coordinated schedule for jobs and maintenance activities to minimize the scheduling cost represented by either one of several objective measures including makespan, (weighted) sum of completion times, maximum lateness and sum of lateness. The problem is proved to be NP-hard in the strong sense in each case of the objective measures. Some restricted cases of the problem are also characterized for their complexities, for which the associated dynamic programming algorithms are derived.

6. Conclusion

This paper considers the problem of scheduling on parallel machines, where each machine requires maintenance activity once during a given time window. In the problem presented here, two different maintenance activities are considered, including the independent case and the dependent case. The first one allows more than one machine to be under maintenance activity simultaneously, if necessary The second one allows only one machine to be under maintenance activity at any time point. Thus, the complexities of various parallel machine problems are characterized with each of the two maintenance activities considered for various scheduling measures. Moreover, some restricted cases of the proposed problem are also characterized for their complexities, for which the associated DP algorithms are derived.