USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

Special case of traveling sales man problem

Example 7.14

Sequencing problem as assignment problem

Special case of traveling sales man problem

The basic difference between the assignment and sequencing problem is that schedule in case of sequencing problem, cannot return to its original point until all the jobs have been completed. Therefore solving sequencing problem is more difficult than the assignment problem. Since both types of problems have certain common features, sequencing: problems can be solved as assignment problem with some modifications.

Traveling salesman problem is a typical sequencing problem where the salesman is expected to visit all the places before corning back to the starting point and complete the journey in minimum time. The following steps explain the procedure adopted to solve this type of sequencing problem.

Step I.

(i)                           Reduce the problem first by rows and then by columns.

(ii)                        If zero cells in the matrix are so placed that they represent a feasible sequence for the jobs, this is taken as optimal solution of the sequencing problem

Step II. If the zero cells in the matrix are-not placed in such a manner that feasible solution can be determined, then the solution is further improved till a lower cost schedule is found, If the zero cells do not give the optimal sequence then next higher cells may have to be considered for getting optimal sequence.

Example 7.15. A traveling salesman has planned to visit to 5 cities. He would like to start from a particular city, visit each city once and then return to the city from where he had started. The traveling cost (Rs.) for each city, is given below.

To

From

A

B

C

D

E

A

7

5

3

5

B

7

8

4

3

C

7

8

6

2

D

3

4

6

2

E

5

3

2

2

 

In what sequence the salesman should visit all the cities in order to minimize the total travelling cost?

Sol. Step I. Row reduction reduced matrix is as follows.

4

3

1

3

4

6

2

1

2

5

4

0

0

1

4

0

2

0

0

0

 

Total reduction in travel cost = R1+ R2 + R3 + R4 + R5

And lower bound = 3 + 3 + 2 + 2 + 2 = 12

Step II, By column Reduction reduced method we get the following matrix.

 

3

2

0

2

3

5

2

0

2

5

4

0

0

1

4

0

2

0

0

0

 

Total reduction in travel cost = C1 + C2= 1 + 1 = 2

and the lower bound = 12 + 2 = 14.

Step III. By moving zero assignments we get

 

3

2

0

2

3

5

2

0

2

5

4

0

0

1

4

0

2

0

0

0

 

As the schedule is not completed, we deduce minimum uncovered value lout of all uncovered and adding it at the intersection of lines we get. Making assignments and again moving same column and drawing parallel lines through unmarked rows and marked columns, we have (Lower bound is 14 + 1 = 15).

We can see the schedule is still not complete, let us deduct the minimum uncovered value lout a uncovered values and add it at intersection of lines and lower bound is 15 + 1 = 16. Now the assignment becomes.

1

0

0

2

2

3

1

0

1

3

4

0

0

0

3

1

3

0

0

2

 

The schedule is still not complete. Again let us deduct the minimum value lout of uncovered element and add it at the intersection of lines we get the improved matrix and the lower bound is 16 + 1 = 17.

From the above, we get two alternatives of optimal sequence

(a) A → C → E → B → 0 → A Travelling cost = 5 + 2 + 3 + 4 + 3 = 17

(b) A → 0 → B → E → C → A

3+4+3+2+5=17

Example 7.16 Use geographical method to minimise time added to process the following jobs on the machines shown i.e. for each machine find the job which should be done first. Also calculate the total time elapsed to complete both the jobs.

Job 1 Sequence Time

A

B

C

D

E

3

4

2

6

2

Job 2 Sequence Time

B

C

A

D

E

5

4

3

2

6

Sol. The information provided in the problem can be used to draw the following diagram. The shaded area are of the overlap and need to be avoided. 

Fig. 7.6

The path that minimises the idle time for Job 1 is an optimal path. Also the ideal (optimal) path should minimise the idle time for Job 2. For working out the elapsed time, we have to add the idle time for either of two jobs to that time which is taken for processing of that job. It can be seen that idle time for the chosen path for Job 1 is 5 hours and for Job 2 it is 2 hours, the elapsed time can be calculated as

Processing time for Job 1 + idle time for Job I = 17 + (2 + 3) = 22 hours

Processing time for Job 2 + idle time for Job 2 = 20 + 2 = 22 hours,

