Page 203 - DCOM303_DMGT504_OPERATION_RESEARCH

Operations Research

Notes Self Assessment

Give one word answer for the following:
1. The time interval between starting the first job and completing the last job including the
idle time (if any) in a particular order by the given set of machines.

2. Order or sequence in which machines are required for completing the job.
3. The condition to be satisfied in which the order of jobs are to be processed on given
machines.

10.2 Types of Sequencing Problems

Type I: Processing n jobs through two machines
Type II: Processing n jobs through three machines
Type III: Processing n jobs through m machines

Type IV: Processing two jobs through m machines

Notes In this unit we will only discuss the type I and II by Johnson’s Rule. Type III and IV
are complex problems of sequencing and are also solved using extension of Johnson’s
Rule.

10.3 Algorithm for Sequencing Problems

10.3.1 Type I: Processing n Jobs through Two Machines

Considering n jobs (say 1,2, …n) to be processed on two machines A and B, in the order AB. The
processing time is t t t and t , t ……. t as represented in Table 10.1 below:
11, 12,….. ln 12 22 2n
Table 10.1: Sequencing Problem

Machines Job
1 2 3 …. n
A t11 t12 T13 …. tln
B t21 t22 T23 …. t2n

Step 1: Check the processing order, i.e., in the order AB or BA. If it is in the order AB, then the first
job would be performed on machine A and then on machine B. If the order is of BA, interchange
the rows with machine B in row l and machine A in row 2.
Step 2: From the given processing time, select the least processing time available on both
machines A and B. If the least processing time exists in row l, place that job at the beginning of
the sequence table (i.e., the sequence is from left to right of the sequence table). If the least
processing time is on row 2, place the job at the end of sequence table (i.e., the sequence is from
right to left of the sequence table).

Note: If there are two least processing times for machine A and machine B, priority is given for
the processing time which has lowest time of the adjacent machine.

198 LOVELY PROFESSIONAL UNIVERSITY