Evaluation of a hybrid genetic tabu search framework on job shop scheduling benchmark problems

S. Meeran, M. S. Morshed

Research output: Contribution to journalArticle

9 Citations (Scopus)
123 Downloads (Pure)

Abstract

It has been well established that to find an optimal or near-optimal solution to job shop scheduling problems (JSSPs), which are NP-hard, one needs to harness different features of many techniques, such as genetic algorithms (GAs) and tabu search (TS). In this paper, we report usage of such a framework which exploits the diversified global search and the intensified local search capabilities of GA and TS, respectively. The system takes its input directly from the process information in contrast to having a problem-specific input format, making it versatile in dealing with different JSSP. This framework has been successfully implemented to solve industrial JSSPs. In this paper, we evaluate its suitability by applying it on a set of well-known job shop benchmark problems. The results have been variable. The system did find optimal solutions for moderately hard benchmark problems (40 out of 43 problems tested). This performance is similar to, and in some cases better than, comparable systems, which also establishes the versatility of the system. However for the harder benchmark problems it had difficulty in finding a new improved solution. We analyse the possible reasons for such a performance.
Original languageEnglish
Pages (from-to)5780-2798
JournalInternational Journal of Production Research
Volume52
Issue number9
Early online date22 Apr 2014
DOIs
Publication statusPublished - 2014

Fingerprint Dive into the research topics of 'Evaluation of a hybrid genetic tabu search framework on job shop scheduling benchmark problems'. Together they form a unique fingerprint.

  • Cite this