Transcript Short-Term Scheduling

Operations
Management
Chapter 15 –
Short-Term Scheduling
PowerPoint presentation to accompany
Heizer/Render
Operations Management, 8e
© 2006
Prentice
Hall, Inc. Hall, Inc.
©
2006
Prentice
15 – 1
Strategic Importance of
Short-Term Scheduling
 Effective and efficient scheduling
can be a competitive advantage
 Faster movement of goods through a
facility means better use of assets
and lower costs
 Additional capacity resulting from
faster throughput improves customer
service through faster delivery
 Good schedules result in more
reliable deliveries
© 2006 Prentice Hall, Inc.
15 – 2
Scheduling Decisions
Organization
Arnold Palmer
Hospital
University of
Missouri
Lockheed-Martin
factory
Hard Rock Cafe
Delta Airlines
Table 15.1
© 2006 Prentice Hall, Inc.
Managers Must Schedule the Following
Operating room use
Patient admissions
Nursing, security, maintenance staffs
Outpatient treatments
Classrooms and audiovisual equipment
Student and instructor schedules
Graduate and undergraduate courses
Production of goods
Purchases of materials
Workers
Chef, waiters, bartenders
Delivery of fresh foods
Entertainers
Opening of dining areas
Maintenance of aircraft
Departure timetables
Flight crews, catering, gate, ticketing personnel
15 – 3
Defining Scheduling
 Scheduling deals with the assignment
of activities to resources (and viceversa) and timing of activities
 Types of scheduling situations
 Type I: Supply options (M) are fewer
than demand options (N)
 Type II: Supply options (M) are equal to
demand options (N)
 Type III: Supply options (M) exceed the
number of demand options (N)
© 2006 Prentice Hall, Inc.
15 – 4
Positioning
Scheduling
Figure 15.1
© 2006 Prentice Hall, Inc.
15 – 5
Objectives of Scheduling
 Goals of scheduling
 Type I: Supply options (M) are fewer than
demand options (N)
 Assign scarce supply to demand to minimize cost or
maximize benefits
Type II: Supply options (M) are equal to
demand options (N)
 Assign supply to demand to minimize cost or
maximize benefits for total process
Type III: Supply options (M) exceed the
number of demand options (N)
 Scheduling is done for limited capacity and excess
capacity is outsourced.
© 2006 Prentice Hall, Inc.
15 – 6
Scheduling Methods
 Types of scheduling methods
 Arbitrary approaches
 Useful when there are no constraints of
resources
 Rule-based approaches
 Useful when there are constraints of resources
 Priorities-based approaches
 Useful when there are constraints of resources
and there are priorities among suppliers or
customers
© 2006 Prentice Hall, Inc.
15 – 7
Assignment Method
(Type II Scheduling)
 A special class of linear programming models
that assign tasks or jobs to resources
 Objective is to minimize cost or time
 Only one job (or worker) is assigned to one
