Scribd
Upload
15 views12 pages

Flowshop Scheduling

Uploaded by

Gavesha Silva
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
15 views12 pages

Flowshop Scheduling

Uploaded by

Gavesha Silva
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 12

Flow Shop Scheduling

• The flow shop scheduling problem can characterized as


follows
• 1. A set of multiple operations jobs are available for
processing at time zero (each job requires m
operations and each job requires a different machine
• 2. Set up times for the operations are sequence
independent and are included in processing times
• 3. Job descriptors are known in advance
• 4. m different machines are continuously available
• 5. Each individual operations of jobs is processed till its
completion without a break
Johnson’s Algorithm( n Jobs , 2
machines)
• Step 1. Find the minimum time among machine 1
and machine 2
• Step2. If the minimum time occurs in the first
machine place the job in the first available
position in the sequence
• Step3. If the minimum occurs in the second
machine , place the job in the last available
position in the sequence
• Step3. Remove the assigned jobs from the
sequence and go to step 1 until all positions in
the sequence are filled
Extension of Johnson’s algorithm to
three machines
• If Min Ti1 greater than or equal to Max Ti2
• OR

• If Min Ti3 greater than or equal to Max Ti2 , the


concept of the johnson’s method is explained in
the following example . Reduce the problem in to
two machine problem

•
Time Hours
Job Machine 1 - Machine 2 – Machine 3 - Processing
Processing time Processing time Time
1 8 5 4
2 10 6 9
3 6 2 8
4 7 3 6
5 11 4 5
• Minimum of Machine 1= 6 which is equal to
Maximum of Machine 2. Therefore
applicability condition is satisfied.
• Can apply extension of Johnson’s algortithm.
Job Machine A Machine B
1 13 9
2 16 15
3 8 10
4 10 9
5 15 9

3 2 5 1 4
Machine1 Machine2 Machine 3
Job In Out In Out In Out Idle M2 Idle M3
3 0 6 6 8 8 16 6 8
2 6 16 16 22 22 31 8 6
5 16 27 27 31 31 36 5 0
1 27 35 35 40 40 44 4 4
4 35 42 42 45 45 51 2 1
• Makespan = 51 Hours
• Idle Time = Idle M2+Idle M3
• = 25+19= 44Hours
Job Shop Scheduling
• n jobs , m machines and jobs different
sequences
• Can not apply johnson’s method.
Job shop Scheduling
Processing time in Hours
Operation
Job 1 2 3
1 2 3 4
2 4 4 1
3 2 2 3
4 3 3 1

Routing
Operation
Job 1 2 3
1 1x 2x 3x
2 3x 2x 1x
3 2x 3x 1x
4 1x 3x 2x
(i,j,k) = (job, operation, machine)
10 13
2 5
M1 (1,1,1) (4,1,1) (2,3,1) (3,3,1)

5 9 10

M2 (3,1,2) (1,2,2) (2,2,2) (4,3,2)

M3 (2,1,3) (3,2,3) (1,3,3)


(4,2,3)

4 6 9 13

Make Span =13 H


Idle time =4 H

You might also like