竝列處理機械에서 最大納期遲延 時間의 最小化에 관한 硏究

Abstract

The purpose of this study is to develope efficient approximate and exact algorithms for the problem of scheduling n independent jobs on m unequal parallel processors to minimize maximum lateness. We incorporate opportunity cost concept to develop a new efficient heuristic. For an exact algorithm we use the result of new heuristic as an upper bound and the result of Lagrangean dual as an lower bound in branch and bound method. With the heuristic and exact algorithm we have following computational experiences.

First, by combining new heuristic with De and Mortons results we improve the quality of heuristic algorithms very well.

Second, this study gets tight lower bound which are almost similar to optimal solution in many cases.

Third, with this algorithm we can enhance the scale of the problem which is optimized.