REVIEW

  1. 1.   What is no passing rule in a sequencing algorithm?
  2. 2.   Explain the four elements that Characterize a sequencing problem.
  3. 3.   Explain the principal assumptions made while dealing with sequencing problems.
  4. 4.   Describe the method of processing ‘n’ jobs through two machines.
  5. 5.   Give Johnson’s procedure for determining an optimal sequence for processing n items on two machines. Give justification of the rules used in the procedure.
  6. 6.   Explain the method of processing ‘m’ jobs on three machines A, B, C in the order ABC.
  7. 7.   Explain the graphical method to solve the two jobs m-machines sequencing problem with given technological ordering for each job. What are the laminations of the method?
  8. 8.   A Company has 8 large machines which receive preventive maintenance. The maintenance team is divided into two crews A and B Crew A takes the machine ‘Power’ and replaces parts according to a given maintenance schedule. The second crew resets the machine and puts it back into
    operation. At all times ‘no passing’ rule is considered to be in effect. The servicing times for each machine are given below.
Machine

a

b

C

d

e

f

g

h

Crew A

5

4

22

16

15

11

9

4

Crew B

6

10

12

8

20

7

2

21

 

  1. 9.   Determine the optimal sequence of scheduling the factory maintenance crew to minimise their idle time and represent it on a chart.
  2. 10.                Use graphical method to find the minimum elapsed total time sequence of 2 jobs and 5 machines, when we are given the following information:

Jo

Sequence

A

B

C

D

E

b 1

Time (hours)

2

3

4

6

2

Jo

Sequence

C

A

D

E

B

b 2

Time (hours)

4

5

3

2

6

  1. 11.                Two jobs are to be processed on four machines a, b, c and d. The technological order for these jobs on machines is as follows.                                          .

Job 1

a

b

c

d

Job 2

d

b

a

C

  1. 12.                Processing times are given In the following table
 

Machines

Job

a

b

c

d

1

4

6

7

3

2

4

7

5

8

 

Find the optimal sequence of jobs on each of machines.

  1. 13.                A machine shop has four machines A, B, C and D. Two jobs must be processed through each of these machines. The time (in hours) taken on each of these machines and the necessary sequence of jobs through the shop are given below.

 

Job 1

Sequence

A

B

C

D

Time (hours)

2

4

5

1

Job 2

Sequence

D

B

C

A

Time (hours)

6

4

2

3

Use graphic method to obtain the total minimum elapsed time.

  1. 14.                Job arrival pattern in sequencing.
  2. 15.                Processing time.
  3. 16.                Job arrival pattern.
  4. 17.                Processing time.
  5. 18.                Sequencing problem.
  6. 19.                What is sequencing problem? Explain and illustrate with examples.
  7. 20.                Explain sequencing problem and give its uses. Also point out the assumptions
    generally made, in case of simple sequencing problems.
  8. 21.                Explain briefly:

(i)                           Total elapsed time.

(ii)                        No passing rule

(iii)                      Processing orders in the context of sequencing problems.

  1. 22.                Discuss briefly the importance of sequencing technique in decision-making. Also give assumptions generally made in case of simple sequencing problem.
  2. 23.                What is the sequencing problem? Explain with illustrations.
  3. 24.                What general assumptions are made in solving “sequencing” problems? List the steps of solving sequencing problem.
  4. 25.                What is Sequencing Problem? How will you assign n jobs on 2 machines such that to minimise the total elapsed time?
  5. 26.                What is sequencing? What are its assumptions? Explain the procedure solving ‘n’ jobs and 3 machine sequencing problem.
  6. 27.                What is a, sequencing problem? Explain the following. terms in context of
    sequencing problems

(i)                           Total elapsed time and idle time.

(ii)                        No passing rule.

(iii)                      Processing order.

  1. 28.                There are five jobs each of which must go through the two machines A and B in the order AB. Processing times are given below. Determine the optimum sequence for 5 jobs.
Job :

J1

J2

J3

J4

J5

Machine A

2

4

5

7

1

Machine B

3

6

1

4

8

  1. 29.                A readymade garment manufacturer has to process 5 items through 2 stages
    production, viz., cutting and sewing. The time taken from each at different stages in given below:

Items:

1

2

3

4

5

Processing Times (Hours)

Cutting

5

7

3

4

6

Sewing

2

6

7

5

9

Find the order, in which these items should be processed so as to minimize the processing time.

  1. 30.                Eight jobs are to be processed through 2 machines ‘each day with -no passing allowed between machines. The processing times are as follows:
Job:

1

2

3

4

5

6

7

8

Processing time (hours) on:

Machine I:

4

8

7

8

2

1

3

9

Machine II:

6

3

6

4

6

5

7

2

Determine an optimum sequence to process the above jobs so as to minimize the total elapsed time.

  1. 31.                Find the sequence that minimizes the total elapsed time required to complete following jobs:
