|20-CS-122-001||Computer Science II||Spring 2012|
|Hints For Homework Assignment 4|
Insert Jobs Into a Schedule
Insert Jobs into a schedule to meet deadlines:
The trick is to maintain a list of jobs, ordered in some way by
increasing deadline. The first thing to notice is that any job with a
deadline greater than the number of jobs (NumbJobs) can
always be scheduled to complete before its deadline, no matter what!
Hence, set any such jobs aside for the end. That means for now we
need only consider the jobs whose deadlines are no greater than
NumbJobs. Construct an array of NumbJobs pointers
to Jobs. Call the array schedule. Initialize all
elements of schedule to point to NULL. Let the
ith element of schedule represent the i+1st
time interval. Elements of schedule will be set to point to
jobs in such a way that a job (non-Null entry) pointed to by
schedule[i] always has a deadline greater than i.
This is done as follows: for each new job, with deadline d,
check schedule[d-1] to see whether it points to
NULL. If so, put the new job there, otherwise try
schedule[d-2], schedule[d-3], etc. until a
NULL is located and set a pointer to the new job there. If
no NULL position can be found down to schedule,
then that job cannot be added to the schedule without some previously
scheduled job being kicked past its deadline, so in that case, forget
the job. When done, output all the jobs that made it into schedule
plus the ones set aside earlier.
The following table shows the result of three implementations. The number of decisions is the total number of tests (if compares) and moves of objects within the schedule.
|This Idea||On File of 10000 Jobs||On File of 100000 Jobs|
|Sorted contiguous list||
|Insertion from deadline||
| Insertion from deadline &