具有通用机的多组工件的Q//C_(max)问题的近似算法  

Heuristic Algorithm of the Q//C_(max) Problem on Multi-Tasks with Uniform Processors

作　　者：丁伟[1] 

机构地区：[1]中山大学数学与计算科学学院,广东广州510275

出　　处：《中山大学学报（自然科学版）》2010年第1期5-8,共4页Acta Scientiarum Naturalium Universitatis Sunyatseni

基　　金：国家自然科学基金资助项目(10531040)

摘　　要：研究的目的在于解决实践中对多组任务的优化排序问题,即在最短的时间内完成所有给定的任务。由于这类问题往往都是NP完全问题,人们通常寻求其近似算法。提出了一种改进的LPT算法,利用"最大相对加工时间"准则和"首先空闲"准则,讨论了将n组工件安排在n台速度不同的专用机,一台速度小于专用机的通用机上的Cmax问题,得到了利用该近似算法所得的解T与最优解T*的一个估计:T/T*≤1+1/∑i∈Isi,其中I表示在最后完工的工件完工之前,在通用机上至少安排了一个工件的工件组的下标集合。由此得出采用该近似算法对工件排序,在最差情况下要比最优排序多出1/∑i∈Isi的时间。To study the C max problem on many-group jobs with one general-purpose machinery and n special-purpose machineries that they are with the different speeds. This problem is always NP-C problem, so the approximate method is usually to be found. An improved LPT algorithm and the upper bound performance are given. The ratio of the approximate solution and the best way is T/T^＊ ≤ 1 ＋ 1/∑ i∈1 si , it means that the complete time using this approximate method is 1/∑i∈1 si more than the best in worst condition.

关 键 词：启发式算法 性能指标 LPT算法 通用机 专用机 

分 类 号：O223[理学—运筹学与控制论]