Suppose there are n jobs J1 J2 two machines say M and M in
Last updated: 10/10/2023
Suppose there are n jobs J1 J2 two machines say M and M in order M M M first and M next Let t be the processing time for ith job in jth machine The list of jobs along with their processing times can be summarized as in the following table Jobs Processing time in M Processing time in M J t11 t21 above Jn which are to be processed in Jz t12 t22 Let x2j be the time for which the machine M remains idle after completing the j 1 th job and before starting jth job A job is assigned to machine My first and after it has been completely processed in machine M it is assigned to the machine M If the machine M is not free at any moment for processing a particular job then that job has to wait in a waiting line for its turn on the machine M In other words passing is not allowed Hence machine M will always be busy and will process the n jobs one by one After processing all the n jobs the machine M remains idle until all the n jobs are completed in the machine M However M may remain idle after the completion of some of the m jobs and before starting the next job The sequencing problem is to minimize the total idle time of the second machine M 32 Jn tin tzn Hence the total idle time for machine M is E 1X2j Thus the sequencing problem is to minimize E 12 The total elapsed time T is given by T Processing time idle time i e T j 121 1 2 Here some of the x2 may be zeros We observe that E 1 t2j is constant Hence minimizing T is equivalent to minimizing 1x2j Algorithm to find the optimum sequence for n jobs in 2 machines Step 1 List the jobs along with their processing times in a table as given Step 2 Find the minimum t j tzj for all j 1 2 n Step 3 If the smallest processing time is for the first machine M then place the corresponding job in the first available position in the sequence If it is for the second machine M then place the corresponding job in the last available position in the sequence Step 4 If there is a tie in the minimum of all the processing times then there arises three cases Case i Minimum among all processing times is same for the two machines i e minimum t j tzj t r tzs then place the rth job in the first available position in the sequence and the sth job in the last available position in the sequence Case it If the tie is for the minimum among the processing times tij on machine My only then place the jobs arbitrarily one after the other in the last available positions in the sequence Case iii If the tie is for the minimum among the processing times t2j on machine M only then place the jobs arbitrarily one after the other in the last available positions in the sequence