首页   按字顺浏览 期刊浏览 卷期浏览 Bounds on the performance of a heuristic to schedule precedence-related jobs on paralle...
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)



返 回