Scheduling

Chapter 16
Scheduling
Operations Management - 5th Edition
Roberta Russell & Bernard W. Taylor, III
Copyright 2006 John Wiley & Sons, Inc.
Beni Asllani University of Tennessee at Chattanooga
Lecture Outline
Objectives in Scheduling Loading Sequencing Monitoring Advanced Planning and Scheduling Systems Theory of Constraints Employee Scheduling
16-2
What is Scheduling?
Last stage of planning before production occurs Specifies when labor, equipment, facilities are needed to produce a product or provide a service
16-3
Scheduled Operations
Process Industry

Linear programming EOQ with non-instantaneous replenishment

Assembly line balancing
Batch Production
Mass Production
Project
Project -scheduling techniques (PERT, CPM)
Aggregate planning Master scheduling Material requirements planning (MRP) Capacity requirements planning (CRP)
16-4
Objectives in Scheduling
Meet customer due dates Minimize job lateness Minimize response time Minimize completion time Minimize time in the system Minimize overtime Maximize machine or labor utilization Minimize idle time Minimize work-inprocess inventory
16-5
Shop Floor Control
Loading
Check availability of material, machines and labor
Sequencing
Release work orders to shop and issue dispatch lists for individual machines
Monitoring
Maintain progress reports on each job until it is complete
16-6
Loading
Process of assigning work to limited resources Perform work on most efficient resources Use assignment method of linear programming to determine allocation
16-7
Assignment Method
1. Perform row reductions 4. If number of lines equals number of rows in matrix then optimum solution subtract minimum value in each
row from all other row values has been found. Make assignments where zeros appear subtract minimum value in each column from all other column values
2. Perform column reductions
5. Else modify matrix

subtract minimum uncrossed value from all uncrossed values add it to all cells where two lines intersect other values in matrix remain unchanged
3. Cross out all zeros in matrix
use minimum number of
horizontal and vertical lines
6. Repeat steps 3 through 5 until optimum solution is reached
16-8
Assignment Method: Example

Initial Matrix Bryan Kari Noah Chris Row reduction 5 4 2 5 0 0 1 1 1 2 0 0 5 4 1 6 1 10 6 7 9 2 5 2 6 5 PROJECT 3 4 6 10 4 6 5 6 4 10 Cover all zeros 3 2 0 3 0 0 1 1 1 2 0 0 4 3 0 5
Column reduction 3 2 0 3 0 0 1 1 1 2 0 0 4 3 0 5
Number lines number of rows so modify matrix

Copyright 2006 John Wiley & Sons, Inc. 16-9
Assignment Method: Example (cont.)

Modify matrix Cover all zeros
1 0 0 1
0 0 3 1
1 2 2 0
2 1 0 3
1 0 0 1
0 0 3 1
1 2 2 0
2 1 0 3
Number of lines = number of rows so at optimal solution 1 1 0 0 1
Bryan Kari Noah Chris
PROJECT 2 3 0 1 0 2 3 2 1 0
4 2 1 0 3
Bryan Kari Noah Chris
1 10 6 7 9
PROJECT 2 3 4 5 6 10 2 4 6 6 5 6 5 4 10
Project Cost = (5 + 6 + 6 + 4) X $100 = $2,100

Sequencing
Prioritize jobs assigned to a resource If no order specified use first-come first-served (FCFS) Many other sequencing rules exist Each attempts to achieve to an objective
Sequencing Rules
FCFS - first-come, first-served LCFS - last come, first served DDATE - earliest due date CUSTPR - highest customer priority SETUP - similar required setups SLACK - smallest slack CR - critical ratio SPT - shortest processing time LPT - longest processing time
16-12
Critical Ratio Rule

CR considers both time and work remaining
CR =
time remaining work remaining
due date - todays date remaining processing time
If CR > 1, job ahead of schedule If CR < 1, job behind schedule If CR = 1, job on schedule
16-13
Sequencing Jobs Through One Process

