Citation
Lower And Upper Bounds For The Job-shop Scheduling Problem With Sequence-dependent Setup Times. In proceedings of the 2nd Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2005), 18 -21 July 2005, New York, USA, pages 316-321, 2005.
Paper
Abstract
We present several methods to minimize the makespan in a job-shop problem with sequence-dependent setup times. We first present active, semi-active and non-delay schedule generation scheme, from which priority-rule based sampling heuristics are derived. Focusing on the disjunctive graph representation of the problem, we discuss the loss of dominance properties of efficient neighborhoods for the standard jobshop problem. We define an alternative interchange neighborhood and we propose a simple tabu search method. We use the traveling salesman problem with time windows relaxation of the problem to derive new lower bounds that we embed in a dichotomizing exact tree search method. All together, the proposed methods significantly improve the best known results on all the 10 previously unsolved instances of Brucker and Thiele, 1996.
You can download the pdf of this publication from here
doi
This publication does not have a doi, so we cannot provide a link to the original source
What is a doi?: A doi (Document Object Identifier) is a unique identifier for sicientific papers (and occasionally other material). This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi). See http://dx.doi.org/ for more information
URL
This pubication does not have a URL associated with it.
The URL is only provided if there is additional information that might be useful. For example, where the entry is a book chapter, the URL might link to the book itself.
Bibtex
@INPROCEEDINGS{2005-316-321-P, author = {C. Artigues and F. Buscaylet and D. Feillet},
title = {Lower And Upper Bounds For The Job-shop Scheduling Problem With Sequence-dependent Setup Times},
booktitle = {In proceedings of the 2nd Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2005), 18 -21 July 2005, New York, USA},
year = {2005},
editor = {G. Kendall and L. Lei and M. Pinedo},
pages = {316--321},
note = {Paper},
abstract = {We present several methods to minimize the makespan in a job-shop problem with sequence-dependent setup times. We first present active, semi-active and non-delay schedule generation scheme, from which priority-rule based sampling heuristics are derived. Focusing on the disjunctive graph representation of the problem, we discuss the loss of dominance properties of efficient neighborhoods for the standard jobshop problem. We define an alternative interchange neighborhood and we propose a simple tabu search method. We use the traveling salesman problem with time windows relaxation of the problem to derive new lower bounds that we embed in a dichotomizing exact tree search method. All together, the proposed methods significantly improve the best known results on all the 10 previously unsolved instances of Brucker and Thiele, 1996.},
owner = {Faizah Hamdan},
timestamp = {2012.05.21},
webpdf = {2005-316-321-P.pdf} }