摘要
对于在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.
出处
《系统工程》
CSSCI
CSCD
北大核心
2016年第6期72-77,共6页
Systems Engineering
基金
国家自然科学基金资助项目(11471110)
湖南省科技厅项目(2012GK3122)
湖南省高等学校科学研究项目(12C0198)
关键词
到达时间非递减
加工时间非递增
半在线
LS算法
最坏性能比
Non-decreasing Release Time
Non-increasing Processing Time
Semi-online
LS Algorithm
Worst CasePerformance Ratio
