Chapter 16 – Scheduling
16–11
Note: A minimum of five lines is needed. There are five rows. Because the minimum number of
lines equals the number of rows, an optimum assignment can be made.
Step 6:
Make the assignments. Begin with rows or columns with only one zero. Match items that have
Note: An alternate solution is possible by flipping Truck 2 & Truck 3: We could assign Truck 2
to Route E & Truck 3 to Route D.
Step 7:
Compute the costs.
Assignment
Cost
1-A
$4
2-D
$3
3-E
$6
4-B
$2
5-C
$3
Total =
$18
Alternate Solution:
1
0
2
6
4
1
2
3
2
6
0
0
Truck
3
3
0
7
0
0
4
2
0
3
2
3
5
2
2
0
0
3
Assignment
Cost
1-A
$4
2-E
$5
3-D
$4
4-B
$2
5-C
$3
Total =
$18
16–12
Education.
4. Given:
Processing costs:
Worker
A
B
C
1
12
8
11
Job
2
13
10
8
3
14
9
14
4
10
7
12
Note: The number of jobs exceeds the number of workers. We must add a dummy worker (D)
with costs of 0.
Worker
Row
A
B
C
D
Min.
1
12
8
11
0
0
Job
2
13
10
8
0
0
3
14
9
14
0
0
4
10
7
12
0
0
Step 1:
Row reduction: Subtract the smallest number in each row from every number in the row.
Because of the dummy worker, the minimum for each row is 0 and the table will not change.
Worker
A
B
C
D
1
12
8
11
0
Job
2
13
10
8
0
3
14
9
14
0
4
10
7
12
0
Column
Min.
10
7
8
0
Chapter 16 – Scheduling
16–13
Step 2:
Column reduction: Subtract the smallest number in each column of the previous table from every
number in the column.
Worker
A
B
C
D
1
2
1
3
0
Job
2
3
3
0
0
3
4
2
6
0
4
0
0
4
0
Step 3:
Test whether an optimum assignment can be made. Determine the minimum number of lines
(horizontal and/or vertical) needed to cover all zeros. If the number of lines equals the number of
rows, an optimum assignment is possible.
Worker
A
B
C
D
1
2
1
3
0
Job
2
3
3
0
0
3
4
2
6
0
4
0
0
4
0
Note: A minimum of three lines is needed, which is less than the number of rows (four).
Step 4:
Because the number of lines is less than the number of rows, we must modify the table.
a. Subtract the smallest uncovered number (1) from every uncovered number in the table.
b. Add the smallest uncovered number (1) to the numbers at intersections of cross-out lines.
c. Carry over numbers crossed out but not at intersections to the next table.
Worker
A
B
C
D
1
1
0
3
0
Job
2
2
2
0
0
3
3
1
6
0
4
0
0
5
1
Chapter 16 – Scheduling
16–14
Education.
Step 5:
Test whether an optimum assignment can be made. Determine the minimum number of lines
(horizontal and/or vertical) needed to cover all zeros. If the number of lines equals the number of
rows, an optimum assignment is possible.
Worker
A
B
C
D
1
1
0
3
0
Job
2
2
2
0
0
3
3
1
6
0
4
0
0
5
1
Step 6:
Make the assignments. Begin with rows or columns with only one zero. Match items that have
zeros, using only one match for each row and column. Eliminate both the row and the column
after the match.
Start with Row 3, Column A, & Column C because each has one zero.
Worker
A
B
C
D
1
1
0
3
0
Job
2
2
2
0
0
3
3
1
6
0
4
0
0
5
1
Step 7:
Compute the costs.
Assignment
Cost
1-B
$8
2-C
$8
3-D
$0
4-A
$10
Total =
$26
Note: The implication of scheduling Job 3 to the dummy worker (D) is that Job 3 will not
performed.
Chapter 16 – Scheduling
5. Given:
Worker
A
B
C
D
E
1
14
18
20
17
18
2
14
15
19
16
17
Job
3
12
16
15
14
17
4
11
13
14
12
14
5
10
16
15
14
13
a. The combination 2-D is undesirable.
Note: We need to assign a relatively high cost to this combination (2–D) to avoid it. For
example, we could take its cost and set it equal to the highest value in the table (20) times 3:
20 * 3 = 60.
Worker
Row
A
B
C
D
E
Min.
1
14
18
20
17
18
14
2
14
15
19
60
17
14
Job
3
12
16
15
14
17
12
4
11
13
14
12
14
11
5
10
16
15
14
13
10
Step 1:
Row reduction: Subtract the smallest number in each row from every number in the row.
Worker
A
B
C
D
E
1
0
4
6
3
4
2
0
1
5
46
3
Job
3
0
4
3
2
5
4
0
2
3
1
3
5
0
6
5
4
3
Column
Min.
0
1
3
1
3
Chapter 16 – Scheduling
16–16
Education.
Step 2:
Column reduction: Subtract the smallest number in each column of the previous table from
every number in the column.
Worker
A
B
C
D
E
1
0
3
3
2
1
2
0
0
2
45
0
Job
3
0
3
0
1
2
4
0
1
0
0
0
5
0
5
2
3
0
Step 3:
Test whether an optimum assignment can be made. Determine the minimum number of lines
(horizontal and/or vertical) needed to cover all zeros. If the number of lines equals the
number of rows, an optimum assignment is possible.
Worker
A
B
C
D
E
1
0
3
3
2
1
2
0
0
2
45
0
Job
3
0
3
0
1
2
4
0
1
0
0
0
5
0
5
2
3
0
Note: A minimum of five lines is needed. There are five rows. Because the minimum number
Start with Row 1, Column B, & Column D because each has one zero.
Worker
A
B
C
D
E
1
0
3
3
2
1
2
0
0
2
45
0
Job
3
0
3
0
1
2
4
0
1
0
0
0
5
0
5
2
3
0
Chapter 16 – Scheduling
Step 5
Chapter 16 – Scheduling
Step 2:
(horizontal and/or vertical) needed to cover all zeros. If the number of lines equals the
number of rows, an optimum assignment is possible.
Worker
A
B
C
D
E
1
44
1
1
0
0
2
0
0
2
45
1
Job
3
0
3
0
1
3
4
0
1
0
0
1
5
0
5
2
3
1
Note: A minimum of five lines is needed. There are five rows. Because the minimum number
of lines equals the number of rows, an optimum assignment can be made.
Step 6:
Make the assignments. Begin with rows or columns with only one zero. Match items that
have zeros, using only one match for each row and column. Eliminate both the row and the
Worker
A
B
C
D
E
1
44
1
1
0
0
2
0
0
2
45
1
Job
3
0
3
0
1
3
4
0
1
0
0
1
5
0
5
2
3
1
Processing
Due Date
Processing
Due Date
6. Given:
The following table contains information on four jobs waiting for processing at a work center (the
jobs are listed in the order of their arrival):
Job
Job Time
(days)
Due Date
(days)
A
14
20
B
10
16
C
7
15
D
6
17
a. Determine job sequence for (1) FCFS, (2) SPT, (3) EDD, and (4) CR:
(1) FCFS: A-B-C-D
(2) SPT: D-C-B-A
(3) EDD: C-B-D-A
(4) CR: A-C-D-B (see below for work)
CR Calculations (round to 2 decimals):