ON A SCHEDULING PROBLEM WHERE A JOB CAN BE EXECUTED ONLY BY A LIMITED NUMBER OF PROCESSORS

In this paper we consider a job scheduling problem where each job can be executed only by a subset of available processors. This problem arises when we are scheduling a set of cannons to be fired on a set of targets. Each cannon can destroy only a subset of targets and we want the targets to be destroyed in the shortest possible time. We define what is meant by a balanced solution. We then consider three problems: How can we detect that there is a balanced solution? If this solution exists, find such a solution. If no such solution exists, find an optimal assignment which minimizes the makespan. We show that there are polynomial time algorithms to solve these problems.