Flowtime (completion time)
Time for a job to flow through the system Time for a group of jobs to be completed Difference between a late jobs due date and its completion time
16-14
Makespan
Tardiness
Simple Sequencing Rules
JOB
PROCESSING TIME
DUE DATE
A B C D E
5 10 2 8 6
10 15 5 12 8
16-15
Simple Sequencing Rules: FCFS

FCFS SEQUENCE START TIME PROCESSING COMPLETION DUE TIME TIME DATE TARDINESS
A B C D E
0 5 15 17 25
5 10 2 8 6
5 15 17 25 31
10 15 5 12 8
0 0 12 13 23
16-16
Simple Sequencing Rules: DDATE

DDATE SEQUENCE START TIME PROCESSING COMPLETION DUE TIME TIME DATE TARDINESS
C E A D B
0 2 8 13 21
2 6 5 8 10
2 8 13 21 31
5 8 10 12 15
0 0 3 9 16
16-17
Simple Sequencing Rules: SLACK
A(10-0) 5 = 5 B(15-0) - 10 = 5 C(5-0) 2 = 3 D(12-0) 8 = 4 E(8-0) 6 = 2

TARDINESS
SLACK SEQUENCE
START TIME
PROCESSING COMPLETION DUE TIME TIME DATE
E C D A B
0 6 8 16 21
6 2 8 5 10
6 8 16 21 31
8 5 12 10 15
0 3 4 11 16
16-18
Simple Sequencing Rules: CR

CR SEQUENCE START TIME
A(10)/5 = 2.00 B(15)/10 = 1.50 C (5)/2 = 2.50 D(12)/8 = 1.50 E (8)/6 = 1.33
TARDINESS
E D B A C
0 6 14 24 29
6 8 10 5 2
6 14 24 29 31
8 12 15 10 5
0 2 9 19 26
16-19
Simple Sequencing Rules: SPT
SPT SEQUENCE
START TIME
TARDINESS
C A E D B
0 2 7 13 21
2 5 6 8 10
2 7 13 21 31
5 10 8 12 15
0 0 5 9 16
16-20
Simple Sequencing Rules: Summary

RULE AVERAGE COMPLETION TIME AVERAGE TARDINESS NO. OF JOBS TARDY MAXIMUM TARDINESS
FCFS DDATE SLACK CR SPT
18.60 15.00 16.40 20.80 14.80
9.6 5.6 6.8 11.2 6.0
3 3 4 4 3
23 16 16 26 16
16-21
Sequencing Jobs Through Two Serial Process

Johnsons Rule
1. List time required to process each job at each machine. Set up a one-dimensional matrix to represent desired sequence with # of slots equal to # of jobs. 2. Select smallest processing time at either machine. If that time is on machine 1, put the job as near to beginning of sequence as possible. 3. If smallest time occurs on machine 2, put the job as near to the end of the sequence as possible. 4. Remove job from list. 5. Repeat steps 2-4 until all slots in matrix are filled and all jobs are sequenced.
16-22
Johnsons Rule
JOB A B C D E
PROCESS 1 6 11 7 9 5
PROCESS 2 8 6 3 7 10
16-23
Johnsons Rule (cont.)

E
E 5 A 11 D 20
D
B
C
C 31 38
Process 1 (sanding)
Idle time E 5 15 A 23 D 30 B 37 C 41
Process 2 (painting)
Completion time = 41 Idle time = 5+1+1+3=10

Guidelines for Selecting a Sequencing Rule

1. 2. 3. 4. 5. 6. SPT most useful when shop is highly congested Use SLACK for periods of normal activity Use DDATE when only small tardiness values can be tolerated Use LPT if subcontracting is anticipated Use FCFS when operating at low-capacity levels Do not use SPT to sequence jobs that have to be assembled with other jobs at a later date
16-25
Monitoring
Work package
Shop paperwork that travels with a job Shows both planned and completed activities against a time scale Monitors the input and output from each work center
16-26
Gantt Chart
Input/Output Control
Gantt Chart
Job 32B
3 Job 23C 2 Job 11C 1 Ahead of schedule Job 12A On schedule Behind schedule
Facility
1 Key:
6 8 Todays Date
10
11
12
Days
Planned activity
Completed activity
16-27
Input/Output Control
Input/Output Report PERIOD Planned input Actual input Deviation Planned output Actual output Deviation Backlog 30 1 65 60 75 70 2 65 60 75 70 3 70 65 75 65 4 75 65 75 65 TOTAL
16-28
Input/Output Control (cont.)

