A Precedence Graph Algorithm for the Shop Scheduling Problem
作者:
AshourSaid,
ParkerR. G.,
期刊:
Journal of the Operational Research Society
(Taylor Available online 1971)
卷期:
Volume 22,
issue 2
页码: 165-175
ISSN:0160-5682
年代: 1971
DOI:10.1057/jors.1971.34
出版商: Taylor&Francis
数据来源: Taylor
摘要:
AbstractThis paper is concerned with the development of a precedence graph algorithm for solving certain combinatorial problems. This algorithm is applied mainly to job-shop scheduling problems; however, the extension of its applicability can be demonstrated by considering project scheduling, travelling salesman and explosion problems. The algorithm employs linear graphs to construct the quantified precedence matrix, a powerful criterion to resolve the conflict between the tied operations, and the use of a quasi-Boolean procedure to evaluate the obtained sequence.Considerable experimentation is conducted to evaluate the performance of the algorithm. Significant results pertaining to the quality of solution, the computation time and the number of iterations and conflicts encountered in obtaining a solution are given.
点击下载:
PDF (3330KB)
返 回