You are running a software company and have a series of n jobs that must be pre-processed first on a supercomputer before being moved to a smaller PC. You have only one super- computer, but you have n PCs so the second stage can be performed in in parallel. More specifically, your jobs are described as J- (s1f), J2 (22).., Jn-(Sn, n), where job J needs si units of time to be pre-processed on the super-computer and fi units of time on the PC You need to work out an order in which to give the jobs to the super-computer. As soon as the first job is done on the super-computer, it can be moved to the PC for finishing; at that point a second job can be given to the super-computer; when the second job is done it can go straight to a PC since the PCs can work in parallel, and so on. So if the jobs are processed in the order given, job J finishes at time (sk) fi. A schedule is an ordering of the jobs to be given to the super-computer. The completion time is the point at which all jobs have finished being processed on the PCs. We wish to minimize the completion time. (a) Give an efficient (greedy!) algorithm for computing the optimal order in which to proces the jobs so that the completion time is minimized. (b) Describe the greedy choice your algorithm makes and show that it is correct.

A)

Greedy algorithms are a class of algorithm that will choose the local optimum at any time to find the optimum solution for the problem.

The problem here is to reduce the completion time.

Since only one super computer is there, it can process the jobs sequentially and its processing time is constant.

The individual "n" PCs need to process only one job each and the completion time will depend on the completion of all PC processing

Thus sort the jobs in descending order of the "fi" time and feed the super computer from lager PC time process to smaller PC time process.

Algorithm:

- sort the jobs in the descending order of value of "fi".

       New List = Sort(Ji) on fi

- Feed the super computer in the sorted order of jobs Newlist.

B)

The greedy choice used above is selecting the jobs with higher value of PC time at every time.

Thus the completion time can be reduced since the jobs with higher PC time will be finished first.

Thus the overhead time after finishing the super computer processing can be eliminated.

Since the super computer process the job with smallest PC time last, the best finishing time can be + smallest(fi).

Thus optimum completion time can be obtained through the algorithm in "A".

Explanation:

hi

explanation:

how is this a question? in order for me to answer it i have to understand the question

explanation: