| 同速度的具有m台通用机的n组工件的排序问题 |
| |
| 引用本文： | 丁伟. 同速度的具有m台通用机的n组工件的排序问题[J]. 中山大学学报(自然科学版), 2008, 47(3): 19-22 |
| |
| 作者姓名： | 丁伟 |
| |
| 作者单位： | 中山大学数学系,广东,广州,510275;中山大学物理系,广东,广州,510275 |
| |
| 摘 要： | 改进了经典的LPT(Longest Processing Time)算法，利用“首先空闲”准则安排机器，而对于工件的安排则按照“长时间任务优先”的原则，讨论了将n组工件安排在n台速度相同的专用机，m台同速度的通用机上的优化排序问题，得到了利用该近似算法所得的解T与最优解T*的一个估计：T/T*≤(2m+1)/(m+1)。
|
| 关 键 词： | 启发式算法性能指 标 LS算法 LPT算法 通用机与专用机 |
| 文章编号： | 0529-6579(2008)03-0019-04 |
| 收稿时间： | 2007-10-15; |
| 修稿时间： | 2007-10-15 |
A Type of Scheduling Problem on m General-Purpose Machinery and n Group Tasks with Uniform Processors |
| |
| DING Wei. A Type of Scheduling Problem on m General-Purpose Machinery and n Group Tasks with Uniform Processors[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2008, 47(3): 19-22 |
| |
| Authors: | DING Wei |
| |
| Affiliation: | (Department of Mathematics ;Department of Physics,Sun Yat sen University,Gaungzhou 510275,China) |
| |
| Abstract: | The Cmax problem on many group jobs with m general purpose machinery and n special purpose machineries with the same speed was studied in this paper. This problem is always a NP Hard problem,and an approximate method need to be found. An improved LPT algorithm and the upper bound performance are given. The ratio of the approximate solution and the best solution is (2m+1)/(m+1). |
| |
| Keywords: | heuristic approach performance indexes LS algorithm LPT algorithm general purpose and special purpose machinery |
| 本文献已被 维普 万方数据 等数据库收录！ |
| 点击此处可从《中山大学学报(自然科学版)》浏览原始摘要信息 |
|
点击此处可从《中山大学学报(自然科学版)》下载全文 |
