摘要
本文研究平行机排序中最著名的贪婪算法─LPT算法的性质．经典排序中机器随时可以开始加工．本文研究机器不都是从开始就可以加工，而是需要一个准备时间，也就是说本文研究各台机器最早可以开工的时间可以不同的同型号平行机（ideaticalParallel）的排序问题，分析LPT算法得到的近似解的参数上界．
In this paper we concern with the problem of scheduling on m identical parallel machineswith nonsimultaneous machine available times. We derive a new parametric bound on thegreedy algorithm-LPT. The paper is closed by some numerical results and comparisionsamong the new bound and others.
出处
《运筹学学报》
CSCD
1999年第1期56-64,共9页
Operations Research Transactions
基金
国家自然科学基金!19701028
19771057
关键词
排序
贪婪算法
参数上界
平行机排序
Scheduling, Greedy algorithm, Worst-case analysis, Parametric bound.
