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

S. Meeran, M. S. Morshed

Research output: Contribution to journalArticle

8 Citations (Scopus)
64 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

Tabu search
Genetic algorithms
Job shop scheduling
Benchmark
Evaluation
Optimal solution
Genetic algorithm

Cite this

Evaluation of a hybrid genetic tabu search framework on job shop scheduling benchmark problems. / Meeran, S.; Morshed, M. S.

In: International Journal of Production Research, Vol. 52, No. 9, 2014, p. 5780-2798.

Research output: Contribution to journalArticle

@article{88fc52ac94af4434998e3ad27e12bbf1,
title = "Evaluation of a hybrid genetic tabu search framework on job shop scheduling benchmark problems",
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.",
author = "S. Meeran and Morshed, {M. S.}",
year = "2014",
doi = "10.1080/00207543.2014.911417",
language = "English",
volume = "52",
pages = "5780--2798",
journal = "International Journal of Production Research",
issn = "0020-7543",
publisher = "Taylor and Francis",
number = "9",

}

TY - JOUR

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

AU - Meeran, S.

AU - Morshed, M. S.

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

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

UR - http://dx.doi.org/10.1080/00207543.2014.911417

U2 - 10.1080/00207543.2014.911417

DO - 10.1080/00207543.2014.911417

M3 - Article

VL - 52

SP - 5780

EP - 2798

JO - International Journal of Production Research

JF - International Journal of Production Research

SN - 0020-7543

IS - 9

ER -