Scheduling jobs with fixed start and end times

AbstractWe analyze a scheduling problem in which each job has a fixed start and end time and a value. We describe an algorithm which maximizes the value of jobs completed by k identical machines. The algorithm runs in time O(n2 log n), where n is the number of jobs. We also show that the problem is NP-complete under the following restriction: Associated with each job is a subset of the machines on which it can be processed. For a fixed number of machines k, an O(nk+1) time algorithm is presented