摘要
ＢＩＮＰＡＣＫＩＮＧ中γ_ｍ≤１．２０的直接证明刘明堂，越民义（中国科学院应用数学研究所，北京１０００８０）ＡＤＩＲＥＣＴＰＲＯＯＦＯＦＴＨＥＩＮＥＱＵＡＬＩＴＹγ_ｍ≤１．２０ＩＮＭＵＬＴＩＰＲＯＣＥＳＳＯＲＳＣＨＥＤＵＬＩＮＧ￥ＬＩＵＭＩＮＧＴＡＮ...
This paper considers one of the basic, well studied problems in scheduling theory, that of nonpreemptively scheduling n independent tasks on m identical parallel processors with the objective of minimizing the 'makespan'. Coffman, Garey and Johnson described an algorithm MULTIFIT, which gives a better worst case performance than the LPT-algorithm. The upper bound 1.22 obtained by them was improved by Yue Minyi, Hans Kellerer and Zhongliang Yu.They gave the bound 1.20 a shorter proof in [3], by means of the weight function. In this paper we will analyse the structure of bin packing directly and give the bound 1.20 a proof without using the weight function.
出处
《应用数学学报》
CSCD
北大核心
1994年第1期9-14,共6页
Acta Mathematicae Applicatae Sinica
基金
国家自然科学基金