Input/Output Report PERIOD Planned input Actual input Deviation Planned output Actual output Deviation Backlog 30 1 60 60 0 75 70 -5 20 2 65 60 -5 75 70 -5 10 3 70 65 -5 75 65 -10 10 4 75 65 -10 75 65 -10 10 TOTAL 270 250 -20 300 270 -30
16-29
Advanced Planning and Scheduling Systems

Infinite - assumes infinite capacity

Loads without regard to capacity Then levels the load and sequences jobs Sequences jobs as part of the loading decision Resources are never loaded beyond capacity
16-30
Finite - assumes finite (limited) capacity
Advanced Planning and Scheduling Systems (cont.)

Advanced planning and scheduling (APS)

Add-ins to ERP systems Constraint-based programming (CBP) identifies a solution space and evaluates alternatives Genetic algorithms based on natural selection properties of genetics Manufacturing execution system (MES) monitors status, usage, availability, quality
16-31
Theory of Constraints
Not all resources are used evenly Concentrate on the bottleneck resource Synchronize flow through the bottleneck Use process and transfer batch sizes to move product through facility
16-32
Drum-Buffer-Rope
Drum
Bottleneck, beating to set the pace of production for the rest of the system
Inventory, placed in front of the bottleneck to ensure it is always kept busy Determines output or throughput of the system Communication signal, tells processes upstream when they should begin production
Buffer

Rope
16-33
TOC Scheduling Procedure

Identify bottleneck Schedule job first whose lead time to the bottleneck is less than or equal bottleneck processing time Forward schedule the bottleneck machine Backward schedule the other machines to sustain the bottleneck schedule Transfer in batch sizes smaller than the process batch size
16-34
B B3 1 7
C C3 2 15
D D3 3 5
B2 2 3
C2 1 10
D2 2 8
B1 1 5
Key: i
C1 3 2
Item i
D1 3 10
Synchronous Manufacturing
ij k l
Operation j of item i performed at machine center k takes l minutes to process
16-35
Synchronous Manufacturing (cont.)

Demand = 100 As Machine setup time = 60 minutes MACHINE 1 MACHINE 2 MACHINE 3 B1 B3 C2 Sum 5 7 10 22 B2 C3 D2 3 15 8 26* C1 D3 D1 2 5 10 17
* Bottleneck
16-36
Synchronous Manufacturing (cont.)

Machine 1
C2 2 Idle Machine 2 C3 12 Machine 3 Setup C1 0 200 D1 1260 1512 Setup B2 1872 Setup D2 2732 1002 Setup B1 1562 Setup B3 2322
Setup Idle 1940 D3 Completion time 2737
16-37
Employee Scheduling
Labor is very flexible resource Scheduling workforce is complicated repetitive task Assignment method can be used Heuristics are commonly used
16-38
Employee Scheduling Heuristic

1. Let N = no. of workers available Di = demand for workers on day i X = day working O = day off 2. Assign the first N - D1 workers day 1 off. Assign the next N - D2 workers day 2 off. Continue in a similar manner until all days are have been scheduled 3. If number of workdays for full time employee < 5, assign remaining workdays so consecutive days off are possible 4. Assign any remaining work to part-time employees 5. If consecutive days off are desired, consider switching schedules among days with the same demand requirements
Employee Scheduling
DAY OF WEEK MIN NO. OF WORKERS REQUIRED
Taylor Smith Simpson Allen Dickerson
M
3
T
3
W
4
TH
3
F
4
SA
5
SU
3
16-40
Employee Scheduling (cont.)

M
3 O O X X X
T
3 X X O O X
W
4 X X X X O
TH
3 O O X X X
F
4 X X O X X
SA
5 X X X X X
SU
3 X X X O O
Completed schedule satisfies requirements but has no consecutive days off
16-41
Employee Scheduling (cont.)

