ISSN:
1741-038X
Source:
Emerald Fulltext Archive Database 1994-2005
Topics:
Technology
,
Economics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1108/17410380510627906
Permalink