20-CS-122-001 Computer Science II Spring 2012
Hints For Homework Assignment 4

Virtual functions, classes, inheritance, lists, queues, stacks, applications

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[0], 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    
51362876 decisions
.49 seconds
5147458604 decisions
236 seconds
   Insertion from deadline    
9052321 decisions
0.18 seconds
938647458 decisions
7.12 seconds
   Insertion from deadline &    
   path compression   
73478 decisions
0.19 seconds
1124499 decisions
1.78 seconds