M
3 O O X X X
T
3 O O X X X
W
4 X X O X X
TH
3 X X O O X
F
4 X X X X O
SA
5 X X X X X
SU
3 X X X O O
Revised schedule satisfies requirements with consecutive days off for most employees
16-42
Automated Scheduling Systems

Staff Scheduling Schedule Bidding Schedule Optimization
16-43
Copyright 2006 John Wiley & Sons, Inc. All rights reserved. Reproduction or translation of this work beyond that permitted in section 117 of the 1976 United States Copyright Act without express permission of the copyright owner is unlawful. Request for further information should be addressed to the Permission Department, John Wiley & Sons, Inc. The purchaser may make back-up copies for his/her own use only and not for distribution or resale. The Publisher assumes no responsibility for errors, omissions, or damages caused by the use of these programs or from the use of the information herein. Copyright 2006 John Wiley & Sons, Inc. 16-44

Scheduling

Uploaded by

Copyright:

Available Formats

Scheduling

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Scheduling

Uploaded by

Copyright:

Available Formats

Chapter 16

Copyright 2006 John Wiley & Sons, Inc.

Beni Asllani University of Tennessee at Chattanooga

Copyright 2006 John Wiley & Sons, Inc.

Copyright 2006 John Wiley & Sons, Inc.

Linear programming EOQ with non-instantaneous replenishment

Project -scheduling techniques (PERT, CPM)

Copyright 2006 John Wiley & Sons, Inc.

Copyright 2006 John Wiley & Sons, Inc.

Shop Floor Control

Copyright 2006 John Wiley & Sons, Inc.

Copyright 2006 John Wiley & Sons, Inc.

2. Perform column reductions

5. Else modify matrix

3. Cross out all zeros in matrix

use minimum number of

horizontal and vertical lines

6. Repeat steps 3 through 5 until optimum solution is reached

Copyright 2006 John Wiley & Sons, Inc.

Assignment Method: Example

Number lines number of rows so modify matrix

Assignment Method: Example (cont.)

Number of lines = number of rows so at optimal solution 1 1 0 0 1

Bryan Kari Noah Chris

Bryan Kari Noah Chris

Project Cost = (5 + 6 + 6 + 4) X $100 = $2,100

Copyright 2006 John Wiley & Sons, Inc.

Critical Ratio Rule

time remaining work remaining

due date - todays date remaining processing time

Copyright 2006 John Wiley & Sons, Inc.

Sequencing Jobs Through One Process

Copyright 2006 John Wiley & Sons, Inc.

Simple Sequencing Rules

Copyright 2006 John Wiley & Sons, Inc.

Simple Sequencing Rules: FCFS

Copyright 2006 John Wiley & Sons, Inc.

Simple Sequencing Rules: DDATE

Copyright 2006 John Wiley & Sons, Inc.

Simple Sequencing Rules: SLACK

A(10-0) 5 = 5 B(15-0) - 10 = 5 C(5-0) 2 = 3 D(12-0) 8 = 4 E(8-0) 6 = 2

PROCESSING COMPLETION DUE TIME TIME DATE

Copyright 2006 John Wiley & Sons, Inc.

Simple Sequencing Rules: CR

PROCESSING COMPLETION DUE TIME TIME DATE

Copyright 2006 John Wiley & Sons, Inc.

Simple Sequencing Rules: SPT

PROCESSING COMPLETION DUE TIME TIME DATE

Copyright 2006 John Wiley & Sons, Inc.

Simple Sequencing Rules: Summary

FCFS DDATE SLACK CR SPT

18.60 15.00 16.40 20.80 14.80

9.6 5.6 6.8 11.2 6.0

Copyright 2006 John Wiley & Sons, Inc.

Sequencing Jobs Through Two Serial Process

Copyright 2006 John Wiley & Sons, Inc.

Copyright 2006 John Wiley & Sons, Inc.

Johnsons Rule (cont.)

Completion time = 41 Idle time = 5+1+1+3=10