Sequencing is 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.
The following assumptions are generally made in sequencing problems.
- The processing times on different machines are independent of the order of the job in which they are to be processed.
- Only one job can be processed on a given machine at a time.
- The time taken by the jobs in moving from one machine to another is very negligible and is taken as equal to zero.
- Each job once started on a machine is to be performed up to the completion on that machine.
- Machines to be used are of different types.
- All jobs are known and are ready for processing before the period under consideration begins.
- Processing times are given and do not change.
- The order of the completion of the jobs has no significance. Sequencing become complicated if the above stated assumptions not hold good. We shall only deal with the simple sequencing problems in this chapter.
- 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.
- Processing time means the time each job requires at each machine.
- Processing order refers to the order in which various machines are required for completing the job.
- Total elapsed time is the between starting the first job and completing the last one.
- Idle time on a machine is the time a machine remains idle during the total elapsed time.
- 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.