A Heuristic Approach Based on Tabu Search for Early/Tardy Flexible Job Shop Problems

This paper addresses minimizing total weighted earliness/tardiness (twet) of jobs in a flexible job shop (fjs) problem. the fjs problem is an extension of the classical job shop (js) problem that implies each operation may be assigned to alternative available machines. so, a job may have alternative routing. the fjs problem with a twet criterion is modeled as a mixed integer programming. the model is proven to be np-complete. to solve the model, an algorithm, based on a tabu search approach (ts), is developed. the proposed algorithm employs ts to find the best routing of each job and a backward procedure to operations scheduling. two neighboring functions are designed and their effect is investigated on the performance. the numerical experiments show the suggested algorithm efficiently solves the model in a reasonable cpu time.