A modified shifting bottleneck heuristic and disjunctive graph for job shop scheduling problems with transportation constraints

Affiliation auteurs!!!! Error affiliation !!!!
TitreA modified shifting bottleneck heuristic and disjunctive graph for job shop scheduling problems with transportation constraints
Type de publicationJournal Article
Year of Publication2014
AuteursZhang Q, Manier H, Manier M-A
JournalINTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
Volume52
Pagination985-1002
Date PublishedFEB 16
Type of ArticleArticle
ISSN0020-7543
Mots-clésbounded processing times, disjunctive graph, job shop scheduling, shifting bottleneck procedure, transportation
Résumé

In this paper, we consider job shop scheduling problems with transportation constraints and bounded processing times. We use a modified disjunctive graph to represent the whole characteristics and constraints of such considered problems. Compared with classical disjunctive graph, it contains not only processing nodes, but also transportation and storage nodes. There are also positive and negative arcs for bounded processing time constraints, transportation times and minimum and maximum allowed storage times before and after each processing task. The objective is to minimise makespan. A feasible solution for makespan is found, if its associated graph contains no positive cycle. A modified shifting bottleneck procedure is used to solve the studied job shop problems which are represented by disjunctive graphs. It is coupled with a heuristic for assigning and sequencing transportation tasks iteratively. To validate our approach, several types of benchmarks with fixed or bounded processing times are tested, corresponding to flexible manufacturing systems, robotic cells and surface treatment facilities. Computational results show that the modified disjunctive graph and the proposed method are efficient and can deal with various cases.

DOI10.1080/00207543.2013.828164