A branch-and-bound approach to the job-shop scheduling problem
作者:
SAID ASHOUR,
S. R. HIREMATH,
期刊:
International Journal of Production Research
(Taylor Available online 1973)
卷期:
Volume 11,
issue 1
页码: 47-58
ISSN:0020-7543
年代: 1973
DOI:10.1080/00207547308929945
出版商: Taylor & Francis Group
数据来源: Taylor
摘要:
The shop scheduling problem with which this paper is concerned is to determine a sequence ofJjobs on each of theMmachines such that the schedule time is minimized. The machine ordering of each job is pre-specified but independent of those of other jobs. A branch-and-bound algorithm, using a powerful bounding procedure, has been developed for obtaining an optimal solution. An illustrative example is solved. Computational experience with this algorithm shows that it is practical in problems of moderate size. However, for larger problems, the algorithm can be applied without backtracking in which an optimal or near-optimal solution may be obtained. The quality of solutions obtained by the branch-and-bound algorithm without backtracking has been investigated. The optimal-producing algorithm is compared favourably with other published methods The number of nodes explored and the computational time are considered as bases for evaluation.
点击下载:
PDF (396KB)
返 回