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
Copyright 2006 John Wiley & Sons, Inc.
16-2
John Deere Case : Page 718 Scheduling Problem Genetic Algorithms (GA)
Copyright 2006 John Wiley & Sons, Inc.
16-3
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
Copyright 2006 John Wiley & Sons, Inc.
16-4
Scheduling function differs based on type of operation . Process industries Mass Production Projects Batch or Job Shop production
Copyright 2006 John Wiley & Sons, Inc.
16-5
type of operation Projects
oneofakind production of a product to customer order
Batch production
systems process many different jobs through the system in groups or batches
Mass production
produces large volumes of a standard product for a mass market
Continuous production (Process Industries)
used for veryhigh volume commodity products
Copyright 2006 John Wiley & Sons, Inc.
16-6
Scheduled Operations Process Industry
Linear programming EOQ with noninstantaneous replenishment
Mass Production
Assembly line balancing
Batch or Job shop Production
Project
Project scheduling techniques (PERT, CPM)
Copyright 2006 John Wiley & Sons, Inc.
Aggregate planning Master scheduling Material requirements planning (MRP) Capacity requirements planning (CRP) Scheduling
16-7
Objectives in Scheduling Meet customer due dates Minimize job lateness Minimize response time Minimize completion time Minimize time in the system
Copyright 2006 John Wiley & Sons, Inc.
Minimize overtime Maximize machine or labor utilization Minimize idle time Minimize workin process inventory
16-8
This chapter concentrates on Batch or Job shop Scheduling Is also known as
Shop Floor control (SFC) or Production control Production Activities Control (PAC)
Copyright 2006 John Wiley & Sons, Inc.
16-9
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
Copyright 2006 John Wiley & Sons, Inc.
16-10
Loading Process of assigning work to limited resources If there is enough capacity, perform work on most efficient resources Use assignment method of linear programming to determine allocation
Copyright 2006 John Wiley & Sons, Inc.
16-11
Assignment Method 1. Perform row reductions
If number of lines equals number of rows in matrix then optimum solution subtract minimum value in each
has been found. Make assignments where zeros appear 2. Perform column reductions subtract minimum value in each Else modify matrix subtract minimum uncrossed value column from all other column from all uncrossed values values add it to all cells where two lines 3. Cross out all zeros in matrix intersect use minimum number of other values in matrix remain horizontal and vertical lines unchanged row from all other row values
3. Repeat steps 3 through 5 until optimum solution is reached
Copyright 2006 John Wiley & Sons, Inc.
16-12
Assignment Method: Example Initial Matrix Bryan Kari Noah Chris
1 10 6 7 9
Row reduction 5 4 2 5
0 0 1 1
1 2 0 0
5 4 1 6
PROJECT 3 6 4 5 4
2 5 2 6 5
4 10 6 6 10
Column reduction
Cover all zeros
3 2 0 3
3 2 0 3
0 0 1 1
1 2 0 0
4 3 0 5
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-13
Assignment Method: Example (cont.) Modify matrix 1 0 0 1
0 0 3 1
1 2 2 0
Cover all zeros 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
Bryan Kari Noah Chris
1 1 0 0 1
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 Copyright 2006 John Wiley & Sons, Inc.
16-14
Microsoft Excel Exhibit 16.1 ลองใช้ Excel แก้ปัญหาการมอบหมายงาน ลองนำาไปใช้แก้ปัญหา Wilkerson Printing หน้า 741
Copyright 2006 John Wiley & Sons, Inc.
16-15
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 Copyright 2006 John Wiley & Sons, Inc.
16-16
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 Slack = (due date – today’s date) – processing time CR - critical ratio SPT - shortest processing time LPT - longest processing time
Copyright 2006 John Wiley & Sons, Inc.
16-17
Slack Time ตัววัดความเร่งด่วนของงานอีกชนิดหน่ ึงคือ ค่าผลต่างระหว่างเวลาท่เี หลือก่อนท่ีจะถึงกำาหนดส่ งมอบกับเวลาท่ีตอ ้ งใช้ในการผลิต เราเรียกเวลานีว้า่ slack time Slack time = dj – pj เสร็จก่อนกำำหนด slack slack
เสร็จตรงตำมกำำหนด เสร็จช้ำกว่ำกำำหนด
t=0
dj
Critical Ratio Rule CR considers both time and work remaining CR =
time remaining work remaining
=
due date - today’s date remaining processing time
If CR > 1, job ahead of schedule If CR < 1, job behind schedule If CR = 1, job on schedule
Copyright 2006 John Wiley & Sons, Inc.
16-19
Sequencing Jobs Through One Process ตัวแบบเคร่ ืองจักรเด่ียว
(Single Machine Scheduling Model)
…
1 machines
MC
n jobs Copyright 2006 John Wiley & Sons, Inc.
16-20
Single Machine Scheduling Model a queue of jobs at one machine. No new jobs arrive during the analysis. processing times and due dates are fixed. Setup times is considered negligible.( เวลาปรับตัง้เคร่ อ ื งไม่ได้ขึ้นกับลำาดับงานท่ท ี ำาก่อน หน้าและเวลาปรับตัง้ถูกรวมอยู่ในเวลาผลิตแล้ว ) no preemption and no idle . Copyright 2006 John Wiley & Sons, Inc.
16-21
Objectives Flowtime (completion time)
Time for a job to flow through the system
Makespan
Time for a group of jobs to be completed
Tardiness
Difference between a late job’s due date and its completion time
Copyright 2006 John Wiley & Sons, Inc.
16-22
Simple Sequencing Rules
JOB
PROCESSING TIME
DUE DATE
A B C D E
5 10 2 8 6
10 15 5 12 8
มี 5! = 120 ทางเลือกในการจัดลำาดับงาน Copyright 2006 John Wiley & Sons, Inc.
16-23
Simple Sequencing Rules: FCFS FCFS START SEQUENCE TIME
A B C D E
0 5 15 17 25
PROCESSING COMPLETION DUE TIME TIME DATE
5 10 2 8 6
Copyright 2006 John Wiley & Sons, Inc.
5 15 17 25 31
10 15 5 12 8
TARDINESS
0 0 12 13 23
16-24
Simple Sequencing Rules: DDATE (earliest due date) DDATE START SEQUENCE TIME
C E A D B
0 2 8 13 21
PROCESSING COMPLETION DUE TIME TIME DATE
2 6 5 8 10
Copyright 2006 John Wiley & Sons, Inc.
2 8 13 21 31
5 8 10 12 15
TARDINESS
0 0 3 9 16
16-25
Simple Sequencing Rules: SLACK
SLACK START SEQUENCE TIME
E C D A B
0 6 8 16 21
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
6 2 8 5 10
Copyright 2006 John Wiley & Sons, Inc.
6 8 16 21 31
8 5 12 10 15
TARDINESS
0 3 4 11 16
16-26
Simple Sequencing Rules: CR CR START SEQUENCE TIME
E D B A C
0 6 14 24 29
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
PROCESSING COMPLETION DUE TIME TIME DATE
6 8 10 5 2
Copyright 2006 John Wiley & Sons, Inc.
6 14 24 29 31
8 12 15 10 5
TARDINESS
0 2 9 19 26
16-27
Simple Sequencing Rules: SPT SPT START SEQUENCE TIME
C A E D B
0 2 7 13 21
PROCESSING COMPLETION DUE TIME TIME DATE
2 5 6 8 10
Copyright 2006 John Wiley & Sons, Inc.
2 7 13 21 31
5 10 8 12 15
TARDINESS
0 0 5 9 16
16-28
Simple Sequencing Rules: Summary RULE
AVERAGE COMPLETION TIME
FCFS DDATE SLACK CR SPT
AVERAGE NO. OF MAXIMUM TARDINESS JOBS TARDY TARDINESS
18.60 15.00 16.40 20.80 14.80
Copyright 2006 John Wiley & Sons, Inc.
9.6 5.6 6.8 11.2 6.0
3 3 4 4 3
23 16 16 26 16
16-29
Sequencing Jobs Through Two Serial Process
Flow Shop m machines
…
…..
n jobs Copyright 2006 John Wiley & Sons, Inc.
16-30
Flow Shop มีสถานีผลิต m สถานี มีงาน n งาน งานแต่ละงานต้องผ่านสถานีผลิตทุกสถานีไปตาม ลำาดับท่ีเหมือนกันและงานไหลไปแล้วไม่ยอ ้ นกลับม าเข้าสถานีผลิตเดิมซ้ำาอีก อาจมีการข้ามสถานีผลิตใดได้ โดยกำาหนดเวลาทำางานสถานีนัน ้ เป็ น 0 เป้ าหมายคือ Minimum Completion Time ตัวอย่าง Flow shop ได้แก่ สายการประกอบ (assembly Copyright 2006 John Wiley & Sons, Inc.
16-31
Flow Shop ที่มี 2 สถานีผลิต Johnson’s 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. Copyright 2006 John Wiley & Sons, Inc.
16-32
Johnson’s Rule JOB
PROCESS 1
PROCESS 2
A B C D E
6 11 7 9 5
8 6 3 7 10
E
Copyright 2006 John Wiley & Sons, Inc.
A
D
B
C
16-33
Johnson’s Rule (cont.) E E
A 5
A
D
D 11
B
C
B
Process 1 (sanding)
C
20
31
38
Idle time E 5
A 15
D 23
B 30
Process 2 (painting)
C 37
41
Completion time = 41 Idle time = 5+1+1+3=10 Copyright 2006 John Wiley & Sons, Inc.
16-34
Excel Exhibit 16.3 ผู้ใช้กำาหนดลำาดับการผลิต Worksheet จะคำานวนหา makespan ให้
Copyright 2006 John Wiley & Sons, Inc.
16-35
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 lowcapacity levels Do not use SPT to sequence jobs that have to be assembled with other jobs at a later date
Copyright 2006 John Wiley & Sons, Inc.
16-36
Monitoring Work package
Shop paperwork that travels with a job
Gantt Chart
Shows both planned and completed activities against a time scale
Input/Output Control
Monitors the input and output from each work center
Copyright 2006 John Wiley & Sons, Inc.
16-37
Gantt Chart Job 32B Behind schedule
Facility
3 Job 23C
Ahead of schedule
2 Job 11C
Job 12A On schedule
1
1 Key:
2
3
4
5
6 8 Today’s Date
9
10
11
12
Days
Planned activity Completed activity
Copyright 2006 John Wiley & Sons, Inc.
16-38
Input/Output Control Input/Output Report PERIOD Planned input Actual input Deviation Planned output Actual output Deviation Backlog 30
1
2
3
4
65 60
65 60
70 65
75 65
75 70
75 70
75 65
75 65
Copyright 2006 John Wiley & Sons, Inc.
TOTAL
16-39
Input/Output Control (cont.) Input/Output Report PERIOD Planned input Actual input Deviation Planned output Actual output Deviation Backlog 30
1
2
3
4
60 60 0 75 70 -5 20
65 60 -5 75 70 -5 10
70 65 -5 75 65 -10 10
75 65 -10 75 65 -10 10
Copyright 2006 John Wiley & Sons, Inc.
TOTAL 270 250 -20 300 270 -30
16-40
Advanced Planning and Scheduling Systems Infinite assumes infinite capacity
Loads without regard to capacity Then levels the load and sequences jobs
Finite assumes finite (limited) capacity
Sequences jobs as part of the loading decision Resources are never loaded beyond capacity
Copyright 2006 John Wiley & Sons, Inc.
16-41
Finite Scheduling Methods Mathematical Programming Network Analysis Simulation ConstraintBased Programming Genetic Algorithm Advanced Neural Network Planning Expert System System Copyright 2006 John Wiley & Sons, Inc.
16-42
Advanced Planning and Scheduling Systems (cont.) Advanced planning and scheduling (APS)
Addins to ERP systems Constraintbased 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
Copyright 2006 John Wiley & Sons, Inc.
16-43
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 Copyright 2006 John Wiley & Sons, Inc.
16-44
Drum-Buffer-Rope Drum
Bottleneck, beating to set the pace of production for the rest of the system
Buffer
Inventory, placed in front of the bottleneck to ensure it is always kept busy Determines output or throughput of the system
Rope
Communication signal, tells processes upstream when they should begin production
Copyright 2006 John Wiley & Sons, Inc.
16-45
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 Copyright 2006 John Wiley & Sons, Inc.
16-46
A
B
Synchronous Manufacturing
C
D
B3 1 7
C3 2 15
D3 3 5
B2 2 3
C2 1 10
D2 2 8
B1 1 5
C1 3 2
D1 3 10
Key:
i
ij k l
Copyright 2006 John Wiley & Sons, Inc.
Item i Operation j of item i performed at machine center k takes l minutes to process
16-47
Synchronous Manufacturing (cont.) Demand = 100 A’s 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
Copyright 2006 John Wiley & Sons, Inc.
16-48
Synchronous Manufacturing (cont.) Setup
Machine 1 C2
Setup B1
2
B3
1002
1562
2322
Idle Setup
Machine 2 C3
B2
12
1512
Machine 3 Setup C1 0 200
Setup D2 1872
2732
Setup D1
Idle 1260
Copyright 2006 John Wiley & Sons, Inc.
D3 1940
Completion time
2737
16-49
Employee Scheduling Labor is very flexible resource Scheduling workforce is complicated repetitive task Assignment method can be used Heuristics are commonly used Copyright 2006 John Wiley & Sons, Inc.
16-50
Employee Scheduling Heuristic •
•
• • •
Let N = no. of workers available Di = demand for workers on day i X = day working O = day off 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 If number of workdays for full time employee < 5, assign remaining workdays so consecutive days off are possible Assign any remaining work to part-time employees If consecutive days off are desired, consider switching schedules among days with the same demand requirements Copyright 2006 John Wiley & Sons, Inc.
16-51
Employee Scheduling DAY OF WEEK MIN NO. OF WORKERS REQUIRED
M
T
W
TH
F
SA
SU
3
3
4
3
4
5
3
Taylor Smith Simpson Allen Dickerson
Copyright 2006 John Wiley & Sons, Inc.
16-52
Employee Scheduling (cont.) DAY OF WEEK MIN NO. OF WORKERS REQUIRED Taylor Smith Simpson Allen Dickerson
M
T
W
TH
F
SA
SU
3
3
4
3
4
5
3
O O X X X
X X O O X
X X X X O
O O X X X
X X O X X
X X X X X
X X X O O
Completed schedule satisfies requirements but has no consecutive days off
Copyright 2006 John Wiley & Sons, Inc.
16-53
Employee Scheduling (cont.) DAY OF WEEK MIN NO. OF WORKERS REQUIRED Taylor Smith Simpson Allen Dickerson
M
T
W
TH
F
SA
SU
3
3
4
3
4
5
3
O O X X X
O O X X X
X X O X X
X X O O X
X X X X O
X X X X X
X X X O O
Revised schedule satisfies requirements with consecutive days off for most employees
Copyright 2006 John Wiley & Sons, Inc.
16-54
Automated Scheduling Systems Staff Scheduling Schedule Bidding Schedule Optimization
Copyright 2006 John Wiley & Sons, Inc.
16-55
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 Copyright 2006 John Wiley & Sons, Inc. 16-56