Job

A

B

C

D

E

F

G

G

I

J

Time (Hours) of M1

2

5

4

9

6

3

8

7

5

4

Time (Hours) on M2

6

8

7

4

3

11

9

8

5

2

  1. 32.                A certain manufacture has to process 6 items through two stages of production viz., assembling and polishing. The time taken for each of these items at different stages are given below. Find the optimal sequence so as to minimize the total processing time.
Item:

1

2

3

4

5

6

Assembling:

5

10

6

7

9

14

Polishing:

5

9

10

8

12

8

  1. 33.                Find the sequence that minimize the total elapsed time required to complete the following jobs:
Jobs

A

B

C

D

E

F

G

H

Time (Hours) on M1

2

5

4

9

6

3

8

7

Time (Hours) on M2

6

8

7

4

3

11

9

8

  1. 34.                Graphically find the minimum elapsed time to perform jobs J1 and J2 on machines A through F. The sequence and process timing are given as under:
Job 1 Sequence

A

B

C

D

E

F

6

4

5

3

4

2

Job 2 Sequence

A

C

E

D

D

F

4

8

4

3

6

4

  1. 35.                Solve following sequencing problem and find total elapsed time:
Job:

1

2

3

4

5

6

M/c I:

7

4

2

5

9

8

M/c II:

3

8

6

6

4

1

  1. 36.                Using graphical method find the minimum elapsed time to perform jobs 11 and J2 on machines M1 through M4. The sequence and process timing are given as follows:
Job1 Sequence

M1

M2

M3

M4

 

2

4

5

1

Job2 Sequence

M2

M3

M4

M1

 

6

5

2

3

  1. 37.                Determine the optimal sequencing of the following jobs and obtain the total
    elapsed time.
Job

1

2

3

4

5

6

7

8

Machine M1

7

3

6

8

9

5

4

3

Machine M2

8

8

2

4

7

5

6

8

  1. 38.                Solve the following sequencing problem.
 

Jobs

 

1

2

3

4

5

6

Machine X

8

10

11

12

16

20

Machine Y

7

15

10

14

13

9

 

Find the total elapsed time.

  1. 1.   The maintenance groups are G1 and G2, G1 is responsible for changing parts G2
    Oils and Resets the machines. The time required by G1 and G2 are given as under. In what order should the machines be serviced so that total time taken is minimised?
Machine

M1

M2

M3

M4

M5

M6

M7

Group-1

8

6

10

11

10

14

4

Group-2

5

3

7

12

8

6

7

 

  1. 2.   Solve the following sequencing problems and find total elapsed time also.
Job

1

2

3

4

5

6

7

Machine A

7

25

31

13

20

23

19

Machine B

17

21

21

13

24

3

7

 

  1. 3.   Solve the following Sequencing Problem:
 

1

2

3

4

5

6

7

8

9

M/c X

5

6

12

15

7

8

9

4

5

M/c Y

8

10

6

9

15

3

6

5

9

  1. 4.   Two maintenance teams T1 and T2 are responsible for maintaining seven
    The time required are given as under. In what order the machines be serviced so that total time taken is minimised:
 

M1

M2

M3

M4

M5

M6

M7

T1

18

16

20

21

20

24

14

T2

15

13

17

22

18

16

17

  1. 5.   Script of a book has to pass through two stages-Printing and Binding before
    completion of the job. The time required during each of the above two processes in respect of six different books is given below:

Book No.

Printing Time (Hours)

Binding Time (Hours)

1

2

3

4

5

6

30

120

50

20

90

110

80

100

90

60

30

10

 

Determine the Optimal sequence and Idle lime and Completion time for the Jobs.

  1. 6.   : Job arrival pattern in sequencing.
  2. 7.   Processing time
  3. 8.   Job arrival pattern
  4. 9.   Processing time
  5. 10.                Sequencing problem
  6. 11.                What is sequencing problem? Explain the following terms in context of
    sequencing problems :

(i)                           Total elapsed time and idle time

(ii)                        No passing rule

(iii)                      Processing order

  1. 12.                What is sequencing problem? Explain and illustrate with examples.
  2. 13.                Explain sequencing problem and give its uses. Also point out the assumptions generally made in case of simple sequencing problems.
  3. 14.                Explain briefly:

(i)                           Total elapsed time

(ii)                        No passing rule

