New Heuristics for Flowshop Scheduling

In the flowshop scheduling problem,  n  jobs are to be processed on  m  machines. The order of the machines is fixed. We assume that a machine processes one job at a time and a job is processed on one machine at a time without preemption. Let  t   p   ( i ,  j ) denote the processing time of job  j  on machine  i  and  t   c   ( i ,  j ) denote the completion time of job  j  on machine  i . Let  Jj  denote the  j -th job and  M   i   the  i -th machine. The completion times of the jobs are obtained as follows. For  i  = 1, 2,...,  m  and  j  = 1, 2,...,  n ,  t   c   ( M   1 ,  J   1 ) =  t   p   ( M   1 ,  J   1 ); t   c   ( M   i   ,  J   1 ) =  t   c   ( M   i− 1 ,  J   1 ) +  t   p   ( M i   ,  J   1 ); t   c   ( M   1 ,  J   j   ) =  t   c   ( M   1 ,  J   j− 1 ) +  t   p   ( M   1 ,  J   j   );  t   c   ( M   i   ,  J   j   ) = m ax{t   c   ( M   i− 1 ,  J   j   ), t   c   ( M   i   , J   j− 1 )} +  t   p   ( M   i   , J   j   ).  Makespan  is defined as the completion time of the last job,  t   c   ( M   m   ,  J   n   ). The goal is to obtain the  n -job sequence that minimizes the makespan. The search space consists of  n ! possible job sequences. The problem is NP-hard.