Sequencing Problems, Steps involved to solve seq Assignment Help

Assignment Help: >> Techniques of Operations Research >> Sequencing Problems, Steps involved to solve seq

SEQUENCING PROBLEMS

Sequencing problems are concerned with an appropriate selection of a sequence of jobs to be done on a finite number of service facilities (like machines) in some well defined technological order so as to optimize some efficiency measure such as total elapsed time or overall cost, etc. for example, the well known sequencing problem is to determine the sequence in which two or more jobs should be processed on one or more machines in order to optimize some measure of effectiveness. A general sequencing problem may be expressed as follows:

            Suppose there are n jobs (1,2,3,….,n) each of which has to be processed one at a time at each of m machines A,B,C…… the order of processing each job through the machines as well as the time required by the jobs on each of the machines is also given. The problem is to select from the (n!)m theoretically possible sequences (or combinations) that sequence (or order) for processing the jobs which optimizes (minimizes) the total elapsed time (i.e., the total time for the start of the first job upto the completion of the last job).

Remark. Theoretically, a solution by simple enumeration is always possible but in actual practice the computation of effectiveness for a given sequence can be quite complex, and the number of cases for enumeration makes this approach quite prohibitive even for moderate values of m and n.

7.2 GENERAL ASSUMPTIONS

The following assumptions are generally made in sequencing problems.

1.      The processing times on different machines are independent of the order of the job in which they are to be processed.

2.      Only one job can be processed on a given machine at a time.

3.      The time taken by the jobs in moving from one machine to another is very negligible and is taken as equal to zero.

4.      Each job once started on a machine is to be performed up to the completion on that machine.

5.      Machines to be used are of different types.

6.      All jobs are known and are ready for processing before the period under consideration begins.

7.      Processing times are given and do not change.

8.      The order of the completion of the jobs has no significance.

Sequencing problems become complicated if the above stated assumptions not hold good. We shall only deal with the simple sequencing problems in this chapter.

 

7.3 BASIC TERMINOLOGY

1.Number of Machines means the service facilities through which a job must pass before it is completed. For example a book to be published has to be processed through composing printing binding etc. in this case the book constitutes the job and the various processes constitute the number of machines.

2. Processing time means the time each job requires at each machine.

3. Processing order refers to the order in which various machines are required for completing the job.

4. Total elapsed time is the between starting the first job and completing the last one.

5. Idle time on a machine is the time a machine remains idle during the total elapsed time.

6. No passing rule implies that passing is not allowed i.e., the same order of jobs is maintained over each machine. If each of the n-jobs to be processed through two machines M1 and M2 in the order M1M2 then this rule will mean that each job will go to machine M1 first and then to M2.

7.4 PROCESSING n- JOBS THROUGH TWO MACHINES

The simplest possible sequencing decision problem is that of N- job two machine sequencing in which n-jobs should be processed through two machines so as to minimize the total elapsed time. T. this type of problem can be completely described as:

(i)                 Only two machines A and B are involved.

(ii)               Each job is processed in the order AB and

(iii)             The expected processing times A1,A2,….,An, B1,B2, …., Bn are known as given below:

Job

I                   1                        2                              3                                ….                           N

Ai                A1                      A2                           A3                             ….                          An

Bi                B1                       B2                          B3                              ….                          Bn

 The procedure for the solution of the above problem was developed by johnson and Bellman (1953) and involves the following steps:

Step 1. Select the smallest processing time occurring in the list A1, A2,….., An and B1,B2,….Bn. if there is a tie select either of the smallest processing time.

Step 2. (i) if the smallest processing time is An do the rth job first and place it at the beginning of the sequence.

(ii) if it is Bn do the sth job last of all (because of the given order AB) and place it at the end of the sequence.

This decision will apply to both machines AandB.

(i)                 (a) if there is a tie for minima Ar  = Bs process the rth job first and the sth one in the last.

(b) if there is a tie for minimum among Ar’s then do any one of these jobs for which there is a tie first.

