Job sequences with deadlines

Chapter 3 : 

3 1 Chapter 3 The Greedy Method

A simple example : 

3 2 A simple example Problem: Pick k numbers out of n numbers such that the sum of these k numbers is the largest. Algorithm: FOR i = 1 to k pick out the largest number and delete this number from the input. ENDFOR

The greedy method : 

3 3 The greedy method Suppose that a problem can be solved by a sequence of decisions. The greedy method has that each decision is locally optimal. These locally optimal solutions will finally add up to a globally optimal solution. Only a few optimization problems can be solved by the greedy method.

Shortest paths on a special graph : 

3 4 Shortest paths on a special graph Problem: Find a shortest path from v0 to v3. The greedy method can solve this problem. The shortest path: 1 + 2 + 4 = 7.

Shortest paths on a multi-stage graph : 

3 5 Shortest paths on a multi-stage graph Problem: Find a shortest path from v0 to v3 in the multi-stage graph. Greedy method: v0v1,2v2,1v3 = 23 Optimal: v0v1,1v2,2v3 = 7 The greedy method does not work.

Solution of the above problem : 

3 6 Solution of the above problem dmin(i,j): minimum distance between i and j. This problem can be solved by the dynamic programming method.

The activity selection problem : 

3 7 The activity selection problem Problem: n activities, S = {1, 2, …, n}, each activity i has a start time si and a finish time fi, si  fi. Activity i occupies time interval [si, fi]. i and j are compatible if si  fj or sj  fi. The problem is to select a maximum-size set of mutually compatible activities

Slide 8: 

3 8 Example: The solution set = {1, 4, 8, 11} Algorithm: Step 1: Sort fi into nondecreasing order. After sorting, f1  f2  f3  …  fn. Step 2: Add the next activity i to the solution set if i is compatible with each in the solution set. Step 3: Stop if all activities are examined. Otherwise, go to step 2. Time complexity: O(nlogn)

Slide 9: 

3 9 Solution of the example: Solution = {1, 4, 8, 11}

Job sequencing with deadlines : 

3 10 Job sequencing with deadlines Problem: n jobs, S={1, 2, …, n}, each job i has a deadline di  0 and a profit pi  0. We need one unit of time to process each job and we can do at most one job each time. We can earn the profit pi if job i is completed by its deadline. The optimal solution = {1, 2, 4}. The total profit = 20 + 15 + 5 = 40.

Slide 11: 

3 11 Algorithm: Step 1: Sort pi into nonincreasing order. After sorting p1  p2  p3  …  pi. Step 2: Add the next job i to the solution set if i can be completed by its deadline. Assign i to time slot [r-1, r], where r is the largest integer such that 1  r  di and [r-1, r] is free. Step 3: Stop if all jobs are examined. Otherwise, go to step 2. Time complexity: O(n2)

Slide 12: 

3 12 e.g. solution = {1, 2, 4} total profit = 20 + 15 + 5 = 40

The knapsack problem : 

3 13 The knapsack problem n objects, each with a weight wi > 0 a profit pi > 0 capacity of knapsack: M Maximize Subject to 0  xi  1, 1  i  n

The knapsack algorithm : 

3 14 The knapsack algorithm The greedy algorithm: Step 1: Sort pi/wi into nonincreasing order. Step 2: Put the objects into the knapsack according to the sorted sequence as possible as we can. e. g. n = 3, M = 20, (p1, p2, p3) = (25, 24, 15) (w1, w2, w3) = (18, 15, 10) Sol: p1/w1 = 25/18 = 1.32 p2/w2 = 24/15 = 1.6 p3/w3 = 15/10 = 1.5 Optimal solution: x1 = 0, x2 = 1, x3 = 1/2 total profit = 24 + 7.5 = 31.5

The 2-way merging problem : 

3 15 The 2-way merging problem # of comparisons required for the linear 2-way merge algorithm is m1+ m2 -1 where m1 and m2 are the lengths of the two sorted lists respectively. 2-way merging example 2 3 5 6 1 4 7 8 The problem: There are n sorted lists, each of length mi. What is the optimal sequence of merging process to merge these n lists into one sorted list ?

Extended binary trees : 

3 16 An extended binary tree representing a 2-way merge Extended binary trees

An example of 2-way merging : 

3 17 An example of 2-way merging Example: 6 sorted lists with lengths 2, 3, 5, 7, 11 and 13.

Slide 18: 

3 18 Time complexity for generating an optimal extended binary tree:O(n log n) Using min-heap

Huffman codes : 

3 19 Huffman codes In telecommunication, how do we represent a set of messages, each with an access frequency, by a sequence of 0’s and 1’s? To minimize the transmission and decoding costs, we may use short strings to represent more frequently used messages. This problem can by solved by using an extended binary tree which is used in the 2-way merging problem.

An example of Huffman algorithm : 

3 20 An example of Huffman algorithm Symbols: A, B, C, D, E, F, G freq. : 2, 3, 5, 8, 13, 15, 18 Huffman codes: A: 10100 B: 10101 C: 1011 D: 100 E: 00 F: 01 G: 11