Scheduling

IE 1101

Md. Ariful Ferdous

Lecturer
Department of Industrial Engineering
BUFT
IE 1101 1
Scheduling

Scheduling is the process of arranging, controlling and optimizing work

and workloads in a production process or manufacturing process.
Scheduling is used to allocate plant and machinery resources, plan
human resources, plan production processes and purchase materials.

IE 1101 2
Scheduling

Flow time – length of time a job is at particular workstation

Job delay – length of time the job completion data is expected to exceed
the job due date
Make span – total time needed to complete a group of jobs
Average no of jobs – ratio of total flow time to make-span

IE 1101 3
Scheduling Criteria

✓Minimize completion time

✓Maximize utilization of facilities

✓Minimize work-in-process (WIP) inventory

✓Minimize customer waiting time

IE 1101 4
Principles of Scheduling

The principle of optimum task size: Scheduling tends to achieve

maximum efficiency when the task sizes are small and all tasks are of
same order of magnitude.

IE 1101 5
Sequencing Jobs

✓Specifies the order in which jobs should be performed at work centers

✓Priority rules are used to dispatch or sequence jobs in one work center
✓FCFS: First come, first served

✓SPT: Shortest processing time

✓EDD: Earliest due date

✓LPT: Longest processing time

IE 1101 6
Sequencing Example

✓Apply the four popular sequencing rules to these five jobs

Job Work Job Due
(Processing) Time Date
Job (Days) (Days)
A 6 8
B 2 6
C 8 18
D 3 15
E 9 23

IE 1101 7
Sequencing Example(FCFS)

✓FCFS: Sequence A-B-C-D-E

Job Work
Job (Processing) Flow Job Due Job
Sequence Time Time Date Lateness
A 6 6 8 0
B 2 8 6 2
C 8 16 18 0
D 3 19 15 4
E 9 28 23 5
28 77 11
IE 1101 8
Sequencing Example(FCFS)

✓FCFS: Sequence A-B-C-D-E

Sum of total flow time

Average completion time = Number of jobs = 77/5 = 15.4 days

Total late days

Average job lateness = Number of jobs = 11/5 = 2.2 days

IE 1101 9
Sequencing Example(SPT)

✓SPT: Sequence B-D-A-C-E

Job Work
Job (Processing) Flow Job Due Job
Sequence Time Time Date Lateness
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 9
IE 1101 10
Sequencing Example(SPT)

✓SPT: Sequence B-D-A-C-E

Sum of total flow time

Average completion time = Number of jobs = 65/5 = 13 days

Total late days

Average job lateness = Number of jobs = 9/5 = 1.8 days

IE 1101 11
Sequencing Example(EDD)

✓EDD: Sequence B-A-D-C-E

Job Work
Job (Processing) Flow Job Due Job
Sequence Time Time Date Lateness
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 6
IE 1101 12
Sequencing Example(EDD)

✓EDD: Sequence B-A-D-C-E

Sum of total flow time

Average completion time = Number of jobs = 68/5 = 13.6 days

Total late days

Average job lateness = Number of jobs = 6/5 = 1.2 days

IE 1101 13
Sequencing Example(LPT)

✓LPT: Sequence E-C-A-D-B

Job Work
Job (Processing) Flow Job Due Job
Sequence Time Time Date Lateness
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 48
IE 1101 14
Sequencing Example(LPT)

✓LPT: Sequence E-C-A-D-B

Sum of total flow time

Average completion time = Number of jobs = 103/5 = 20.6 days

Total late days

Average job lateness = Number of jobs = 48/5 = 9.6 days

IE 1101 15
Sequencing Example(Summary for different Rules)

Average Average
Total Flow
Rule Completion Time Lateness
Time(Days)
(Days) (Days)

FCFS 77 15.4 2.2

SPT 65 13.0 1.8

EDD 68 13.6 1.2

LPT 103 20.6 9.6

IE 1101 16
Sequencing Example for Practice

