Bounds on the performance of a heuristic to schedule precedence-related jobs on parallel machines
作者:
SUBHASHC. SARIN,
SALAHE. ELMAGHRABY,
期刊:
International Journal of Production Research
(Taylor Available online 1984)
卷期:
Volume 22,
issue 1
页码: 17-30
ISSN:0020-7543
年代: 1984
DOI:10.1080/00207548408942426
出版商: Taylor & Francis Group
数据来源: Taylor
摘要:
We propose a heuristic procedure that constructs a schedule for N unit jobs with arbitrary precedence on m identical processors in parallel. The criterion is the minimization of the total weighted completion times. The procedure translates the optimal solution on one processor into a solution on the m-processors. Two bounds on the worst-ease performance of the procedure are derived, with the second being the stronger of the two, but at the expense of requiring slightly more computing effort. In view of the fact that the one-processor solutions may be hard to obtain, the proposed heuristic is applied to one processor near optimal solutions and the experimental results presented indicate that the heuristic performs equally well.
点击下载:
PDF (409KB)
返 回