| A Dynamic Programming Algorithm for the Single Machine Total (2001) | |||||||||||||||||
Abstract | |||||||||||||||||
| In this paper, we study the single machine total completion scheduling problem subject to a period of maintenance. The problem is known to be NP-hard. We propose a pseudo-polynomial dynamic programming algorithm for the problem with time complexity O(nR), where n refers to the number of jobs and R to the date of the beginning of the maintenance. The efficiency of the algorithm is improved using a fixation of variables technique. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||