Analysis of Algorithms : An Active Learning Approach

8.4 TESTING POSSIBLE SOLUTIONS 227

ate in polynomial time. This section will look at algorithms that check pro-
posed solutions for the job scheduling and graph coloring problems.

■ 8.4.1 Job Scheduling
You will recall that the job scheduling problem gives a set of jobs that need to
be done. Each job has a time it takes to complete, a deadline by which it must
be completed, and a penalty if that job is not completed in time. Jobs are done
one at a time, and the deadlines are measured from the start of the first job. The
jobs are specified as a 4-tuple (n,t,d,p) where n is the job number, t is the
amount of time it will take, d is the deadline, and p is the penalty. For example,
a set of five jobs could be {(1, 3, 5, 2), (2, 5, 7, 4), (3, 1, 5, 3), (4, 6, 9, 1),
(5, 2, 7, 4)}.
The decision problem specifies some value P and wants to know if there is
an ordering of the jobs that can be done with penalty less than or equal to P.
The optimization problem wants to know the smallest penalty for any ordering
of the jobs. We will consider the decision problem, because calling the decision
problem with a series of values until it answers yes can solve the optimization
problem. In other words, we ask if there is an order with penalty 0 and if it
answers no, we try a penalty of 1. We keep increasing the penalty until we get
an answer of yes. The following algorithm will test one potential solution for
the decision version of the problem:
PenaltyLess( list, N, limit )
list the ordering of the jobs
N the number of jobs
limit the maximum penalty

currentTime = 0
currentPenalty = 0
currentJob = 1
while (currentJob ≤ N) and (currentPenalty ≤ limit) do
currentTime = currentTime + list[currentJob].time
if (list[currentJob].deadline < currentTime) then
currentPenalty = currentPenalty +
list[currentJob].penalty
end if
currentJob = currentJob + 1
end while

if currentPenalty ≤ limit then