Interval scheduling

Several possible greedy strategies for solving Interval Scheduling . Three in particular are:

1. Choose jobs in order of starting time s(i). Earliest jobs are scheduled first.

2. Choose jobs in order of duration time d(i). Shortest jobs are scheduled first.

3. Choose jobs in order of finishing time f(i). Earliest finishing jobs are scheduled first.

[login to view URL] must implement one additional greedy algorithm, which is to sort the intervals by number

of conflicts, and to choose jobs with fewer conflicts first

You need to program these 4 strategies, run each 1000 times on random data, and

report the results. Here are specific instructions on how to program:

1. Create a “job” object with attributes start, finish, and duration.

2. Create an array of 1000 jobs.

3. For each job, use a random number generator to give it a start time between 1 and

9500. Use a random number generator to give each job a duration between 10 and 500.

Determine the finish time of each job by adding start to duration.

4. Write 4 methods to implement the 4 job selection strategies discussed above.

Because you are writing 4 methods that do the same thing, the best programming

practice would be to write an interface and then implement it for the 4 strategies. It is ok to use a library method tosort your job arrays.

5. Your final program should create a job array, run the EarliestStartTimeFirst,

EarliestFinishTimeFirst and ShortestDurationFirst methods and record the resulting

number of jobs scheduled for each method. For accurate comparisons, make sure that

all 3 methods are being run on the same job array! Run this 1000 times, keeping track of

the highest, mean, and lowest values for each interval scheduling strategy.

After running your program, you must report the [login to view URL] is

what your report should contain:

1. A short introduction stating the problem and your approach to solving/programming it.

2. The table of results, as shown in step 5 above.

3. A section discussing your interpretation of the results. This discussion should include:

a. Based on what you know, how should the numbers look? For example, should

certain numbers be larger than other numbers? Should best and average be the

same in some cases? Any expectations discussed here MUST be based on facts

that you know about the algorithms. If you don’t know facts about the

algorithms, Google the algorithms and find some. Be sure to state the source of

any facts. (K&T page 649 contains an interesting fact that might be useful here.)

b. How do your values confirm what you expected in part (a)? Do your values differ

from what you expected? In both cases, why?

c. Based on your results, is one of the 3 methods superior? Is one of the methods

clearly in second place?

4. As an appendix, include your code.

Also, submit your code separately as a zipped file.

Java

Project ID: #25906910

About the project