Jill Recla, a student in data structures, requested "I wish I had a program that would write an essay for me. I also wish I had a program that would complete my chemistry assignment, but I think that's beyond the scope of this course.” We probably could add a data structures programming assignment to the students list of tasks to perform. The student is correct that this programming assignment can not write the assignments, but we could write a utility that could help by organizing the homework and scheduling them.
For this programming assignment you are to write a scheduler for tasks, which will input tasks and output a schedule for performing the tasks.
A Task will have three attributes:
· description – a quoted string describing the task
· duration – an integer representing the expected time, in days, to perform the task
· dueDate – an integer representing the due date of the assignment, in days from zero hour.
The HWScheduler will perform two functions:
· addTask description duration dueDate – which adds a task, as described above, for scheduling.
· printScdedule – which prints a schedule for working on the tasks.
Examples:
addTask “Data Structure Programming Assignment” 5 10
addTask “World Cultures Essay” 6 11
addTask “Chemistry Assignment” 2 12
printSchedule
So the Data Structure assignment is expected to take 5 hours and is due in the 10 th hour from hour zero, the World Cultures Essay is expected to take 6 hours and is due in the 11 th hour, and Chemistry Assignment is expected to take 2 hours and is due the 12 th hour. The studious student will notice that not all assignments can be performed by the due dates. Nevertheless we will attempt to schedule as many assignments as possible.
Output of print Schedule could be:
1 Data Structure Programming Assignment
2 Data Structure Programming Assignment
3 Data Structure Programming Assignment
4 Data Structure Programming Assignment
5 Data Structure Programming Assignment
6 Chemistry Assignment
7 Chemistry Assignment
which specifies what assignment to do on a particular day. Note that this schedule maximizes the number of assignments completed on time and minimizes the amount of time you have to work on assignments.
To solve this problem we need to make some assumptions, we will assume that all tasks have equal value and we wish to maximize the number tasks we can perform on time, while minimizing the time we have to work on the homework. Clearly, the best greedy approach is to consider the shortest tasks first for scheduling, this should maximize the number tasks performs. This suggests a greedy algorithm:
algorithm List schedule(Sequence tasks)
// input is a Sequence of task with duration and due date
// returns a list of task in sequence,
// which maximizes the number of task performed on time
make PriorityQueue Q of tasks keyed by duration
make empty Sequence schedule
while Q is not empty do
Task task = Q.removeMin()
int location = schedule.add(task)
if not feasible(schedule) then schedule.remove(location)
return schedule
Note that if schedule is viewed as an array then the rank of sequence can represent the days that a task is performed. The function, feasible, returns a Boolean specifying if all the tasks can be performed on time. How much does not the algorithm cost? Depends on how you implement the priority queue and the function feasible. The algorithm would be very expensive if feasible checked every possible ordering, or permutation, of the tasks in feasible. If n is the size of schedule then the cost would be O(n*n!) worst then exponential! We should not check every permutation. Fortunately a theorem can come to the rescue.
A schedule is feasible if and only if the schedule ordered by increasing due dates is feasible.
The proof of a schedule is feasible if the schedule ordered by increasing due dates is feasible is obvious.
We move on to the more interesting side of the equivalence, a schedule is feasible only if the schedule ordered by increasing due dates is feasible, and prove by showing that any schedule, which feasible, then the same list of tasks ordered by due dates is feasible. Without lost of generality assume that task t1 is scheduled before task t2, but t1.dueDate > t2.dueDate. Because schedule is feasible then the last rank that that t2 is scheduled for is less then equal to t1.dueDate, so we could switch the two tasks by shifting any intermediate tasks and the ordered schedule is feasible.
The theorem tells us two things; we only need to check one permutation, and the permutation we should check. Which permutation is that, and how much does feasible cost?
To receive a 100% on this program you should explain the details of your algorithm, include how you add the new task to schedule and how you determine if the schedule is feasible. In addition you should give the cost of each operation and the total cost for printSchedule.
After you have debugged your program putting all the classes in a single file called HomeWorkScheduler.java. Have fun scheduling your homework and remember to make sure your program compiles.