Homework 5 Solution

1-) A small business – lets say, a photocopying service with a single large machine - faces the following scheduling problem. Each morning they get a set of jobs from customers. They want to do the jobs on their single machine in an order that keeps their customers happiest. Job of customer i will take ti time to complete. Given a schedule (i.e., an ordering of the jobs), let Ci denote the finishing time of job i. For example, if job j is the first to be done, we would have Cj




tj; and if job j is done right after job i, we would have Cj = Ci + tj. Each customer i also has a given weight wi that represents his or her importance to the business. The happiness of customer i is expected to be dependent on the finishing time of i’s job. So the company decides
that they want to order the jobs to minimize the weighted sum of the completion times,

∑ =1 . .




Propose a greedy algorithm to solve this problem. That is, you are given a set of n jobs with a processing time ti and a weight wi for each job. You want to order the jobs to minimize the weighted sum of the completion times, ∑ =1 . . Implement the algorithm with Python.




For an example, suppose there are two jobs: the first takes time t1 = 1 and has weight w1 = 10, while the second job takes time t2 = 3 and has weight w2 = 2. Then doing job 1 first would yield a weighted completion time of 10.1 + 2.4 = 18, while doing the second job first would yield the larger weighted completion time of 10.4 + 2.3 = 46.




2-) Suppose you’re running a lightweight consulting business - just you, two associates, and some rented equipment. Your clients are distributed between the East Coast and the West Coast, and this leads to the following question. Each month, you can either run your business from an office in New York (NY) or from an office in San Francisco (SF). In month i, you’ll incur an operating cost of Ni if you run the business out of NY; you’ll incur an operating cost of Si if you run the business out of SF. (It depends on the distribution of client demands for that month.) However, if you run the business out of one city in month i, and then out of the other city in month i + 1, then you incur a fixed moving cost of M to switch base offices.




Given a sequence of n months, a plan is a sequence of n locations - each one equal to either NY or SF - such that the ith location indicates the city in which you will be based in the ith month. The cost of a plan is the sum of the operating costs for each of the n months, plus a moving cost of M for each time you switch cities. The plan can begin in either city.




The problem: Given a value for the moving cost M, and sequences of operating costs




N1 ..... Nn and S1 ..... Sn, find a plan of minimum cost (Such a plan will be called optimal.).




For an example, let’s suppose n=4, M=10 and the operating costs are given by the following table.

#
Month 1
Month 2
Month 3
Month 4










NY
1
3
20
30










SF
50
20
2
4
















Then the plan of minimum cost would be the sequence of locations:




[NY, NY, SF, SF]




with a total cost of 1 + 3 + 2 + 4 + 10 = 20, where the final term of 10 arises because you change locations once.




Show that the following algorithm does not correctly solve this problem by giving an instance which it does not return the correct answer.



for i= 1 to n




if Ni < Si then




Output “NY in Month i”




else




Output “SF in Month i”




end




Propose a dynamic programming algorithm that takes values for n, M, and sequences of operating costs N1 ..... Nn and Sl .....Sn, and returns the cost of an optimal plan. Implement the algorithm with Python.















Explain the algorithms clearly, and analyze time complexity of them in a single PDF file. Add your .py file /s and the PDF file in a folder which is named as your number. Don’t forget to zip your homework before upload it to the Moodle.



















Note:




Submit your homework on Moodle.
You can send an email to b.koca@gtu.edu.tr to ask any question about the homework
Do your homework personally, group studies will be considered as cheating.