Sequencing Problem
Kaushal Patel
Department of Mathematics
Veer Narmad South Gujarat University, Surat
Introduction
• The short - term schedules shows an optimal
sequence and time in which jobs are processed as
well as show timetable for job equipment,
people, materials, facilities and all other resources
that needed to support the production plan
• The schedules should use resources efficiently to
give low costs and high utilization
• Minimizing customer wait time for a product,
meeting promised delivery dates, keeping stoke
levels low, giving preferred working pattern,
minimizing waiting time of patients in a hospital
for different types of test
General sequencing Problem
• Let there be ‘
n
’ jobs to be performed one at a time
on each of ‘m’ machines.
• The sequence of the machine in which each job
should be performed is given.
• The actual expected time required by the jobs on
each of the machines is also given
• To find the sequence which minimize the total
elapsed time between the start of the job in the
first machine and the completion of the last job on
the last machine
Definitions
• Number of Machine:The number of machine refer to the number
of service facilities through which job must pass before it is
assumed to be completed
• Processing time: it is the time required by a job on each machine
• Processing order: it refers to the order in which machines are
required for completion of the job
• Idle time for machine: it is a time for which a machine does not
have a job to process
• Total elapsed time: it is the time interval between starting the
first job and completing the last job including idle time in order
by the given set of machine
• No passing rule: It refers to the rule of maintaining the order in
which jobs are to be processed on given machines
Algorithm of 2-machine m-jobs
Step-1 List the jobs along with their processing times on
each machine in a table as shown below:
Step-2 Examine the columns for processing time on each
machine M1 & M2 and fine the smallest processing time
in each column ie. Find Min(T1,j ,T2,j)
Step-3 If the smallest processing time is on Machine M1
then place the job in the first available position in the
table. If the processing time is on machine M2 then
place the job in the last available position in the
sequence
Processing time on
machine
1 2 3 … N
M1 T1
1
T1
2
T1
3
… T1n
M2 T2
1
T2
2
T2
3
… T2n
Step-4 If there is a tie in the selecting the minimum
(1) Minimum along processing time is in same for the
machine ie. Min(t1k,t2r)=t1k=t2r then process the kth job first
then the rth job last
(2) if the tie for the minimum occurs among processing
time t1j on machine M1 only, then select the job
corresponding to the smallest job subscript first
(3) if the tie for the minimum occurs among processing
time t2j on machine M2 only, then select the job
corresponding to the smallest job subscript last
Algorithm of 2-machine m-jobs
Step-5 Calculate the ideal time for machine M1 &M2
(a) Ideal time for machine M1= (total elapsed time) –
(time when the last job in a sequence finishes on
machine M1
)
(b) Ideal time for machine M2 = time at which the first
job in a sequence finishes on machine M1 – total
[(time when the jth job in a sequence starts on
machine M2
) – (time when the (j-1)th job in a
sequence finishes on machine M2
)]
Step-6 The total elapsed time to process all jobs
through two machine is given by time when the nth
job in a sequence finishes on machine M2
Algorithm of 2-machine m-jobs
Example
• Find the sequence that minimize the total elapsed
time required to complete the tasks on two
machine
task a b c d e f g h I
M1 2 5 4 9 6 8 7 5 4
M2 6 8 7 4 3 9 3 8 11
Solution
Task a b c d e f g h I
M1 2 5 4 9 6 8 7 5 4
M2 6 8 7 4 3 9 3 8 11
task a
minimum
Solution
Task b c d e f g h I
M1 5 4 9 6 8 7 5 4
M2 8 7 4 3 9 3 8 11
task a g e
minimum
Solution
Task b c d f h I
M1 5 4 9 8 5 4
M2 8 7 4 9 8 11
task a c I d g e
minimum
Solution
Task b f h
M1 5 8 5
M2 8 9 8
task a c I b h f d g e
minimum
Example
• Following table shows the machine time for
five jobs to be processed on two different
machine
task a b c d e
M1 3 7 4 5 7
M2 6 2 7 3 4
Example
• A manufactured company processes 6 different
jobs on two machine A and B. Number of unit of
each job and its processing time on A and B are
given below
Job Unit of each job Processing time
Mach. - A Mach. – B
1 3 5 8
2 4 16 7
3 2 6 11
4 5 3 5
5 2 9 7.5
6 3 6 14
Jobs unit Machine - A Machine - B
4 5 0-3, 3-6, 6-9, 9-12, 12-15 0 3-8, 8-13,13-18,18-23,23-28 3
1 3 15-20, 20 - 25, 25 -30 0 28-36, 36-44, 44-52 0
3 2 30-36, 36-42 0 52-63, 63-74 0
6 3 42-48, 48-54, 54-60 0 74-88,88-102,102-116 0
5 2 60-69,69-78 0 116-123.5, 123.5-131 0
2 4 78-94,94-110,110-126,
126-142
17 131-138,138-145,145-
152,152-159
0
Idle time for machine M1
(0+0+0+0+0+17)
19 for M2 (3+0+0+0+0+0) 3
Total elapsed time is 159
1 3 5 8
2 4 16 7
3 2 6 11
4 5 3 5
5 2 9 7.5
6 3 6 14
3-machines m-jobs
• Extension of 2-machine m-jobs
• Each job is to be processed through three machine
M1
, M2
, M3
. In the specific order
• An optimal solution to this problem can be obtain if
(1) the minimum processing time on machine M1
is at
last as great as the maximum processing time on
machine M2
ie. min t1j >= max t2j
(2) the minimum processing time on machine M3 is
at last as great as the maximum time on machine M2
ie. Min t3j >= max t2j
Algorithm of 3-machine m-jobs
Step-1 Examine the processing time of given
jobs on all three machines and if either one or
both the above condition holds then
Step-2 introduce two fictitious machine G & H
(1) tgj=t1j+t2j and thj=t2j+t3j
Step-3 determine the optimum sequence of jobs
for 2-machine m-jobs discuss earlier
Example
• Find the sequence that minimize the total time
required to complete the tasks on three machine in
order M1M2M3
Task a b c d e
M1 8 10 6 7 11
M2 5 6 2 3 4
M3 4 9 8 6 5
Solution
• Here min(tM1,j)=6; min(tM3,j)=4; max(tM2,j)=6
• Since min(tM1,j) >= Max(tM2,j) for all j
• The given problem can be converted in to 5-
job 2-machine
• The processing time on two machine G and H
can be determined by the relationships
tGj=tAj+tBj
tHj=tBj+tCj
• The processing time for the new problem
are given below
• When the algorithm describe for n jobs on
two machines is applied to this problem, the
optimum sequence so obtain is given by
task A B C D E
G 8+5=13 10+6=16 6+2=8 7+3=10 11+4=15
H 5+4=9 6+9=15 2+8=10 3+6=9 4+5=9
Task C B E A D
• The total minimum elapsed time is
• The total elapsed time is 51 hours. The ideal
time for machine A, B, C is 9 (51-42) hours
, 31 =((51-45)+(6-0)+(16-8)+(27-22)+(35-
31)+(42-40))hours, and 19 =((45-44)+(40-
36)+(22-16) +(8-0)), hours respectively. time In Time Out time In Time Out time In Time Out
3 0 6 6 8 8 16
2 6 16 16 22 22 31
5 16 27 27 31 31 36
1 27 35 35 40 40 44
4 35 42 42 45 45 51
job sequence Machine A Machine B Machine C
n-machines m-jobs
• Extension of 2-machine m-jobs and 3-machine m-jobs
• Each job is to be processed through three machine M1
,
M2
, M3…Mn
. In the specific order
• An optimal solution to this problem can be obtain if
(1) the minimum processing time on machine M1
is at
last as great as the maximum processing time on
machine M2
,…, Mn-1
ie. min {t1j} >= max {tij }
(2) the minimum processing time on machine Mn
is at last
as great as the maximum time on machine M2
,…, Mn-1
ie. Min {tnj} >= max {tij}
Algorithm of n-machine m-jobs
Step-1 Examine the processing time of given
jobs on all n-machines and if either one or
both the above condition holds then
Step-2 introduce two fictitious machine G & H
(1) tgj=t1j+t2j+…+ tn-1j and thj=t2j+t3j +…+ tnj
Step-3 determine the optimum sequence of jobs
for 2-machine m-jobs discuss earlier
m1 m2 m3 m4 m5
A 7 5 2 3 9
B 6 6 4 5 10
C 5 4 5 6 8
D 8 3 3 2 6
job machine
Example
• Find the sequence that minimize the total time
required to complete the tasks on five machine in
order M1,M2,M3,M4
,M5. Also find the total elapsed
time
m1 m2 m3 m4 m5
A 7 5 2 3 9
B 6 6 4 5 10
C 5 4 5 6 8
D 8 3 3 2 6
job machine
MINIMUM
MAXIMUM
Since the condition min(tM5,j)>=max(tM2,j,tM3,j,tm4,j) is satisfy
Therefore the given problem can be converted into a four jobs and
Two machine problem as G and H
• The processing time for the new problem
are given below
• When the algorithm describe for n jobs on
two machines is applied to this problem, the
optimum sequence so obtain is given by
task A B C D
G 7+5+2+3
=17
5+6+4+5=
21
5+4+5+6
=20
8+3+3+2
=16
H 5+2+3+9
=19
6+4+5+10
=25
4+5+6+8
=23
3+3+2+6
=14
Task A C B D
M1 M2 M3 M4 M5
A 0-7 7-12 12-14 14-17 17-26
C 7-12 12-16 16-21 21-27 27-35
B 12-18 18-24 24-28 28-33 35-45
D 18-26 26-29 29-32 33-35 45-51
MACHINE JOB SEQUENCE
•The total elapsed time is 51 hours. The ideal
time for machine M1
,M2
,M3
,M4
and M5
is
A B C D E F
Machine M1 8 3 7 2 5 1
Machine M2 3 4 5 2 1 6
Machine M3 8 7 6 9 10 9
JOB SEQUENCE job
1 2 3 4 5 6
Turning 3 12 5 2 9 11
Threading 8 6 4 6 3 1
knurling 13 14 9 12 8 13
JOB SEQUENCE job
M1 M2 M3 M4 M5
A 6 4 1 2 8
B 5 5 3 4 9
C 4 3 4 5 7
D 7 2 2 1 5
MACHINE JOB SEQUENCE

Edit

Pub: 01 Jan 2022 02:40 UTC

Views: 115