Due: Thr, Dec 5, in class
Undergraduate students can work in teams of two students and can submit a single paper per team.
Any notation that is not explained is standard notation. Search google for the definition. 10 pts are assigned for each problem. Answers from undergraduate students are marked out of 30 points. Answers from graduate students are marked out of 50 points.
Problem 1: (Based on Problem 3.3 in the textbook) There are $n$ jobs to be scheduled on a single machine, where each job $j$ has a processing time $p_j$, a weight $w_j$, and a due date $d_j$, $j = 1, \ldots, n$. The objective is to schedule the jobs so as to maximize the total weight of the jobs that complete by their due date.
- First prove that there always exists an optimal schedule in which all on-time jobs complete before all late jobs, and the on-time jobs complete in an earliest due date order.
- Next, give a polynomial time algorithm that finds the optimal solution to the scheduling problem for the case when all weights are one, $w_j = 1$ for all $j = 1, \ldots, n$. Justify the time complexity of your algorithm.
Problem 2: Consider the scheduling problem with arbitrary weights from Problem 1. Show how to solve this problem using dynamic programming in $O(nW )$ time, where $W = \sum_{j=1}^n w_j$. Use this result to derive a fully polynomial-time approximation scheme for the problem.
Problem 3: (Problem 4.2 in the textbook) Consider the scheduling problem from Section 4.2 in the textbook but without release times. We must schedule jobs non-preemptively on a single machine to minimize the weighted sum of completion times $\sum_{j=1}^n w_j C_j$. Suppose that the jobs are indexed such that $\frac{w_1}{p_1} \ge \frac{w_2}{p_2}
\ge \ldots \ge \frac{w_n}{p_n}$. Then show it is optimal to schedule job 1 first, job 2 second, and so on. This scheduling rule is called Smith’s rule.
Problem 4: Consider the Integer Programming formulation for the minimum cost complete matching problem in a bipartite graph from Exercise 4.6 in the text.
- Give an example of a bipartite graph for which there is no feasible solution to the integer programming formulation.
- Answer Question 4.6 a.
Problem 5: Answer Question 4.6 b.