Question

1. Suppose you are given a set S = {a1,a2,···,an} of tasks, where task ai requires pi units of processing time to complete, once it has started. You have one computer on which to run these tasks, and the computer can run only one task at a time. Let ci be the completion time of task ai, that is, the time at which task ai completes processing. Your goal is to minimize the average completion time, that is, to minimize n1 · ∑ni=1 ci. For example, suppose there are two tasks, a1 and a2, with p1 = 3 and p2 = 5, and consider the schedule in which a2 runs first, followed by a1. Then c2 = 5, c1 = 8, and the average completion time is (5 + 8)/2 = 6.5. If task a1 runs first, however, then c1 = 3, c2 = 8, and the average completion time is (3 + 8)/2 = 5.5.

2. (1) Design an algorithm with the time complexity of O(nlgn) that schedules the tasks in S so as to minimize the average completion time. Write down the pseudocode of your algorithm.

3. (2) Programming Problem Write a program to implement your algorithm. Get the number of tasks n, and the minimum and maximum units of processing time [min, max] from keyboard. After reading these parameters, randomly generate n tasks with the units of processing time within the range of [min, max]. Print out these n tasks including the units of processing time of each. Your program will process the tasks one by one. After processing each task, print out the current minimal average completion time. For example, for tasks a1 with p1 = 3 and a2 with p2 = 5, suppose task a1 runs first, then your print out could be:

   Process the first task with the units of processing time of 3 Current minimal average completion time: 3

   Process the second task with the units of processing time of 5 Current minimal average completion time: 5.5

   Note: If sorting is used in your program, then you must use heapsort (implement the heapsort algorithm yourself shown on PPT slide 77 of Chapter 2 Basics of Algorithm Analysis). Any existing sorting technique, such as PriorityQueue data structure, Collections.sort and Comparable in Java, in any programming language must not be used in your program.

In java

Answer 1

Algorithm:

Run tasks in shortest possible order of their processing time

Let's suppose {p1, p2, p3, p4, ..,pn} is the processing time. so if we run the task in this order only then

Average completion time would be (p1 + (p1 + p2) + (p1 + p2 + p3).....)

so p1 would be part of each task completion time. similarly p2 would be part of each tasks completion time except first task. so in order to minimize this summation we need to minimize p1, p2, p3 ...pn.

Therefore if we sort the task in increasing order of their procession time we would get minimum average completion time.

Steps:

1> Sort the tasks based on processing time in increasing order

2> Pick each task from sorted array and execute that task