CH 6 Scheduling
CH 6 Scheduling
CH 6 Scheduling
Chapter 2: Scheduling
2022
1
After viewing this presentation, you
should be able to:
Explain why production scheduling must be done
by every organization whether it manufactures or
provides services.
Discuss the application of the loading function.
Draw a Gantt chart and explain its information
display.
Describe the role of sequencing and how to apply
sequencing rules for one facility and for more than
one facility. 2
After viewing this presentation, you
should be able to (continued)
Classify scheduling problems according to
various criteria that are used in practice.
Explain the purpose of priority sequencing rules.
Describe various priority rules for sequencing.
Apply Johnson’s rule to the 2-machine flow
shop problem.
Analyze dynamic scheduling problems.
3
Loading, Sequencing and Scheduling
4
Loading, Sequencing and Scheduling
(continued)
5
Loading
6
Loading vs. Aggregate Planning
The backlog is generally much larger than the work in process, which can
be seen on the shop floor.
8
Sequencing
Sequencing models and methods follow the discussion of loading models and
methods.
Sequencing establishes the order for doing the jobs at each facility.
Sequencing reflects job priorities according to the way that jobs are arranged in
the queues.
Say that Jobs x, y, and z have been assigned to workstation 1 (through loading
function).
Jobs x, y, and z are in a queue (waiting line). Sequencing rules determine which
job should be first in line, which second, etc.
9
Sequencing (continued)
A good sequence provides less waiting time, decreased delivery delays, and
better due date performance.
There are many other costs associated with the various orderings of jobs, for
example, set up cost and in-process inventory costs.
The three jobs consist of 4, 3, and 4 operations respectively; and there are
four machines - one machine of each type. We designate them as M1, M2,
M3, and M4 based on their categories.
The operations for job A are designated as A1, A2, A3, and A4. The
operations of job B are designated as B1, B2, and B3. Similarly the four
operations of job C are designated as C1, C2, C3, and C4.
13
Scheduling Example (continued)
Each job is characterized by its routing that specifies the information
about the number of operations to be performed, the sequence of these
operations, and the machines required for processing these operations.
The times required for processing these operations are also required for
developing a production schedule.
14
Scheduling Example - Data
Operation Machine Processing Time
Job
The table on right hand side (RHS) gives the data for Number Number (Days)
this example. A A1 M1 5
A2 M3 3
The table gives the machine required for each A3 M4 7
A4 M2 4
operation of each job. For example, the first
operation of job A, A1, is processed on machine M1; B B1 M2 2
second operation, A2, is processed on machine M3 B2 M3 6
and so on. B3 M4 8
15
Scheduling Example – Objective
Function
16
Scheduling Example Solution – Gantt Chart
One of the schedules for this example is presented below in the form of a
Gantt Chart.
The Gantt chart, for each machine, shows the start and finish times of all
operations scheduled on that machine.
17
Scheduling Example - Alternative schedules
Several alternative schedules can be generated for this example.
The schedules differ in the order in which the jobs are processed on the four
machines. Three of these schedules are:
o The first schedule orders jobs as: A first, then B and then C (A-B-C).
o The second schedule orders jobs as: B first, then A, and then C (B-A-C).
o The third schedule orders jobs as: C first, then A, and then B (C-A-B).
The Gantt charts for these schedules are shown in next slide.
The values of make-span for these three schedules are 25, 27 and 30 days
respectively. Schedule A-B-C is the best of these three schedules.
18
Scheduling Example - Alternative
Schedules (continued)
Time (Days)
Sequence A-B-C
M1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
A1 A1 A1 A1 A1 C1 C1 C1 C1 (Make-span = 25
M2 B1 B1 C2 C2 C2 C2 C2 C2 A4 A4 A4 A4 days)
M3 A2 A2 A2 B2 B2 B2 B2 B2 B2 C3 C3 C3 C3 C3 C3 C3 C3
M4 A3 A3 A3 A3 A3 A3 A3 B3 B3 B3 B3 B3 B3 B3 B3 C4 C4
Sequence B-A-C
(Make-span = 27
days)
Time (Days)
Sequence C-A-B
M1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
C1 C1 C1 C1 A1 A1 A1 A1 A1
(Make-span = 30
M2 B1 B1 C2 C2 C2 C2 C2 C2 A4 A4 A4 A4
days)
M3 B2 B2 B2 B2 B2 B2 A2 A2 A2 C3 C3 C3 C3 C3 C3 C3 C3
M4 A3 A3 A3 A3 A3 A3 A3 C4 C4 B3 B3 B3 B3 B3 B3 B3 B3
19
Scheduling Example - Alternative
Schedules (continued)
20
Scheduling Example - Assumptions
• Sequence of machines
• Number of machines
• Processing times
• Job arrival time
• Objective functions
22
Sequence of Machines
Flow Shops
Job Shops
23
Flow Shop
In a flow-shop , processing of all jobs require machines in the same order.
Operation Operation Operation Operation Machine for Machine for Machine for Machine for
Job
#1 #2 #3 #4 Operation # 1 Operation # 2 Operation # 3 Operation # 4
A A1 A2 A3 A4 M1 M3 M4 M2
B B1 B2 B3 B4 M1 M3 M4 M2
C C1 C2 C3 C4 M1 M3 M4 M2
24
Job Shop
In a job shop the sequence of machines will be mixed,
that is, the jobs may require machines in different
sequences.
Operation Operation Operation Operation Machine for Machine for Machine for Machine for
Job
#1 #2 #3 #4 Operation # 1 Operation # 2 Operation # 3 Operation # 4
A A1 A2 A3 A4 M1 M3 M4 M2
B B1 B2 B3 M2 M3 M4
C C1 C2 C3 C4 M1 M2 M3 M4
25
Number of Machines
Based on the number of machines, the
scheduling problems are classified as:
26
Processing Times
Deterministic: If processing times of all jobs
are known and constant the scheduling
problem is called a deterministic problem.
Minimize make-span
Minimize average flow time (or job completion time)
Average number of jobs in the system
Minimize average tardiness
Minimize maximum tardiness
Minimize number of tardy jobs
29
Objective Functions (continued)
Minimizing make span is relevant for two or more machines.
In this presentation we will discuss the scheduling rule for static and deterministic
flow shop problems consisting of two machines where the objective is to minimize
make-span.
The other five objectives can be used for any number of machines, both deterministic
and probabilistic processing times, and for static as well as dynamic problems.
However, we will study these objective functions for a single machine, deterministic
and static problems.
The scheduling rule for job shops and for more than three machines are complex and
beyond the scope of this presentation.
30
Example: 2-Machines Flow Shop
Consider a problem with five jobs (A, B, C, D, and E); and two
machines designated as M1 and M2.
All five jobs consist of two operations each. The first operation of
each job is processed on machine M1; and the second operation is
processed on machine M2.
The next slide gives the machines required for each job; and the
processing times for each operation of each job.
31
Data for a 2-Machine Flow Shop
32
Scheduling Objective
The scheduling objective is to find an optimal sequence that gives the order in
which the five jobs will be processed on the two machines.
Once we know a sequence, the time to complete all jobs can be determined. This time
is called the schedule time, or the make-span. The optimal sequence is the one that
minimizes make-span.
For example, A-B-C-D-E is a sequence order that tells us that A is the first job to be
processed; B is the second job and so on. E is the last job to be processed. Is it
optimal?
33
Number of Sequences
For this 5-job problem there are 120 (5!) different sequences. For
a six-job problem, the number of sequences will be 720 (6!).
Let us find the make-span for one of these sequences, say A-B-
C-D-E. We will draw a Gantt chart to find make-span.
34
Gantt Chart
Sequence A-B-C-D-E
The Gantt chart for the sequence A-B-C-D-E is given below. We are assuming
that the sequence is the same on both machines.
Our objective is to identify the sequence that minimizes the value of make-span.
Time (Days)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
M1 A1 A1 A1 A1 A1 A1 A1 A1 B1 B1 B1 B1 B1 C1 C1 C1 C1 C1 C1 D1 D1 D1 D1 D1 D1 D1 E1 E1 E1 E1
M2 A2 A2 A2 B2 B2 B2 B2 B2 B2 B2 C2 C2 C2 C2 C2 C2 C2 C2 C2 D2 E2 E2 E2 E2 E2 E2
35
Identifying the best sequence
There may be multiple optimal sequences.
We will study Johnson’s rule that identifies one of these
optimal sequence.
36
Johnson’s Rule
to Minimize Make-span
We use the following four step process to find
the optimal sequence.
38
Johnson’s Rule (continued)
Johnson’s rule makes the following assumptions:
39
Iteration 1
Operation # 1
Operation # 2
M2.
(Days)
(Days)
Job
Step 3: Since the machine identified at
Step 2 is machine M2, job D will be
assigned to the last available sequence A A1 A2 M1 M2 8 3
position which is position 5; and the B B1 B2 M1 M2 5 7
C C1 C2 M1 M2 6 9
resulting partial sequence is given D D1 D2 M1 M2 7 1
below.
Position 1 Position 2 Position 3 Position 4 D
E E1 E2 M1 M2 4 6
40
Iteration 2
Step 1: The next minimum time is
Operation # 1
Operation # 2
Step 2: The job is A and the
(Days)
(Days)
Job
machine is M2.
Step 3: The job A will be assigned
to the last available schedule
position, which is position 4. After A
B
A1
B1
A2
B2
M1
M1
M2
M2
8
5
3
7
assigning job A to position 4, the C C1 C2 M1 M2 6 9
D D1 D2 M1 M2 7 1
partial sequence is given below.
Scheduled
E E1 E2 M1 M2 4 6
41
Iteration 3
Step 1: The minimum time is 4.
Operation # 1
Operation # 2
machine is M1.
(Days)
(Days)
Job
Step 3: The job E will be assigned
to the first available schedule
position, which is position 1. The
partial sequence after assigning job A
B
A1
B1
A2
B2
M1
M1
M2
M2
8
5
3
7
Scheduled
E Position 2 Position 3 A D E E1 E2 M1 M2 4 6
42
Iteration 4
Step 1: The minimum time is 5.
Operation # 1
Operation # 2
machine is M1.
(Days)
(Days)
Job
Step 3: The job B will be assigned
to the first available schedule
position, which is position 2. The
partial sequence after assigning job A
B
A1
B1
A2
B2
M1
M1
M2
M2
8
5
3
7
Scheduled
43
Iteration 5
The only unscheduled job at this
Operation # 1
Operation # 2
the remaining unassigned position
(Days)
(Days)
Job
3.
E B C A D
44
Finding Make-span
The sequence E-B-C-A-D identified by Johnson’s
rule guarantees the minimum value of make-
span.
However, Johnson’s rule does not give the value of
make-span. It only identifies the best sequence.
The value of make-span is obtained either by
drawing the Gantt chart or a computerized
algorithm can be developed.
The Gantt chart for this optimal sequence is given
in the next slide.
45
Sequence E-B-C-A-D
The Gantt chart for the sequence E-B-C-A-D
is given below. The value of make-span is 31
days.
Time (Days)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
M1 E1 E1 E1 E1 B1 B1 B1 B1 B1 C1 C1 C1 C1 C1 C1 A1 A1 A1 A1 A1 A1 A1 A1 D1 D1 D1 D1 D1 D1 D1
M2 E2 E2 E2 E2 E2 E2 B2 B2 B2 B2 B2 B2 B2 C2 C2 C2 C2 C2 C2 C2 C2 C2 A2 A2 A2 D2
46
Multiple Sequences
It may be noted that multiple optimal
sequences are possible for a given problem. It
means that several sequences can have the
same minimum value of make-span.
For example, for the problem studied in
previous slides, the sequence E-C-B-A-D also
gives a make-span of 31 days. TRY IT.
However, Johnson’s rule identifies only one of
these sequences.
47
Breaking Ties
It might happen at Step 1, that there are more than one
minimum times. In such a situation, which job should be
picked up for assignment.
We will discuss three different cases of these ties.
Case 1: Minimum time is on both machines but for different
jobs.
Case2: Minimum time is on the same machine but for different
jobs.
Case 3: Minimum time is on both machines but for the same
job.
48
Ties: Case 1 - Data
Consider the problem given below. The minimum time is 1 but occurs at two
places – Job A at M1 and Job D at M2.
Time for
Machine for Machine for Time for
Operation Operation Operatio
Job Operation # Operation # Operation #
#1 #2 n#2
1 2 1 (Days)
(Days)
A A1 A2 M1 M2 1 3
B B1 B2 M1 M2 5 7
C C1 C2 M1 M2 6 9
D D1 D2 M1 M2 7 1
E E1 E2 M1 M2 4 6
49
.
In either case, the resulting partial sequence after both A and D are scheduled, is
given below.
The scheduling algorithm continues until all jobs are scheduled. The final
sequence is also shown below.
50
Ties: Case 2 - Data
Consider the problem given below. The minimum time is 1 but occurs at two places – Job B at
M2 and Job D at M2.
Time for
Machine for Machine for Time for
Operation Operation Operatio
Job Operation # Operation # Operation #
#1 #2 n#2
1 2 1 (Days)
(Days)
A A1 A2 M1 M2 8 3
B B1 B2 M1 M2 5 1
C C1 C2 M1 M2 6 9
D D1 D2 M1 M2 7 1
E E1 E2 M1 M2 4 6
51
Ties: Case 2 – Solution
The ties are broken at random.
In this case, two different partial sequences will result based on which job is
selected first. These partial sequences are shown below.
Time for
Machine for Machine for Time for
Operation Operation Operatio
Job Operation # Operation # Operation #
#1 #2 n#2
1 2 1 (Days)
(Days)
A A1 A2 M1 M2 8 3
B B1 B2 M1 M2 5 7
C C1 C2 M1 M2 2 2
D D1 D2 M1 M2 7 9
E E1 E2 M1 M2 4 6
53
Ties: Case 3 - Solution
The ties are broken at random.
In this case, two different partial sequences will result based on which
combination is selected first. These partial sequences are shown below.
54
Comments About Ties
In general all three cases of ties may exist in a given problem.
55
Example with Multiple Ties
Johnson’s rule will give four different sequences for this problem because of various ties.
TRY IT.
Time for
Machine for Machine for Time for
Operation Operation Operatio
Job Operation # Operation # Operation #
#1 #2 n#2
1 2 1 (Days)
(Days)
A A1 A2 M1 M2 2 3
B B1 B2 M1 M2 5 7
C C1 C2 M1 M2 2 2
D D1 D2 M1 M2 8 9
E E1 E2 M1 M2 4 2
56
Single Machine Scheduling
59
59
Example
60
60
First Come First Served (FCFS)
The table on RHS gives answers by First Come First Served
using the FCFS rule. The order of Completion
Job Time Due Date Tardiness
processing is A, B, C, D, and E. Time
A 17 45 17 0
B 12 35 29 0
A is the first job to be processed and C 22 27 51 24
will be completed at time 17. Its due D 18 54 69 15
E 26 47 95 48
date is 45. So job A is not late (tardy);
tardiness is zero.
Tardiness = Completion Time – Due Date
Job B starts after job A, and is Make it zero if you get a negative value.
61
FCFS: Calculation of Objective
Functions
Average Completion Time: Add completion
times of all jobs and divide by the number of
jobs (261/5). It is 52.5.
62
62
Shortest Processing Time (SPT)
63
63
Earliest Due Date (EDD)
64
64
Dynamic Scheduling Problems
The new jobs (production orders, customers, cars etc.) keep on coming into
the system; and the schedule needs to integrate the new arrivals when an
updated schedule is prepared.
65
65
Example – Dynamic Scheduling
Problem
Consider a single machine problem for which
the data are given on RHS. Data for Dynamic Problem
There are five jobs A, B, C, D, and E that are Job Time (Days)
waiting to be processed.
A 17
Suppose Shortest Processing Time (SPT) rule B 12
is being used. C 22
D 18
SPT sequence is given on RHS.
E 26
B is the first job to be processed. SPT Sequence
66
66
Example – Dynamic Scheduling Problem
(continued)
After job B has been processed, there are six jobs (A,
C, D, E, F, and G) that are waiting to be processed.
Since the scheduling rule is SPT, the job with the SPT Sequence - New
minimum processing time from among the jobs that
are waiting to be processed will be scheduled next. Job Time (Days)
Table 3 gives the schedule at this time.
F 8
The next job is F. This will be completed at time 20
A 17
(12+8) where 12 is the completion time of job B. If
more jobs arrive in the system while F is being D 18
processed, they will be integrated with the current G 20
jobs and a new schedule will be developed.
C 22
These are called dynamic problems since the schedule E 26
is continuously updated. Dynamic situations are faced
in multiple machines problems also.
67
67
Objective Functions – Dynamic Scheduling
Problems
Objective functions for dynamic problems are defined in the same way as for
single machine static problems.
The values of completion time and tardiness of each job are recorded; and
the values of the objective functions can be calculated at any time based on
the number of jobs completed at that time.
68
68
Thank you.
69