The simulations performed by the Simulator class all start with a fixed number of processors and create a schedule for a collection of tasks. A schedule specifies the processor to which each task is assigned, and the starting time of that task on that processor. Each processor may work on only one task at any time step (or tick, in Weiss's terminology). Tasks may not be interrupted and resumed later. You will be considering two types of simulations -- one in which all of the tasks are known in advance, and another in which tasks arrive at unpredictable times.

The Simulator class is to have a constructor that takes the number of processors in the simulation as its only argument. This class is also to have two public methods to create schedules as specified below. For extra credit you will be asked below to define a third such method.

The first of these two methods is to be called simulate. It is to take two LinkedLists as arguments -- the first representing a list of Tasks and the second representing a sequence of Integer arrival times of the tasks. You may assume that the arrival times are in strictly increasing order. In particular, you may assume that no two tasks arrive in the same time step. If the two input lists are of different sizes, ignore the extra values in the longer list. The method should return an instance of the Schedule class.

Your simulation should use the second (preferred) implementation of Section 6.4.2 of Weiss. When a task arrives, you should assign it to an available processor (i.e., a processor without a task) if one exists, or if a processor becomes available at the current time step. You should assign to the processor that has been waiting the longest. If no processor is or becomes available, you should add the task to a set of waiting tasks. When a processor becomes available (corresponding to a departure event in Section 6.4.2), the waiting task that takes the longest amount of time should be scheduled for that processor. Your simulation may terminate when all tasks have been scheduled -- you needn't simulate the execution of any tasks after this time.

The second method is to be called createSchedule. It is to take a LinkedList of Tasks, consider them in nonincreasing order of the time they take, and schedule them in that order to the processor that has the earliest available starting time. Ties are to be broken by assigning to the lowest-numbered processor. Note that if a task requires t time steps, then assigning that task to processor p means that processor p's earliest available starting time has increased by t time steps. In particular, no processor's schedule should have any gaps in it -- the time when each processor finishes with its tasks should be simply the sum of all of the times required by all of its tasks. For example, if the tasks have time requirements 9, 8, 7, 6, 5, 4, and 3, and the processors are numbered 0, 1, and 2, then the tasks would be assigned to processors 0, 1, 2, 2, 1, 0, and 0 respectively. Note that this schedule requires a final completion time of 9 + 4 + 3 = 16, but that other schedules exist which achieve the theoretically optimal completion time of (9 + 8 + 7 + 6 + 5 + 4 + 3)/3 = 14. The method should return an instance of the Schedule class.

It is very important to documentation the algorithms and data structures used in these two methods (and in the extra credit if you do it), since there are so many possibilities in each case.

The Task class is to have a 2-argument constructor that takes an integer identification number and an integer representing the number of time steps needed for its completion. You should redefine the Object.toString() method for this class. You may want to have the class implement the Comparable interface. Since tasks may not be scheduled until well after their creation, you may want a mutator that sets a task's starting time.

The Schedule class is to have its own toString method whose return value shows for each processor the tasks assigned to that processor (with the task id numbers, the time they started processing, and the processing time they require). It should also show the time when each processor finished its last task. The class will of course need enough constructors and methods to support the gathering of this information. The precise design of the class, and of its interaction with other classes, is up to you. You should follow good software practices -- for example you should be careful with methods that return collections of mutable values. Finally, note that the use of newline characters like \n is not platform independent. I recommend the use of the string returned by System.getProperty("line.separator") to separate lines.

The BinaryHeap class may have any or all of the methods of the Weiss text. For his insert method, you may simply throw an Overflow exception. You needn't worry about extending the capacity of the heap. Note that the maximum sizes of the appropriate binary heaps are known for each type of simulation that you will be performing in this assignment. If you initialize these heaps to have an appropriate capacity in your Simulator methods, you may squelch any Overflow exceptions that arise.

You may use code from Chapter 6 of Weiss or from my posted solutions for earlier semesters. As always, you should give credit for any code that you did not write.

As in the previous assignments, you needn't try to handle ClassCastExceptions that result from comparing incomparable elements.

Test your classes with the class A3, available on the class web site.

If you do the extra credit, you should uncomment out the test cases in the main method of the class A3.

There is a maximum of 30 points of extra credit for this class. Since students who have taken the pretest have already received 30 points, they will receive no credit for doing the extra credit portion of this assignment (which may not even be graded for them).