带准备时间的平行机排序的LPT算法

The LPT-bound of parallel machines scheduling with nonsimultaneous machine available time

本文考虑带准备时间的平行机排序问题，讨论在使最早机器完工时间达到最大目标下的优化问题．这是ＮＰ－ｈａｒｄ问题，本文证明ＬＰＴ排序解至少是最优解的倍．

We consider the problem of scheduling n independent jobs on m identical machines in order to maximize the earliest processor completion time. The jobs are available at time zero,but some machines may not be available at time zero. In this paper,we show that the worst case ratio of LPT algorithm is greater than