| 可中断的多任务平行机排序问题 |
| |
| 引用本文： | 仲维亚,马文慧,霍志明.可中断的多任务平行机排序问题[J].运筹学学报,2013,17(3):115-123. |
| |
| 作者姓名： | 仲维亚 马文慧 霍志明 |
| |
| 作者单位： | 1. 上海大学理学院数学系, 上海, 200444 |
| |
| 基金项目： | 上海大学第六届研究生创新基金项目 |
| |
| 摘 要： | Leung等(Preemptive multiprocessor order scheduling to minimize total weighted flowtime J]. European Journal of Operational Research, 2008, 190: 40-51)研究了如下问题: 有 n 个订单, 其中每个订单 i 含有 n_i 个不同的工件. 所有的订单在零时刻已经到达, 并且工件的加工是可中断的. 每个订单 i有一个权重 \omega_i, 定义订单 i 的完工时间 C_i 为订单 i 最后一个完工工件的完工时间. 目标是找到一个可行排序使得加权总完工时间\sum\limits_{i=1}^n \omega_iC_i 最小. Leung等证明了这个问题是NP-难的, 给出了一个近似算法, 并且分析了该算法的最坏情况界. 但是定理2的证明存在一些错误. 证明了尽管定理2的证明过程存在错误, 但是其结论仍然正确. 另外, 对上述模型的一种特殊情形给出了更好的近似算法.
|
| 关 键 词： | 排序 近似算法 NP-难 |
A preemptive multiprocessor order parallel machine scheduling problem |
| |
| ZHONG Weiya,MA Wenhui,HUO Zhiming.A preemptive multiprocessor order parallel machine scheduling problem[J].OR Transactions,2013,17(3):115-123. |
| |
| Authors: | ZHONG Weiya MA Wenhui HUO Zhiming |
| |
| Institution: | 1. Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, China |
| |
| Abstract: | |
| |
| Keywords: | scheduling approximation algorithm NP-hard |
|
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
|