Job Processing Time (days) Due Date (days)

A 2 7
B 8 16
C 4 4
D 10 17
E 5 15
F 12 18

IE 1101 17
Sequencing Example for Practice Solved
Techniques

Criteria FCFS SPT EDD

Total Flow Time 120 108 110

Av Flow Time 20 18 18.33

Total Delay 54 40 38

Average Delay 9 6.67 6.33

IE 1101 18
Gantt chart

✓a chart in which a series of horizontal lines shows the of time in relation

to the amount of work done or production completed in certain
periods mount planned for those periods.
✓Modern Gantt charts also show the dependency relationships between
activities and current schedule status
✓Originated by [Link] in 1918

IE 1101 19
Gantt chart

IE 1101 20
Parallel Machine model procedures:
Step-1: Sequence the n jobs in LPT order
Step-2: Schedule each job(From the LPT) in order, each time
assigning a job to the machine with the least amount of
processing already assigned.
Step-3: After all the jobs are assigned, reverse the sequence
individually on each machine.

IE 1101 21
Parallel Machine Problem
Consider the following 10 jobs with 3 parallel identical machines.

Job 1 2 3 4 5 6 7 8 9 10
Processing
time(hrs) 5 6 3 8 7 2 3 5 4 2

IE 1101 22
Parallel Machine Problem(Solution)
Consider the following 10 jobs with 3 parallel identical machines.

Job 1 2 3 4 5 6 7 8 9 10
Processing
time(min) 5 6 3 8 7 2 3 5 4 2

Solution:
Step-1:

IE 1101 23
Parallel Machine Problem(Solution)

Job 1 2 3 4 5 6 7 8 9 10
Processing
time(min)
Step-2: 5 6 3 8 7 2 3 5 4 2

IE 1101 24
Parallel Machine Problem(Solution)

Job 1 2 3 4 5 6 7 8 9 10
Processing
time(min)
Step-2: 5 6 3 8 7 2 3 5 4 2

IE 1101 25
Parallel Machine Problem(Solution)
Average flow time = (2+6+14+3+8+15+2+5+10+16)/10
= 8.1 hrs.

IE 1101 26
Sequencing N Jobs on Two Machines: Johnson’s Rule

✓Works with two or more jobs that pass through the same two machines
or work centers
✓Minimizes total production time and idle time

IE 1101 27
Johnson’s Rule

✓List all jobs and times for each work center

✓Choose the job with the shortest activity time. If that time is in the first
work center, schedule the job first. If it is in the second work center,
schedule the job last.
✓Once a job is scheduled, it is eliminated from the list
✓Repeat steps 2 and 3 working toward the center of the sequence

✓Draw gantt chart and calculate the idle time

IE 1101 28
Johnson’s Rule Example

Job Work Center 1 Work Center 2

A 5 2
B 3 6
B E D C A
C 8 4
D 10 7
E 7 12

IE 1101 29
Johnson’s Rule Example
Job Work Center 1 Work Center 2
A 5 2
B 3 6
B E D C A
C 8 4
D 10 7
E 7 12
Time 0 3 10 20 28 33

WC
1 B E D C A

WC
2

IE 1101 30
Johnson’s Rule Example
Job Work Center 1 Work Center 2
A 5 2
B 3 6
B E D C A
C 8 4
D 10 7
E 7 12
Time 0 3 10 20 28 33

WC
1 B E D C A

WC
2 B E D C A

Time➔ 0 1 3 5 7 9 10 11 12 13 17 19 21 22 2325 27 29 31 33 35
IE 1101 31
B E D C A
Johnson’s Rule Example
Job Work Center 1 Work Center 2
A 5 2
B 3 6
B E D C A
C 8 4
D 10 7
E 7 12
Time 0 3 10 20 28 33

WC
1 B E D C A

WC
2 B E D C A

Time➔ 0 1 3 5 7 9 10 11 12 13 17 19 21 22 2325 27 29 31 33 35
IE 1101 32
B E D C A