中文摘要：

对于在m台平行机上工件有单调非减的到达时间和单调非增的加工时间的半在线排序问题进行了研究,其目标函数是要令所有机器中最大完工时间达到最小。对任意半在线工件序列和任意m台机器,证明了3/2-1/2 m为LS算法的最坏性能比的上界。

英文摘要：

In this paper, we consider semi-online scheduling on m machines for jobs with non-decreasing release times and non-increasing processing times. The aim is to minimize the last completion time of all jobs. We show that, for any semi- online job list L= {J1,J2,…… ,Jn } and m machines, 3/2-1/2m is an upper bound of the worst case ratio of LS algorithm.