排序的贪婪算法的参数上界

Parametric Bounds on Greedy Scheduling Algorithm

本文研究平行机排序中最著名的贪婪算法─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.