Job Shop Scheduling (Sequencing)
Some of the rules available for scheduling include:
Earliest due date (Due Date)
Shortest Processing Time (SPT) or Shortest Operation Time (SOT)
Longest Processing Time (LPT) or Longest Operation Time (LOT)
First-In First-Out (FIFO) or First Come First Serve
Last-In First-Out (LIFO)
The job shop scheduling models are used to solve one and two machine job shop problems.
For the one machine problem the available methods are shortest processing time, first
come first serve, due date scheduling
One machine scheduling
Input M/C Output
Consider the following one machine scheduling problem. Six jobs are to be processed on
one machine. The time to process each job is given below as well as due dates.
Job1 Processing time Due Date
A 3days 4
B 5 7
C 4 13
D 7 10
2
E 9 15
F 2 5
Using SPT, Sequence is : F, A, C, B, D, E
Sequence according to SPT
Job1 Processing time Due Date Flow Time Tardiness
F 2 5 2 0
A 3days 4 5 1
C 4 13 9 0
B 5 7 14 7
D 7 10 21 11
E 9 15 30 15
Total 81 34
Average 13.5 5.6667
Flow time. The time at which each job ends is given in a column of flow times. In the
example F is the first one processed and ends after its processing time of 2 days. A is the
second processed and ends after 3 more days at time 5. The last job performed, E, ends
after 30 days.
Page 2 of 12
3
Tardiness or lateness. If due dates are given then the difference between the flow time and
the due date is displayed. This difference will never be below 0. (There is generally no such
thing as early in scheduling.)
Totals. For both the flow time and the lateness the totals are computed and displayed.
Averages. More relevant than the totals are the averages. The average flow time represents
the speed with which jobs leaves the system after they have entered. The average lateness
(tardiness) represents how badly the schedule is performing with respect to our promised
due dates.
NOTE: The average lateness is computed based on all jobs - not just the jobs which are
late. In the example it is 34/6 even though F was processed on time.
Average number of jobs in the system.
This is computed as the total flow time divided by the maximum flow time.
Gantt Chart
F A C B D E
0 15 30
Flow Time
First come first serve
Job1 Processing time Due Date
A 3days 4
Page 3 of 12
4
B 5 7
C 4 13
D 7 10
E 9 15
F 2 5
first come first serve (FCFS) sequence is in this order – A, B, C, D, E and F
Job1 Processing time Due Date Flow Time Tardiness
A 3days 4 3 0
B 5 7 8 1
C 4 13 12 0
D 7 10 19 9
E 9 15 28 13
F 2 5 30 25
Total 100 48
Average 16.67 8
Due date scheduling
Job1 Processing time Due Date
A 3days 4
Page 4 of 12
5
B 5 7
C 4 13
D 7 10
E 9 15
F 2 5
Sequence according to earliest due date : A, F, B, D, C, E
Job1 Processing time Due Date Flow Time Tardiness
A 3days 4 3 0
F 2 5 5 0
B 5 7 10 2
D 7 10 17 7
C 4 13 21 8
E 9 15 30 15
Total 87 32
Average 14.5 5.33
Page 5 of 12
6
A F B D C E
0 15 30
Flow Time
Average flow time in SPT < Average flow time in Due date schedule
Average tardiness in SPT > Average tardiness in due date schedule
Schedule according to slack
Slack is defined as the due date minus the time required to process a job. In order to use slack the
due date must be given. The slack column did not appear before but does now. It is the difference
between the due column and the processing time column. For example, A must be processed by
day 4 but it takes 3 days to process, so there is one day of slack. The jobs are scheduled
according to increasing order of slack. A has the least and is scheduled first while C has the
most (9) and is scheduled last.
Job1 Processing time Due Date Slack
A 3 4 1
B 5 7 2
C 4 13 9
D 7 10 3
E 9 15 6
Page 6 of 12
7
F 2 5 3
Job1 Processing time Due Date Flow Time Tardiness
0
A 3 4 3
1
B 5 7 8
5
D 7 10 15
12
F 2 5 17
11
E 9 15 26
17
C 4 13 30
46
Total 99
7.66667
Average 16.5
Longest Processing Time
The LPT method schedules jobs from longest to shortest. This is typically the worst way to perform
scheduling. LPT yields the sequence E, D, B, C, A, F which is exactly opposite the SPT schedule of
course. This schedule has an average flow time of 21.5. No schedule will have a larger average flow time.
This schedule has 4.3 jobs in the system on average. No schedule will have a larger average number of
jobs in the system
Critical ratio
The critical ratio is defined as (due date -today)/processing time. Jobs are scheduled in ascending
order of the critical ratio. In this example the schedule is Janet, Barry, Sammy, Ernie, Lisa,
Alexis.
Looks at time remaining between current time and due date
Considers processing time as a percentage of remaining time
CR = 1.0 means just enough time
CR > 1 .0 more than enough time
CR < 1.0 not enough time Starting date
Page 7 of 12
8
Job1 Processing time Due Date Critical ratio
A 3 4 (4-0)/3 =1.33
B 5 7 (7-0)/5 =1.4
C 4 13 (13-0)/4 =3.25
D 7 10 (10-0)/7=1.43
E 9 15 (15-0)/9=1.67
F 2 5 (5-0)/2=2.50
Sequence A, B, D, E, F, C
Job1 Processing time Due Date Flow Time Tardiness
3 0
A 3 4
8 1
B 5 7
15 5
D 7 10
24 9
E 9 15
26 21
F 2 5
30 17
C 4 13
106 53
Total
17.6667 8.83333333
Average
Starting day
Job1 Processing time Due Date Critical ratio
A 3 4 (4-3)/3 =0.33
Page 8 of 12
9
B 5 7 (7-3)/5 =0.8
C 4 13 (13-3)/4 =2.5
D 7 10 (10-3)/7=1
E 9 15 (15-3)/9=1.33
F 2 5 (5-3)/2=1
Sequence: A, B, D, F, E, C
Job1 Processing Due Date Flow Time Completio Tardiness
time n date
3 3+2 =5 -1
A 3 4
8 8+2 =10 1
B 5 7
15 17 5
D 7 10
17 19 12
F 2 5
26 28 11
E 9 15
30 32 17
C 4 13
99 45
Total
16.5 7.5
Average
Two Machine Scheduling
Johnson algorithm
Consider the problem below
JOB Typing Duplicating
A 20 19
Page 9 of 12
10
B 43 27
C 37 38
D 62 11
E 80 52
F 12 36
F 25 41
Multi machine scheduling
Two Machine flow Shops
Johnson algorithm
Step O. Initialise A = {1,2, .. . . . N}, A is a set of jobs.
Step1. Select job. If A = Ǿ, stop; otherwise, find k =arg minkєA{pi1 or pi2}
Step2. Assign job k if minimum is on machine 1, place k as early as possible in S sequence S. If
minimum is on machine 2, place k as late as possible in S. A = A –k. Go to 1.
Job Shop scheduling
The general job shop problem is to schedule production times for N jobs on M machines.
From each job we have knowledge of the sequence of machines required by the job and the processing
time on each of those machines. Due dates may also be known
The objective :
- minimise make span for completion of all jobs
- minimise the number of tardy jobs
- minimizing the average flow time. Or
- or achieving some weighted combination of the three.
Three jobs are to be scheduled in a 4 machine flow shop. Job data are summarized in the table below
Job Processing Times
Page 10 of 12
11
Machine
Job 1 2 3 4
A 2 4 5 2
B 3 7 4 2
C 10 5 1 2
For each machine, find a lower bound on make-span.
Construct a Gantt chart for job processing sequence A, C, B
Calculate the make-span
M/c
1 A=2 C=10 B=3
2 A=4 C=5 B=7
C= B=4
3 A=5 1
4 A=2 C=2 B=2
Time (days)
- Notice after processing job A B and C machine 1 remain idle
- In each of the machine there are N! possible job sequence making a total of (N!) M possible
solutions
- Makespan =30 days
Page 11 of 12
12
Sequence:A,B,C
M/c
1 A=2 B=3 C=10
2 A=4 B=7 C=5
3 A=5 B=4 C=
1
4 A=2 B=2 C=2
Time (days)
Page 12 of 12
