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 decisions236 seconds Insertion from deadline 9052321 decisions0.18 seconds 938647458 decisions7.12 seconds Insertion from deadline &       path compression 73478 decisions0.19 seconds 1124499 decisions1.78 seconds