中文摘要：

研究以极大化最小机器负载为目标的机器带准备时间的同型机排序问题.证明了LS算法是求解该问题的最好的在线算法,它的最坏情况界为1/m.同时给出了求解两台机的预先知道工件最大加工时间,预先知道工件集的总加工时间以及预先知道工件从大到小到达这三种情形下最好的半在线算法,这三个算法的最坏情况界分别为2/3,2/3以及3/4.

英文摘要：

The paper considers the parallel machine scheduling problem with non-simultaneous machine available time and the object is to maximize the earliest machine completion time. In online version, the worst-case ratio of LS being 1/m is proved, so LS is the optimal algorithm for this problem. Three different semi-online conditions -- the largest processing time known in advance, the total processing time known in advance and the jobs ordered in non-increasing processing time are investigated. For each problem the optimal algorithm （worst-case ratio 2/3, 2/3, 3/4） for two machine case is presented.