A hybrid genetic tabu search algorithm for solving job shop scheduling problems

a case study

S. Meeran, M. S. Morshed

Research output: Contribution to journalArticle

61 Citations (Scopus)
19 Downloads (Pure)

Abstract

In recent decades many attempts have been made at the solution of Job Shop Scheduling Problem using a varied range of tools and techniques such as Branch and Bound at one end of the spectrum and Heuristics at the other end. However, the literature reviews suggest that none of these techniques are sufficient on their own to solve this stubborn NP-hard problem. Hence, it is postulated that a suitable solution method will have to exploit the key features of several strategies. We present here one such solution method incorporating Genetic Algorithm and Tabu Search. The rationale behind using such a hybrid method as in the case of other systems which use GA and TS is to combine the diversified global search and intensified local search capabilities of GA and TS respectively. The hybrid model proposed here surpasses most similar systems in solving many more traditional benchmark problems and real-life problems. This, the system achieves by the combined impact of several small but important features such as powerful chromosome representation, effective genetic operators, restricted neighbourhood strategies and efficient search strategies along with innovative initial solutions. These features combined with the hybrid strategy employed enabled the system to solve several benchmark problems optimally, which has been discussed elsewhere in Meeran and Morshed (8th Asia Pacific industrial engineering and management science conference, Kaohsiung, Taiwan, 2007). In this paper we bring out the system's practical usage aspect and demonstrate that the system is equally capable of solving real life Job Shop problems. 2011 Springer Science+Business Media, LLC.
Original languageEnglish
Pages (from-to)1063-1078
Number of pages16
JournalJournal of Intelligent Manufacturing
Volume23
Issue number4
Early online date8 Mar 2011
DOIs
Publication statusPublished - 1 Aug 2012

Fingerprint

Tabu search
Industrial management
Management science
Industrial engineering
Chromosomes
Computational complexity
Genetic algorithms
Industry
Job shop scheduling

Cite this

A hybrid genetic tabu search algorithm for solving job shop scheduling problems : a case study. / Meeran, S.; Morshed, M. S.

In: Journal of Intelligent Manufacturing, Vol. 23, No. 4, 01.08.2012, p. 1063-1078.

Research output: Contribution to journalArticle

@article{0f52d92219b3419abec4dc20f712d123,
title = "A hybrid genetic tabu search algorithm for solving job shop scheduling problems: a case study",
abstract = "In recent decades many attempts have been made at the solution of Job Shop Scheduling Problem using a varied range of tools and techniques such as Branch and Bound at one end of the spectrum and Heuristics at the other end. However, the literature reviews suggest that none of these techniques are sufficient on their own to solve this stubborn NP-hard problem. Hence, it is postulated that a suitable solution method will have to exploit the key features of several strategies. We present here one such solution method incorporating Genetic Algorithm and Tabu Search. The rationale behind using such a hybrid method as in the case of other systems which use GA and TS is to combine the diversified global search and intensified local search capabilities of GA and TS respectively. The hybrid model proposed here surpasses most similar systems in solving many more traditional benchmark problems and real-life problems. This, the system achieves by the combined impact of several small but important features such as powerful chromosome representation, effective genetic operators, restricted neighbourhood strategies and efficient search strategies along with innovative initial solutions. These features combined with the hybrid strategy employed enabled the system to solve several benchmark problems optimally, which has been discussed elsewhere in Meeran and Morshed (8th Asia Pacific industrial engineering and management science conference, Kaohsiung, Taiwan, 2007). In this paper we bring out the system's practical usage aspect and demonstrate that the system is equally capable of solving real life Job Shop problems. 2011 Springer Science+Business Media, LLC.",
author = "S. Meeran and Morshed, {M. S.}",
year = "2012",
month = "8",
day = "1",
doi = "10.1007/s10845-011-0520-x",
language = "English",
volume = "23",
pages = "1063--1078",
journal = "Journal of Intelligent Manufacturing",
issn = "0956-5515",
publisher = "Springer Netherlands",
number = "4",

}

TY - JOUR

T1 - A hybrid genetic tabu search algorithm for solving job shop scheduling problems

T2 - a case study

AU - Meeran, S.

AU - Morshed, M. S.

PY - 2012/8/1

Y1 - 2012/8/1

N2 - In recent decades many attempts have been made at the solution of Job Shop Scheduling Problem using a varied range of tools and techniques such as Branch and Bound at one end of the spectrum and Heuristics at the other end. However, the literature reviews suggest that none of these techniques are sufficient on their own to solve this stubborn NP-hard problem. Hence, it is postulated that a suitable solution method will have to exploit the key features of several strategies. We present here one such solution method incorporating Genetic Algorithm and Tabu Search. The rationale behind using such a hybrid method as in the case of other systems which use GA and TS is to combine the diversified global search and intensified local search capabilities of GA and TS respectively. The hybrid model proposed here surpasses most similar systems in solving many more traditional benchmark problems and real-life problems. This, the system achieves by the combined impact of several small but important features such as powerful chromosome representation, effective genetic operators, restricted neighbourhood strategies and efficient search strategies along with innovative initial solutions. These features combined with the hybrid strategy employed enabled the system to solve several benchmark problems optimally, which has been discussed elsewhere in Meeran and Morshed (8th Asia Pacific industrial engineering and management science conference, Kaohsiung, Taiwan, 2007). In this paper we bring out the system's practical usage aspect and demonstrate that the system is equally capable of solving real life Job Shop problems. 2011 Springer Science+Business Media, LLC.

AB - In recent decades many attempts have been made at the solution of Job Shop Scheduling Problem using a varied range of tools and techniques such as Branch and Bound at one end of the spectrum and Heuristics at the other end. However, the literature reviews suggest that none of these techniques are sufficient on their own to solve this stubborn NP-hard problem. Hence, it is postulated that a suitable solution method will have to exploit the key features of several strategies. We present here one such solution method incorporating Genetic Algorithm and Tabu Search. The rationale behind using such a hybrid method as in the case of other systems which use GA and TS is to combine the diversified global search and intensified local search capabilities of GA and TS respectively. The hybrid model proposed here surpasses most similar systems in solving many more traditional benchmark problems and real-life problems. This, the system achieves by the combined impact of several small but important features such as powerful chromosome representation, effective genetic operators, restricted neighbourhood strategies and efficient search strategies along with innovative initial solutions. These features combined with the hybrid strategy employed enabled the system to solve several benchmark problems optimally, which has been discussed elsewhere in Meeran and Morshed (8th Asia Pacific industrial engineering and management science conference, Kaohsiung, Taiwan, 2007). In this paper we bring out the system's practical usage aspect and demonstrate that the system is equally capable of solving real life Job Shop problems. 2011 Springer Science+Business Media, LLC.

UR - http://www.scopus.com/inward/record.url?scp=84865247709&partnerID=8YFLogxK

UR - http://dx.doi.org/10.1007/s10845-011-0520-x

U2 - 10.1007/s10845-011-0520-x

DO - 10.1007/s10845-011-0520-x

M3 - Article

VL - 23

SP - 1063

EP - 1078

JO - Journal of Intelligent Manufacturing

JF - Journal of Intelligent Manufacturing

SN - 0956-5515

IS - 4

ER -