S-Space College of Business Administration/Business School (경영대학/대학원) Institute of Information and Operation Management (경영정보연구소) Journal of information and operations management (경영정보논총) Journal of information and operations management vol.06 (1996) (경영정보논총)
竝列處理機械에서 最大納期遲延 時間의 最小化에 관한 硏究
- 안상형; 이송근; 심안섭
- Issue Date
- 서울대학교 경영정보연구소
- Journal of information and operations management, Vol.06, pp. 81-112
- 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 Morton’s 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.