Quick value‐setting algorithms for the longest path problem of job‐shop scheduling

Shiu Hong Choi (Department of Industrial and Manufacturing Systems Engineering, The University of Hong Kong, Hong Kong, People's Republic of China)
Feng Yu Yang (Department of Industrial and Manufacturing Systems Engineering, The University of Hong Kong, Hong Kong, People's Republic of China)

Journal of Manufacturing Technology Management

ISSN: 1741-038X

Publication date: 1 December 2005

Abstract

Purpose

The disjunctive graph is a network representation of the job‐shop scheduling problem, while the longest path problem (LPP) is one of the most important subjects in this research field. This paper aims to study the special topological structure of the disjunctive graph, and proposes a suite of quick value‐setting algorithms for solving the LPPs commonly encountered in job‐shop scheduling.

Design/methodology/approach

The topological structure of the disjunctive graph is analyzed, and some properties and propositions regarding LPPs are presented. Subsequently, algorithms are proposed for solving LPPs encountered in job‐shop scheduling.

Findings

The proposed algorithms significantly improve the efficiency of the shifting‐bottleneck procedure, making it practicable to realise real‐time scheduling and hence effective operations of modern manufacturing systems.

Originality/value

The paper demonstrates that it is possible to develop very efficient algorithms by imposing a special topological structure on the network.

Keywords

Citation

Hong Choi, S. and Yu Yang, F. (2005), "Quick value‐setting algorithms for the longest path problem of job‐shop scheduling", Journal of Manufacturing Technology Management, Vol. 16 No. 8, pp. 956-972. https://doi.org/10.1108/17410380510627906

Download as .RIS

Publisher

:

Emerald Group Publishing Limited

Copyright © 2005, Emerald Group Publishing Limited

Please note you might not have access to this content

You may be able to access this content by login via Shibboleth, Open Athens or with your Emerald account.
If you would like to contact us about accessing this content, click the button and fill out the form.
To rent this content from Deepdyve, please click the button.