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

Author

Faculty of Management,University of Tehran

Abstract

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.

Volume 13, Issue 1 - Serial Number 1
Transactions on Computer Science & Engineering and Electrical Engineering (D)
January 2006
  • Receive Date: 07 August 2006
  • Revise Date: 07 December 2024
  • Accept Date: 30 March 2006