Practice Problem: Chapter 15, Short Term Scheduling

Problem 1:

Assume that Susan is a sorority pledge coordinator with four jobs and only three pledges. The table below gives the expected time for each pledge to do each job.

Job 1 / Job 2 / Job 3 / Job 4
Alice / 4 / 9 / 3 / 8
Barbara / 7 / 8 / 2 / 6
Jennifer / 3 / 4 / 5 / 7

If she wishes to minimize the time taken, to whom should she assign which job?

Problem 2:

A custom furniture shop has the five jobs below to be done and they are unsure how to sequence them through the shop.

Job / Days to Finish / Date Promised
(in Days from Today)
A / 2 / 5
B / 8 / 8
C / 6 / 12
D / 4 / 10
E / 1 / 4

Compare the effect of the scheduling methods (a) FCFS (first come, first served), (b) EDD (earliest due date), and (c) SPT (smallest processing time).

Problem 3:

A firm has the following six jobs waiting to be processed:

Job / Hours to Process / Time Due
#407 / 2 / 7
#281 / 8 / 16
#306 / 4 / 4
#429 / 10 / 17
#038 / 5 / 15
#998 / 12 / 18

Develop the appropriate sequencing for these jobs using the Critical Ratio criteria.

Problem 4:

Our furniture manufacturer has the following five jobs that must go through the two work centers in the table below:

Job / Hours Required
Varnishing (Center 1) / Painting (Center 2)
R / 4 / 5
S / 17 / 7
T / 14 / 12
U / 9 / 2
V / 11 / 6

What is the appropriate sequence for these jobs?

Answers

Problem 1:

First, begin with the following assignment table:

Job 1 / Job 2 / Job 3 / Job 4
Alice / 4 / 9 / 3 / 8
Barbara / 7 / 8 / 2 / 6
Jennifer / 3 / 4 / 5 / 7
Dummy / 0 / 0 / 0 / 0

Note: The “dummy” must be added because we have four jobs and only three people. Solve this table for the set of assignments giving the minimum total job time.

Your final table should look like:

Job 1 / Job 2 / Job 3 / Job 4
Alice / 0 / 4 / 0 / 3
Barbara / 4 / 4 / 0 / 2
Jennifer / 0 / 0 / 3 / 3
Dummy / 1 / 0 / 2 / 0

The set of optimal assignments would then be:

Alice – Job 1

Barbara – Job 3

Jennifer – Job 2

Dummy – Job 4

Note that Job 4 does not get done since it is assigned to the “Dummy.”

Problem 2:

(a)

FCFS
Sequence / Process Time / Flow Time / Due Date / Lateness
A / 2 / 2 / 5 / 0
B / 8 / 10 / 8 / 2
C / 6 / 16 / 12 / 4
D / 4 / 20 / 10 / 10
E / 1 / 21 / 4 / 17
TOTALS / 21 / 69 / 33

Average completion time = 69/5 = 13.8 days

Average number of jobs in the system = 69/21 = 3.29 jobs

Average lateness = 33/5 = 6.6 days

Utilization = 21/69 = 30.4%

(b)

EDD
Sequence / Process Time / Flow Time / Due Date / Lateness
E / 1 / 1 / 4 / 0
A / 2 / 3 / 5 / 0
B / 8 / 11 / 8 / 3
D / 4 / 15 / 10 / 5
C / 6 / 21 / 12 / 9
TOTALS / 21 / 51 / 17

Average completion time = 51/5 = 10.2 days

Average number of jobs in the system = 51/21 = 2.43 jobs

Average lateness = 17/5 = 3.4 days

Utilization = 21/51 = 41.2%

(c)

SPT
Sequence / Process Time / Flow Time / Due Date / Lateness
E / 1 / 1 / 4 / 0
A / 2 / 3 / 5 / 0
D / 4 / 7 / 10 / 0
C / 6 / 13 / 12 / 1
B / 8 / 21 / 8 / 13
TOTALS / 21 / 45 / 14

Average completion time = 45/5 = 9 days

Average number of jobs in the system = 45/21 = 2.14 jobs

Average lateness = 14/5 = 2.8 days

Utilization = 21/45 = 46.7%

Problem 3:

Job / Hours to Process / Time Due / Computed Critical Ratio
#407 / 2 / 7 / 7/2 = 3.5
#281 / 8 / 16 / 16/8 = 2.0
#306 / 4 / 4 / 4/4 = 1.0
#429 / 10 / 17 / 17/10 = 1.7
#038 / 5 / 15 / 15/5 = 3.0
#998 / 12 / 18 / 18/12 = 1.5
Critical Ratio Sequence / Critical Ratio
#306 / 1.0
#998 / 1.5
#429 / 1.7
#281 / 2.0
#038 / 3.0
#407 / 3.5

Problem 4:

1