Sequencing problems deals with the selection of an optimum order for the number of jobs to perform with a finite number of facilities. The objective of sequencing is to determine the sequence of performing jobs such that we can minimize the total cost/time.
Sequencing problems arise in situations like a manufacturing plant for performing orders, in a hospital where the patients wait for different types of tests and in a bank where customers wait for different types of transactions, etc.
To find the optimum sequence, we first need to calculate the total elapsed time for each of the possible sequences.
As we see earlier, even if the values of m and n are very small, it is difficult to get the sequence what we desire with the total minimum elapsed time.
Note- Sequencing problem is the problem of finding an optimal sequence of completing a certain number of jobs so as to minimize the total elapsed time between completion of first and last job.
Terminologies
Processing Time : It is the time that a job i on each machine j requires.
1. Total Elapsed Time T: It is 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. Idle Time : It is the time for which a machine j does not have a job to process, i.e., idle time from the end of job (i-1) to the start of job i.
3. Processing Order: It refers to the order or sequence in which machine requires for completing the job.
4. Number of Machines: It refers to the service facilities available through which a job must pass before it is assumed to be completed.
5. No Passing Rule: It refers to the condition to be satisfied in which the order of jobs are to be processed on given machines.
Assumptions
1. The processing times on different machines are exactly known and are independent of the order of the jobs in which they are to be processed.
2. The time taken by the jobs in moving from one machine to another is negligible.
3. Once a job begins in a machine, it is to complete before another job can begin on the same machine.
4. A job starts on a machine as soon as the previous job is over, and the machine is free to work.
5. No machine can process more than one job simultaneously.
6. Machines are of different types.
7. The order of completion of jobs are independent.
As discussed earlier, the objective of sequencing is to determine the sequence of jobs so that all the jobs are performed in a minimum completion time from the beginning of the first job till the completion of the last job.
The advantages of sequencing are:
1. We get the information like which machines are idle and period of idle time.
2. Completion time for all the jobs to complete
Types of Sequencing Problems–
There are four types of sequencing problems- n jobs through 2 machines,
n jobs through 3 machines, n jobs through m machines, two jobs through m machines