Scheduling jobs with fixed start and end times (Q1098765)

We 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(n^ 2 \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(n^{k+1})\) time algorithm is presented.