machine (or project)
© 2006 Prentice Hall, Inc.
15 – 8
Assignment Method
1.
Create zero opportunity costs by repeatedly subtracting
the lowest costs from each row and column
2.
Draw the minimum number of vertical and horizontal
lines necessary to cover all the zeros in the table. If the
number of lines equals either the number of rows or the
number of columns, proceed to step 4. Otherwise
proceed to step 3.
3.
Subtract the smallest number not covered by a line from
all other uncovered numbers. Add the same number to
any number at the intersection of two lines. Return to
step 2.
4.
Optimal assignments are at zero locations in the table.
Select one, draw lines through the row and column
involved, and continue to the next assignment.
© 2006 Prentice Hall, Inc.
15 – 9
Assignment Example
Typesetter
Job
R-34
S-66
T-50
Step 1a - Rows
C
$11
$ 8
$ 9
$14
$10
$12
$ 6
$11
$ 7
Typesetter
A
© 2006 Prentice Hall, Inc.
B
Step 1b - Columns
Typesetter
Job
R-34
S-66
T-50
A
$ 5
$ 0
$ 2
B
$ 8
$ 2
$ 5
C
$ 0
$ 3
$ 0
Job
R-34
S-66
T-50
A
B
C
$ 5
$ 0
$ 2
$ 6
$ 0
$ 3
$ 0
$ 3
$ 0
15 – 10
Assignment Example
Step 2 - Lines
Typesetter
Job
R-34
S-66
T-50
A
B
C
$ 5
$ 0
$ 2
$ 6
$ 0
$ 3
$ 0
$ 3
$ 0
The smallest uncovered
number is 2 so this is
subtracted from all other
uncovered numbers and
added to numbers at the
intersection of lines
Step 3 - Subtraction
Typesetter
Because only two lines
are needed to cover all
the zeros, the solution
is not optimal
© 2006 Prentice Hall, Inc.
Job
R-34
S-66
T-50
A
B
C
$ 3
$ 0
$ 0
$ 4
$ 0
$ 1
$ 0
$ 5
$ 0
15 – 11
Assignment Example
Step 2 - Lines
Typesetter
Job
R-34
S-66
T-50
A
B
C
$ 3
$ 0
$ 0
$ 4
$ 0
$ 1
$ 0
$ 5
$ 0
Because three lines are
needed, the solution is
optimal and
assignments can be
made
© 2006 Prentice Hall, Inc.
Start by assigning R-34 to
worker C as this is the only
possible assignment for
worker C. Job T-50 must
go to worker A as worker C
is already assigned. This
leaves S-66 for worker B.
Step 4 - Assignments
Typesetter
Job
R-34
S-66
T-50
A
B
C
$ 3
$ 0
$ 0
$ 4
$ 0
$ 1
$ 0
$ 5
$ 0
15 – 12
Assignment Example
From the original cost table
Minimum cost = $6 + $10 + $9 = $25
Step 4 - Assignments
Typesetter
Typesetter
A
Job
R-34
S-66
T-50
© 2006 Prentice Hall, Inc.
$11
$ 8
$ 9
B
$14
$10
$12
C
$ 6
$11
$ 7
Job
R-34
S-66
T-50
A
B
C
$ 3
$ 0
$ 0
$ 4
$ 0
$ 1
$ 0
$ 5
$ 0
15 – 13
Opportunity Loss: Assignment
Example 2
Typesetter
Job
R-34
S-66
T-50
A
B
C
$11
$ 8
$ 9
$14
$10
$12
$ 6
$11
$ 7
Opportunity Loss Table
A
B
C
15-11
15-8
14-9
15-14
15-10
14-12
15-6
15-11
14-7
Job
© 2006 Prentice Hall, Inc.
Opportunity Loss Table
Typesetter
Typesetter
R-34
S-66
T-50
Assume sale price for
units made on each
Resource are:
R-34 = $ 15 /unit;
S-66 = $ 15 /unit;
T-50 = $ 14 /unit;
Job
R-34
S-66
T-50
A
B
C
$ 4
$ 7
$ 5
$ 1
$ 5
$ 2
$ 9
$ 4
$ 7
15 – 14
Opportunity Loss: Assignment
Example 2
The table has profit margins that are earned for each unit made. To
find the optimal assignment, use the method but subtract the highest
score of each row not the least one.
Typesetter
A
Job
R-34
S-66
T-50
B
1
Typesetter
C
Opportunity Loss Table
$ 4
$ 7
$ 5
$ 1
$ 5
$ 2
$ 9
$ 4
$ 7
Take smallest number from uncrossed
cells and subtract it from all other
uncrossed numbers in each column.
Add the number to number on
Intersection to get table 3.
This is not an optimal solution – 2 lines
through all zeros
© 2006 Prentice Hall, Inc.
Job
R-34
S-66
T-50
A
B
-$ 5
$0
-$ 2
-$ 8
-$ 2
-$ 5
Typesetter
Job
R-34
S-66
T-50
A
B
-$ 5
$0
-$ 2
-$ 6
$0
-$ 3
2
C
$0
-$ 3
$0
3
C
$0
-$ 3
$0
15 – 15
Opportunity Loss: Example 2
Largest
uncrossed
number
Subtract largest number from
all unexposed numbers, to get
Table 2
Typesetter
Assign A to T-50; B to S-66; C to R-34.
The profit margin of the assignment
is taken from first table:
=
$5 + $ 5 + $ 9 = $ 19
Typesetter
A
Job
R-34
S-66
T-50
© 2006 Prentice Hall, Inc.
B
1
$ 1
$ 5
$ 2
A
B
-$ 5
$0
-$ 2
-$ 6
$0
-$ 3
Typesetter
C
Opportunity Loss Table
$ 4
$ 7
$ 5
Job
R-34
S-66
T-50
$ 9
$ 4
$ 7
Job
R-34
S-66
T-50
1
A
B
-$ 3
$0
$0
-$ 4
$0
-$ 1
2
C
$0
-$ 3
$0
C
$0
-$ 1
$0
15 – 16
Gantt Load Chart Method
(Type III Scheduling)
Day
Work
Center
Metalworks
Monday
Tuesday
Job 349
Job 349
Job 408
Painting
Processing
Thursday
Friday
Job 350
Mechanical
Electronics
Wednesday
Job 408
Job 349
Job 295
Job 408
Unscheduled
Job 349
Center not available
Figure 15.3
© 2006 Prentice Hall, Inc.
15 – 17
Gantt Staffing Chart (Type III Scheduling)
Bill
Mon
Tue
Off
Off
Mary
Wed
Thu
Off
Off
Sue
Schedule
Off
Will
Off
Off
Bob
Off
Off
Mon
Off
Fri
Sat
Sun
Off
Off
Josh
Off
Off
1. Required Capacity
5
5
6
5
8
9
9
2. Max available staff
7
7
7
7
7
7
7
3. Max off duty staff
2
2
1
2
-1
-2
-2
4. Scheduled off-duty
3
3
2
3
2
1
0
5. Extra staff needed
1
1
1
1
3
3
2
4. Minus 3
© 2006 Prentice Hall, Inc.
15 – 18
Gantt Staffing Chart (Type III Scheduling)
Sat
Sun
Bill
Off
Off
Mary
Off
Off
Sue
Off
Off
Mon
Schedule
Tue
Wed
Thu
Fri
Will
Off
Off
Bob
Off
Off
Mon
Josh
Off
Off
Off
Off
1. Required Capacity
5
5
6
5
8
9
9
2. Max available staff
7
7
7
7
7
7
7
3. Max off duty staff
2
2
1
2
-1
-2
-2
4. Scheduled off-duty
1
2
1
2
2
3
3
5. Extra staff needed
0
0
0
0
3
5
5
4. Minus 3
© 2006 Prentice Hall, Inc.
This solution shifts all temp staff requirement to
weekends
15 – 19
Gantt Staffing Chart (Type III Scheduling)
Mon
Tue
Wed
Thu
Fri
Sat
Sun
Bill
Mary
Sue
Will
Bob
Mon
Josh
1. Required Capacity
2. Max available staff
3. Max off duty staff
4. Actual off-duty
5. Extra staff needed
© 2006 Prentice Hall, Inc.
15 – 20
Gantt Schedule Chart
Example
Job
Day
1
Day Day
2
3
Day Day Day Day Day
4
5
6
7
8
A
B
Start of an
activity
End of an
activity
Scheduled
activity time
allowed
Actual work
progress
Maintenance
Nonproduction
time
C
Figure 15.4
© 2006 Prentice Hall, Inc.
Point in time
when chart is
reviewed
Now
15 – 21
Sequencing
 Specifies the order in which jobs should be
