CSE 321 Homework 5

CSE 321 Homework 5

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.
a) 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
b) 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.