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.
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:
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.
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:
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:
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:
4 3
Repeated application of the said procedure will result in the following list of partial assignments.
4 6 3
4 4 6 3
4 4 5 6 3
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