(c ) If there is a tie for minimum among Bs then do any of these jobs in the last.

Step 3. There are now (n-1) jobs left to be ordered. Repeat step 1 and 2 to the reduced set of processing times obtained by deleting the processing times for both machines corresponding to the job already assigned.

Step 4. Continue the process placing the jobs next to first or next to last and so on till all jobs have been assigned a position in what is called as optimum sequence.

Step 5. After finding the optimum sequence as stated above, we can find the overall or total elapsed time and also the idle times on machines A and B as under.

                    Total elapsed time                       = the time between starting the first job in

                                                                            the optimum sequence on machine A and

                                                                            completing the last job in the optimum  sequence

                                                                            on machine B.

                    idle time on machine A               = (Time when the last job in the optimum sequence

                                                                              is completed on Machine B).

                    idle time on machine B                = (Time when first job in the optimum sequence

                                                                            completed on machine A

 

                                                                        n

                                                                    +  ? [(time when kth job starts on k = 2

                                                                        K = 2

                                                                        Machine B) – (time k-1)sth job finished on machine

                                                B)].

Remark. The following two important assumptions are made while following the above solution procedure.

(i)                 It is assumed that the order of completion of jobs has no significance i.e., no product is required more urgently than the order.

(ii)               It is also assumed that in-process storage is available and that the cost of in-process inventory is either same for each job or is too small to be considered.

Example 1. A book binder has one printing press, one binding machine and the manuscripts of a number of different books. The time required performing the printing and binding operations for each book are shown below. We wish to determine the order in which books should be processed, in order to minimize the total time required to turn out all the books.

Book                           :              1               2                   3               4                   5                6

                                    :              30             120               50             20                 90              110

                                    :              80             100               90             60                 30              10       

Solution. applying steps 1 and 2 of solution procedure, we observe that the smallest processing time is 10 hours for book 6 on binding machine. Therefore, we shall schedule book 6 in the last as shown below.

 

 

 

 

 

     6

 

The reduced set of processing time becomes.

Book                           :              1               2                   3               4                   5

Printing time (hrs)       :              30             120               50             20*               90             

Binding time (hrs)       :              80             100               90             60                 30

Again the smallest processing time in the reduced list is 20 for book 4 on printing machine. Thus we shall do job 4 first and list the elements as follows:

      4

 

 

 

 

6

 

After assigning books 4 and 6 we are now left with 4 books and two machines with reduced set of processing times as follows.

Book                              :                       1                        2                  3               5              

Printing time (hrs)          :                       30*                    120              50             90

Binding time (hrs)          :                       80                      100              90             30*

There are two equal minimal values printing time of 30 hours for book 1 and binding time of 30 hours of book 5. According to the rules. Book 1 is scheduled next to book 4 and book 5 next to book 6, yielding the sequence as follows.

      4

     1

 

 

   5

     6

 

 The reduced set of processing times now becomes.

Book                                       :                      2                        3

Printing time (hrs)                   :                      120                    50*

Binding time (hrs)                   :                      100                    90

Here since smallest printing time is 50 hours for book 3, we place book in the third cell and the remaining book 2 in fourth cell and we get the optimum sequence as:

4

1

3

2

5

6

 

The minimum elapsed time from the start of the first book to the completion of the last book corresponding the optimum sequence is computed as shown in the following table:

Book               printing Machine                           binding Machine                        Idle of time

                        Time in           time out                 tine in       time out                 Binding Machine

4                      0                     20                          20             80                                    20                  

1                      20                   50                          80             160                                    0

3                      50                   100                        160           250                                     0                                          

2                      100                 220                        250           320                                     0

5                      220                 310                        350           380                                     0

6                      310                 420                        420           430                                   40

 

From the above table it is clear that minimum elapsed time is 430 hours. Idle time for printing machine is 10 hours (from 420 hours to 430 hours) and for binding machine is 20+20 = 60 hours (from 0-20 and 380-420 hours).

Remarks 1. It may be noted that the total elapsed time is equal to the of fan blades each day from the following information so as to minimize the total elapsed time.

