Suppose there are n jobs J1J2Jn which are to be processed in

Last updated: 10/10/2023

Suppose there are n jobs J1J2Jn which are to be processed in two machines say M and M in order M M M first and M next Let tij be the processing time for ith job in jih 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 J t12 above 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 My will always be busy and will process the n jobs one by one After processing all the n jobs the machine My 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 Jn tin 32 tzn Hence the total idle time for machine M is E 1X2j Thus the sequencing problem is to minimize E1 X2 The total elapsed time T is given by T Processing time idle time i e T Ej 1t2j j 1 X2j Here some of the x2 may be zeros We observe that E 1 t2 is constant Hence minimizing T is equivalent to minimizing j1 X2j 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 tij t2j 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 t2j t t2s 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 ii If the tie is for the minimum among the processing times tij on machine M 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 Stan 5 Remove the assigned jobs from the table If the table becomes