Seciu

Operations Scheduling

Scheduling opportunities
Job shop scheduling  Personnel scheduling  Facilities scheduling  Vehicle scheduling  Vendor scheduling  Project scheduling  Dynamic vs. static scheduling


You are here
Resource Planning Sales and Operations Planning Demand Management

Front end
Master Production Scheduling

Detailed Capacity Planning

Detailed MaterialPlanning

Engine
Material and Capacity Plans

Shop-Floor Systems

Supplier Systems

Back end

Example
Job 1 2 3 4 5 Processing Time 6 2 3 4 5 Due 18 6 9 11 8

What order should we do them in?

Example

Job Characteristics
Arrival pattern: static or dynamic  Number and variety of machines



We will assume they are all identical

Number of workers  Flow patterns of jobs:


all follow same, or many different



Evaluation of alternative rules

Objectives
Many possible objectives:  Meet due dates  Minimize WIP  Minimize average flow time through  High worker/machine utilization  Reduce setup times  Minimize production and worker costs

Terminology
Flow shop: all jobs use M machines in same order Job shop: jobs use different sequencesParallel vs. sequential processing Flow time: from start of first job until completion of job I Makespan: start of first to finish of last Tardiness: >= 0 Lateness: can be 0

Sequencing Rules
First-come, first-served (FCFS) order they entered the shop Shortest Processing Time (SPT) longest job done last Earliest Due Date (EDD) job with last due date goes last Critical Ratio (CR) - processing time /time until due, smallest ratio goes first

Other rules
R - Random  LWR - Least Work Remaining  FOR - Fewest Operations Remaining  ST - Slack Time  ST/O-Slack Time per Operation  NQ-Next Queue – choose job that is going next to the machine with smallest queue  LSU - Least Setup


Performance
Quantities of interest Li Lateness of i: can be +/Ti Tardiness of i: always >= 0 EiEarliness of i Tmax Maximum tardiness

Example: FCFS
Job Time 1 6 2 2 3 3 4 4 5 5 Total Done 6 8 11 15 20 50 Due 18 6 9 11 8 Tardy 0 2 2 4 12 20 = 10.0 = 4.0 4 12

Mean flow time = 50 / 5 Average tardiness = 20 / 5 Number of tardy jobs = Max. Tardy

Example: SPT
Job Time 2 2 3 3 4 4 5 5 1 6 Total Done 2 5 9 14 20 50 Due 6 9 11 8 18 Tardy 0 0 0 6 2 8

Mean flow time = 50 / 5 = Average tardiness= 8 / 5 = Number tardy = Max Tardy

10.0 1.6 2 6

Example: EDD
Job Time 2 2 5 5 3 3 4 4 1 6 Total Done 2 7 10 14 20 51 Due 6 8 9 11 18 Tardy 0 0 1 3 2 6

Mean flow time = 51 / 5 = Average tardiness = 6 / 5 = Number tardy = Max Tardy =

10.2 1.2 3 3

Critical Ratio
Critical ratio:  looks at time remaining between current time and due date  considers processing time as a percentageof remaining time  CR = 1.0 means just enough time  CR > 1 .0 more than enough time  CR < 1.0 not enough time

Example: Critical Ratio


T=0 Job 1 2 3 4 5

Process Time 6 2 3 4 5

Due 18 6 9 11 8

Critical Ratio 3.0 3.0 3.0 2.75 1.6

Job 5 is done first.

Example: Critical Ratio


T=5 Job 1 2 3 4

Process Time 6 2 3 4

Due Current 13 1 4 6

Critical Ratio 2.17 0.51.33 1.5

Job 2 is done second.

Example: Critical Ratio


T=7 Job 1 3 4

Process Time 6 3 4

Due Current 11 2 4

Critical Ratio 1.84 0.67 1.0

Job 3 is done third.

Example: Critical Ratio


T = 10 Job 1 4

Process Time 6 4

Due Current 8 1

Critical Ratio 1.84 0.25

Job 4 is done fourth, and job 1 is last.

Critical Ratio Solution
Job Time 5 5 2 2 3 3 4 4 1 6Total Done 5 7 10 14 20 56 Due 8 6 9 11 18 Tardy 0 1 1 3 2 7

Mean flow time = 56 / 5 = Average tardiness = 7 / 5 = Number tardy = Max Tardy

11.2 1.4 4 3

Summary
Method FCFS SPT EDD CR Flow 10.0 10.0 10.0 11.2
Average Number Max Tardiness tardy Tardy 4.0 4 12 1.6 2 6 1.2 3 3 1.4 4 3

Minimizing Average Lateness
Mean flow time minimized by SPT  For single-machine scheduling,...