(iii)                      processing orders in the context of sequencing problems.

  1. 15.                Discuss briefly the importance of sequencing technique in decision making. Also give assumptions generally made in case of simple sequencing problem.
  2. 16.                What is the sequencing problem? Explain with illustrations.
  3. 17.                Give three different examples of sequencing problems from your daily life. What is the process of solving the sequencing problem?
  4. 18.                Give four different examples of sequencing problem from your daily life.
  5. 19.                Give an illustrative classification of sequencing problem and explain with examples.

Explain the sequencing problem in proper details.

  1. 20.                There are five jobs, each of which must go through the two machines A and B in the order AB. Processing times are given below. Determine the optimum sequence for jobs.
Job:

J1

J2

J3

J4

J5

Machine A:

2

4

5

7

1

Machine B:

3

6

1

4

8

  1. 21.                A readymade garment manufacturer has to process 5 items through 2 stages of production, viz., cutting and sewing. The time taken for each at different stages is given on next page:
Item:

1

2

3

4

5

Processing Times (Hours)

Cutting

5

7

3

4

6

Sewing

2

6

7

5

9

 

Find an order, in which these items should be processed so as to minimize the total processing time.

  1. 22.                Eight jobs are to be processed through 2 machines each day with no allowed between machines. The processing times are as follows:
Job:

1

2

3

4

5

6

7

8

Processing time (hours on):

Machine I:

4

8

7

8

2

1

9

Machine II:

6

3

6

4

6

5

7

2

 

Determine an optimum sequence to process the above jobs so as to minimize the total elapsed time.

  1. 23.                Find the sequence that minimizes the total elapsed time required to complete the following jobs:
Jobs

A

B

C

D

E

F

G

H

I

J

Time (Hours) on M1

2

5

4

99

6

3

8

7

5

4

Time (Hours) on M2

6

8

7

4

3

11

9

8

5

2

 

  1. 24.                A certain manufacturer has to process 6 items through stages of production viz., assembling and polishing. The time taken for each of these items at different stages are given below, Find the optimal. sequence so as to minimize the total processing time.
Items:

1

2

3

4

5

6

Assembling:

8

10

6

7

9

14

Polishing:

5

9

10

8

12

8

 

  1. 25.                Find the sequence that minimizes the total elapsed time required to complete the following jobs :

 

Items:

1

2

3

4

5

6

Assembling:

8

10

6

7

9

14

Polishing:

5

9

10

8

12

8

 

  1. 26.                Convert the following three machine problems to two machine problem and hence solve for the optimal result:
Tasks

A

B

C

D

E

F

G

Time on Machine-I

3

8

7

4

9

8

7

Machine-II

4

3

2

5

1

4

3

Machine-II

6

7

5

11

5

6

12

 

  1. 27.                Find the optimal sequence and total elapsed time required to
    following tasks:
Time on

A

B

C

D

E

F

G

H

I

Machine I

2

5

4

9

6

8

7

5

4

Machine II

6

8

7

4

3

9

3

8

1

 

  1. 28.                Find the sequence that minimizes the total elapsed time required to complete the following jobs in the order AB :

Processing times in hours

No. of Jobs

1

2

3

4

5

6

Machine A

4

8

3

6

7

4

Machine B

6

3

7

2

8

4

 

  1. 29.                Solve the sequencing problem AB and BA

Jobs

1

2

3

4

5

6

7

Machines

A

B

12

7

6

8

5

9

11

4

5

7

7

8

6

3

 

  1. 30.                Find the sequence that minimizes the total elapsed time required to complete the following tasks. Each job is processed in any two of the machines A, B and C in any order:

Jobs

1

2

3

4

5

6

7

Machines

A

B

C

12

7

3

6

8

4

5

9

11

3

8

5

5

7

2

7

8

8

6

3

4

 

  1. 31.                Jobs, each of which has to go through the machines M1 and M2 in the order
    M2M1. Processing time (in Hour) are given:

Jobs

Job

A

B

C

D

E

F

G

Machine

Machine

M1

M2

3

8

12

10

15

10

6

6

10

12

11

1

6

3

 

(i)                           Determine the optimum sequence that will minimise the total elapsed time, with idle time of each machine.

(ii)                        If the order is reversed to M2M1, what difference will it make to the calculated results?

  1. 32.                A manufacturing company processes 6 different jobs on two machines A and B. Number of units of each job and its processing time on A and B are given in table. Find the optimal sequence, the total minimum elapsed time and idle time for each machine

Table

Job No.

No. of units of each job

Processing time

Machine A (minutes)

Machine B (minutes)

1

2

3

4

5

6

3

4

2

5

2

3

5

16

6

3

9

6

8

7

11

5

7

14