| 时间相关的单机排序的最坏竞争比分析 |
| |
| 引用本文： | 张新功.时间相关的单机排序的最坏竞争比分析[J].重庆师范大学学报(自然科学版),2013,30(5). |
| |
| 作者姓名： | 张新功 |
| |
| 作者单位： | 重庆师范大学数学学院,重庆,401331 |
| |
| 基金项目： | 国家自然科学基金天元专项，重庆市教委自然科学基金，重庆师范大学校级资助项目 |
| |
| 摘 要： | 本文研究了工件的加工时间具有开工时间和加工所在位置相关的单机排序问题.工件的加工时间是序列中加工所在的位置和开工时间的非增函数,目标函数为最小化的误工工件个数和最小化总误工.本文对于所研究的2个目标函数利用Moore-Hodgson算法和EDD规则分别提出的启发式算法,对于目标函数位误工工件个数情形给出了最坏竞争比近似于2,最小化总误工给出非常数的最坏竞争比.进一步如果工件的加工时间和工期具有一致关系,分别给出了2个多项式时间算法.
|
| 关 键 词： | 排序 时间相关排序 最坏竞争比 多项式时间算法 |
The Worst-case Performance Ratio with Time-dependent Single-scheduling Problems |
| |
| ZHANG Xin-gong.The Worst-case Performance Ratio with Time-dependent Single-scheduling Problems[J].Journal of Chongqing Normal University:Natural Science Edition,2013,30(5). |
| |
| Authors: | ZHANG Xin-gong |
| |
| Abstract: | |
| |
| Keywords: | scheduling time-dependent scheduling worst-case performance ratios polynomial time algorithm |
| 本文献已被 万方数据 等数据库收录！ |
|
