本文研究带机器准备时间的m台平行机系统在线和半在线排序问题.对在线排序问题,我们证明了LS算法的最坏情况界为2-1/m.对已知工件加工时间递减,已知总加工时间和已知工件最大加工时间三个半在线模型,我们分析了它们的下界和所给算法的最坏情况界.对其中两台机情形均得到了最好近似算法.

This paper investigates on-line and semi on-line scheduling problems on parallel machines with non-simultaneous machine available times. In on-line version, we prove that the worst-case ratio of LS algorithm is 2 - 1/m. Three semi on-line scheduling problems are studied, where the jobs are ordered in decreasing processing times, the total processing time or the largest processing time being known in advance. For each problem, we analyze its lower bound and give its approximation algorithms. The algorithms are all the best possible ones for a two-machine case.