2. The total elapsed time can also be calculated by using Gantt Chart.

Example 2. Determine on optimum sequence to process the various types of fan blades each day from the following information so as to minimize the total elapsed time:

Types of fan                          Number to be                         Processing times on

Blabes                                    processed each                       Machine A            Machine B

                                               Day                                        (minutes)               (minutes)

1                                             4                                             4                            8                              

2                                             6                                             12                          6

3                                             5                                             14                          16

4                                             2                                             20                          22

5                                             4                                             8                            10

6                                             3                                             18                          2

also work out the total elapsed time for an optimum sequence. What is the total idle time on machine 1? On machine 2?

Solution . using the procedure stated above we find that the smallest processing time is 1 minute relating to type 6 on machine B and as such the partial assignment will be:

 

 

 

 

 

6

Deleting the job (i.e., type 6) from further consideration we have the smallest remaining processing time of 2 minutes in case of type 1 on machine A and as such our partial assignment becomes:

      1

 

 

 

 

    6

   4                                                                                                                                           3

Repeated application of the said procedure will result in the following list of partial assignments.

1

 

 

 

2

6

4                                                                                                         6                                   3

1

5

 

 

2

6

4                          4                                                                             6                                   3

1

5

3

 

2

6

4                          4                        5                                                    6                                   3

1

5

3

4

2

6

4                          4                         5                        2                          6                                  3

Hence the optimum sequence is :

First – Four type 1 fan blades

Second- Four type 5 fan blades

Third – Five type 3 fan blades

Fourth- Two type 4 fan blades

Fifth- Six type 2 fan blades

Sixth – three type 6 fan blades.

Now the total elapsed time and idle can be determined from the following table:

 

 

Job                   Machine 1                                    Machine 2                                    Idle time on

Types of          time in         time out                   time in             time out               machine B

Fan blades       (minutes)      (minutes)                 (minutes)         (minutes)              (minutes)

1                              0                  4                              4                      12                          4

1                              4                  8                              12                    20                          0

1                              8                  12                            20                    28                          0

1                              12                16                            28                    36                          0

5                              16                24                            36                    46                          0

5                              24                32                            46                    56                          0

5                              32                40                            56                    66                          0

5                              40                48                            66                    76                          0     

3                              48                62                            76                    92                          0     

3                              62                76                            92                    108                        0

3                              76                90                            108                  124                        0

3                              90                104                          124                  140                        0

3                              104              118                          140                  156                        0

4                              118              138                          156                  178                        0     

4                              138              158                          178                  200                        0

2                              158              170                          200                  206                        0

2                              170              182                          206                  212                        0

2                              182              194                          212                  218                        0

2                              194              206                          218                  224                        0

2                              206              218                          224                  230                        0

2                              218              230                          230                  236                        0

6                              230              248                          248                  250                        0

6                              248              266                          266                  268                        0

6                              266              284                          284                  286                        0

                                                  

Form the above table we conclude that:

(i)                 The total elapsed time for an optimum sequence is 286 minutes:

(ii)               Idle time on Machine A= 286-284 = 2 minutes.

(iii)             Idle time on Machine B= 4+0+0+…..+12+16+16= 48 minutes.                                                  

Sequencing Problems Homework Help - Assignment Help

Operation research experts at Expertsmind.com are highly qualified and experienced; they are familiar with all kind of operation research techniques problems and questions. Tutors makes it easy for you by providing step by step answers and it may help you in solving future assignments having same kind of problems. We at Expertsmind.com offer sequencing problems based homework help, sequencing problems assignment help, sequencing technique and question's answers with step by step procedure and terms. Get solved sequencing technique and method based questions from Expertmind's online tutors and compare difference yourself.

ExpertsMind.com - techniques of operation research, Sequencing Assignment Help, Sequencing Homework Help, Sequencing Assignment Tutors, Sequencing Solutions, Sequencing Answers, Techniques of Operations Research Assignment Tutors

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd