| 带有前后约束的延误排序问题的近似算法 |
| |
| 引用本文： | 张树霞,唐国春.带有前后约束的延误排序问题的近似算法[J].华东师范大学学报(自然科学版),2007,2007(1):51-55. |
| |
| 作者姓名： | 张树霞 唐国春 |
| |
| 作者单位： | 1. 华东师范大学,数学系,上海,200062;解放军镇江船艇学院,船艇指挥系,江苏,镇江,212003
2. 上海第二工业大学,管理工程研究所,上海,201209 |
| |
| 摘 要： | 把工件之间不带前后约束的延误排序的后移算法移植到带有前后约束的情况, 提出一个多项式时间的近似算法. 这个算法可以快速地得到这种延误问题的近似解.
|
| 关 键 词： | 延误问题 Emmons条件 前后约束 近似算法 延误问题 Emmons条件 前后约束 近似算法 |
| 文章编号： | 1000-5641（2007）01-0051-05 |
| 收稿时间： | 2005-08 |
| 修稿时间： | 2005-08 |
Approximation Algorithm for the Total Tardiness Scheduling(Chinese) |
| |
| ZHANG Shu-xia,TANG Guo-chun.Approximation Algorithm for the Total Tardiness Scheduling(Chinese)[J].Journal of East China Normal University(Natural Science),2007,2007(1):51-55. |
| |
| Authors: | ZHANG Shu-xia TANG Guo-chun |
| |
| Institution: | 1. Department of Mathematics, East China Normal University, Shanghai 200062, China; 2. Department of Watercraft Command, Zhenjiang Watercraft College, Zhenjiang 212003, China; 3. Institute of Management Engineering, Shanghai Second Polytechnic University, Shanghai 201209, China |
| |
| Abstract: | For the total tardiness scheduling with precedence constraints,an ap- proximation algorithm with polynomial complexity was presented by transplanting the backward-shift algorithm of the case without precedence constraints.The new algorithm can get an approximation solution for the scheduling quickly. |
| |
| Keywords: | total tardiness scheduling Emmons conditions precedence constraints approximation algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《华东师范大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《华东师范大学学报(自然科学版)》下载免费的PDF全文 |
