New and 'stronger' job-shop neighbourhoods

a focus on the method of Nowicki and Smutnicki (1996)

Anant Singh Jain, Balasubramanian Rangaswamy, Sheik Meeran

Research output: Contribution to journalArticle

42 Citations (Scopus)

Abstract

Examination of the job-shop scheduling literature uncovers a striking trend. As methods for the deterministic job-shop problem have gradually improved over the years, they have come to rely on neighbourhoods for selecting moves that are more and more constrained. We document this phenomenon by focusing on the approach of Nowicki and Smutnicki (Management Science, 1996, 42(6), 797-813), noted for proposing and implementing the most restrictive neighbourhood in the literature. The Nowicki and Smutnicki (NS) method which exploits its neighbourhood by a tabu search strategy, is widely recognised as the most effective procedure for obtaining high quality solutions in a relatively short time. Accordingly, we analyse the contribution of the method's neighbourhood structure to its overall effectiveness. Our findings show, surprisingly, that the NS neighbourhood causes the method's choice of an initialisation procedure to have an important influence on the best solution the method is able to find. By contrast, the method's choice of a strategy to generate a critical path has a negligible influence. Empirical testing further discloses that over 99.7% of the moves chosen from this neighborhood (by the NS rules) are disimproving-regardless of the initial solution procedure or the critical path generation procedure employed. We discuss implications of these findings for developing new and more effective job-shop algorithms.

Original languageEnglish
Pages (from-to)457-480
Number of pages24
JournalJournal of Heuristics
Volume6
Issue number4
DOIs
Publication statusPublished - 1 Sep 2000

Fingerprint

Job Shop
Management science
Critical Path
Tabu search
Job Shop Scheduling
Testing
Search Strategy
Tabu Search
Initialization
Job shop

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computational Theory and Mathematics
  • Control and Systems Engineering
  • Theoretical Computer Science

Cite this

New and 'stronger' job-shop neighbourhoods : a focus on the method of Nowicki and Smutnicki (1996). / Jain, Anant Singh; Rangaswamy, Balasubramanian; Meeran, Sheik.

In: Journal of Heuristics, Vol. 6, No. 4, 01.09.2000, p. 457-480.

Research output: Contribution to journalArticle

Jain, Anant Singh ; Rangaswamy, Balasubramanian ; Meeran, Sheik. / New and 'stronger' job-shop neighbourhoods : a focus on the method of Nowicki and Smutnicki (1996). In: Journal of Heuristics. 2000 ; Vol. 6, No. 4. pp. 457-480.
@article{b4e2e6d7f7f94f55b1b1657b5caeda6d,
title = "New and 'stronger' job-shop neighbourhoods: a focus on the method of Nowicki and Smutnicki (1996)",
abstract = "Examination of the job-shop scheduling literature uncovers a striking trend. As methods for the deterministic job-shop problem have gradually improved over the years, they have come to rely on neighbourhoods for selecting moves that are more and more constrained. We document this phenomenon by focusing on the approach of Nowicki and Smutnicki (Management Science, 1996, 42(6), 797-813), noted for proposing and implementing the most restrictive neighbourhood in the literature. The Nowicki and Smutnicki (NS) method which exploits its neighbourhood by a tabu search strategy, is widely recognised as the most effective procedure for obtaining high quality solutions in a relatively short time. Accordingly, we analyse the contribution of the method's neighbourhood structure to its overall effectiveness. Our findings show, surprisingly, that the NS neighbourhood causes the method's choice of an initialisation procedure to have an important influence on the best solution the method is able to find. By contrast, the method's choice of a strategy to generate a critical path has a negligible influence. Empirical testing further discloses that over 99.7{\%} of the moves chosen from this neighborhood (by the NS rules) are disimproving-regardless of the initial solution procedure or the critical path generation procedure employed. We discuss implications of these findings for developing new and more effective job-shop algorithms.",
author = "Jain, {Anant Singh} and Balasubramanian Rangaswamy and Sheik Meeran",
year = "2000",
month = "9",
day = "1",
doi = "10.1023/A:1009617209268",
language = "English",
volume = "6",
pages = "457--480",
journal = "Journal of Heuristics",
issn = "1381-1231",
publisher = "Springer Netherlands",
number = "4",

}

TY - JOUR

T1 - New and 'stronger' job-shop neighbourhoods

T2 - a focus on the method of Nowicki and Smutnicki (1996)

AU - Jain, Anant Singh

AU - Rangaswamy, Balasubramanian

AU - Meeran, Sheik

PY - 2000/9/1

Y1 - 2000/9/1

N2 - Examination of the job-shop scheduling literature uncovers a striking trend. As methods for the deterministic job-shop problem have gradually improved over the years, they have come to rely on neighbourhoods for selecting moves that are more and more constrained. We document this phenomenon by focusing on the approach of Nowicki and Smutnicki (Management Science, 1996, 42(6), 797-813), noted for proposing and implementing the most restrictive neighbourhood in the literature. The Nowicki and Smutnicki (NS) method which exploits its neighbourhood by a tabu search strategy, is widely recognised as the most effective procedure for obtaining high quality solutions in a relatively short time. Accordingly, we analyse the contribution of the method's neighbourhood structure to its overall effectiveness. Our findings show, surprisingly, that the NS neighbourhood causes the method's choice of an initialisation procedure to have an important influence on the best solution the method is able to find. By contrast, the method's choice of a strategy to generate a critical path has a negligible influence. Empirical testing further discloses that over 99.7% of the moves chosen from this neighborhood (by the NS rules) are disimproving-regardless of the initial solution procedure or the critical path generation procedure employed. We discuss implications of these findings for developing new and more effective job-shop algorithms.

AB - Examination of the job-shop scheduling literature uncovers a striking trend. As methods for the deterministic job-shop problem have gradually improved over the years, they have come to rely on neighbourhoods for selecting moves that are more and more constrained. We document this phenomenon by focusing on the approach of Nowicki and Smutnicki (Management Science, 1996, 42(6), 797-813), noted for proposing and implementing the most restrictive neighbourhood in the literature. The Nowicki and Smutnicki (NS) method which exploits its neighbourhood by a tabu search strategy, is widely recognised as the most effective procedure for obtaining high quality solutions in a relatively short time. Accordingly, we analyse the contribution of the method's neighbourhood structure to its overall effectiveness. Our findings show, surprisingly, that the NS neighbourhood causes the method's choice of an initialisation procedure to have an important influence on the best solution the method is able to find. By contrast, the method's choice of a strategy to generate a critical path has a negligible influence. Empirical testing further discloses that over 99.7% of the moves chosen from this neighborhood (by the NS rules) are disimproving-regardless of the initial solution procedure or the critical path generation procedure employed. We discuss implications of these findings for developing new and more effective job-shop algorithms.

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

U2 - 10.1023/A:1009617209268

DO - 10.1023/A:1009617209268

M3 - Article

VL - 6

SP - 457

EP - 480

JO - Journal of Heuristics

JF - Journal of Heuristics

SN - 1381-1231

IS - 4

ER -