On the continuous working problem

Abstract In this paper, we are given a set J ={ J 1 , J 2 ,…, J n } of jobs and a set M ={ M 1 , M 2 ,…, M m } of men. Each man M i can only execute a nonempty subset S i of jobs and ∪m i=1 S i =J . Each job takes one unit of time to execute. We now further assume that no man can work indefinitely without any rest. That is, each man, after working for a certain period, will have to take a rest for a while. There are a maximum working time, w i , and a minimum resting time, r i , for man M i ,1≤ i ≤ m . M i can continuously work for at most w i time units. Our problem is: Can we assign jobs to men in such a way that at any time instance there exists at least one man working. Furthermore, if such a schedule does exist, we want all of the jobs to be finished in the shortest time. We shall call this problem the continuous working problem. This problem occurs in a military environment where we want to schedule cannons to destroy targets. In the first part of this paper, we prove that even to determine whether a feasible schedule exists is NP-complete. The computational complexities of some special cases for determining whether a feasible schedule exists are also considered. In the second part, an algorithm based on the concept of A ∗ is presented to find a minimum makespan feasible schedule. This algorithm returns an optimal schedule as soon as the tree searching hits a leave node. Experimental results show that although the continuous working problem is NP-complete, it can still be solved by the A ∗ algorithm approach with polynomial average case performance.