Scheduling a maintenance activity to minimize total weighted completion-time

作者：Mosheiov Gur^*; Sarig Assaf

来源：Computers & Mathematics with Applications, 2009, 57(4): 619-623.

DOI：10.1016/j.camwa.2008.11.008

• Scheduling
• Single machine
• Weighted completion time
• Maintenance activity
• Dynamic programming
• Heuristics

We study a single machine scheduling problem, The processor needs to go through a maintenance activity, which has to be completed prior to a given deadline. The objective function is minimum total weighted completion time. The problem is proved to be NP-hard, and an introduction of a pseudo-polynomial dynamic programming algorithm indicates that it is NP-hard in the ordinary sense. We also present an efficient heuristic, which is shown numerically to perform well.

• 出版日期2009-2