performed at work centers
 Priority rules are used to dispatch or
sequence jobs
 FCFS: First come, first served
 SPT: Shortest processing time
 EDD: Earliest due date
 LPT: Longest processing time
© 2006 Prentice Hall, Inc.
15 – 22
Sequencing Example
Apply the four popular sequencing rules
to these five jobs
Job
A
B
C
D
E
© 2006 Prentice Hall, Inc.
Job Work
(Processing) Time
(Days)
6
2
8
3
9
Job Due
Date
(Days)
8
6
18
15
23
15 – 23
Sequencing: FCFS Example
FCFS: Sequence A-B-C-D-E
Job
Sequence
Job
Work
(Proce
ssing)
Time
Wait
Times
Flow
Time
Job Due
Date
A
6
0
6
8
0
B
2
6
8
6
2
C
8
8
16
18
0
D
3
16
19
15
4
E
9
19
28
23
5
28
28
49
77
© 2006 Prentice Hall, Inc.
Job
Lateness
11
15 – 24
Sequencing Example
FCFS: Sequence A-B-C-D-E
Average completion time =
Total flow time
= 77/5 = 15.4 days
Number of jobs
Total job work time
Utilization =
Total flow time = 28/77 = 36.4%
Total flow time
Average number of
jobs in the system = Total job work time = 77/28 = 2.75 jobs/month
Total late days
Average job lateness = Number of jobs = 11/5 = 2.2 days
© 2006 Prentice Hall, Inc.
15 – 25
Sequencing Example
SPT: Sequence B-D-A-C-E
Job
Sequence
Job Work
(Processing)
Time
Flow
Time
Job Due
Date
B
2
2
6
0
D
3
5
15
0
A
6
11
8
3
C
8
19
18
1
E
9
28
23
5
28
65
© 2006 Prentice Hall, Inc.
Job
Lateness
9
15 – 26
Sequencing Example
SPT: Sequence B-D-A-C-E
Total flow time
Average completion time =
= 65/5 = 13 days
Number of jobs
Total job work time
Utilization =
Total flow time = 28/65 = 43.1%
Total flow time
Average number of
=
= 65/28 = 2.32
jobs in the system
Total job work time
jobs/months
Total late days
Average job lateness = Number of jobs = 9/5 = 1.8 days
© 2006 Prentice Hall, Inc.
15 – 27
Sequencing Example
EDD: Sequence B-A-D-C-E
Job
Sequence
Job Work
(Processing)
Time
Flow
Time
Job Due
Date
B
2
2
6
0
A
6
8
8
0
D
3
11
15
0
C
8
19
18
1
E
9
28
23
5
28
68
© 2006 Prentice Hall, Inc.
Job
Lateness
6
15 – 28
Sequencing Example
EDD: Sequence B-A-D-C-E
Total flow time
Average completion time =
Number of jobs
= 68/5 = 13.6 days
Total job work time
Utilization = Total flow time
= 28/68 = 41.2%
Total flow time
Average number of
=
= 68/28 = 2.43 jobs/
jobs in the system
Total job work time
month
Total late days
Average job lateness = Number of jobs = 6/5 = 1.2 days
© 2006 Prentice Hall, Inc.
15 – 29
Sequencing Example
LPT: Sequence E-C-A-D-B
Job
Sequence
Job Work
(Processing)
Time
Flow
Time
Job Due
Date
E
9
9
23
0
C
8
17
18
0
A
6
23
8
15
D
3
26
15
11
B
2
28
6
22
28
103
© 2006 Prentice Hall, Inc.
Job
Lateness
48
15 – 30
Sequencing Example
LPT: Sequence E-C-A-D-B
Total flow time
Average completion time =
= 103/5 = 20.6 days
Number of jobs
Total job work time
Utilization =
Total flow time = 28/103 = 27.2%
Total flow time
Average number of
=
= 103/28 = 3.68 jobs
jobs in the system
Total job work time
Total late days
Average job lateness = Number of jobs = 48/5 = 9.6 days
© 2006 Prentice Hall, Inc.
15 – 31
Summary Sequencing Examples
Summary of Rules
Average Number
of Jobs in
Average
Utilization
System per
Lateness
(%)
month
(Days)
Rule
Average
Completion
Time (Days)
FCFS
15.4
36.4
2.75
2.2
SPT
13.0
43.1
2.32
1.8
EDD
13.6
41.2
2.43
1.2
LPT
20.6
27.2
3.68
9.6
© 2006 Prentice Hall, Inc.
15 – 32
Comparison of
Sequencing Rules
 No one sequencing rule excels on all
criteria
 SPT does well on minimizing flow time and
number of jobs in the system
 But SPT moves long jobs to the end which
may result in dissatisfied customers
 FCFS does not do especially well (or
poorly) on any criteria but is perceived as
fair by customers
 EDD minimizes lateness
© 2006 Prentice Hall, Inc.
15 – 33
Improving Performance of System
 Changing setting of due dates
 Changing process serial to parallel form
A
B
C
A
B
E
C
© 2006 Prentice Hall, Inc.
E
D
D
15 – 34