| 单机带库存约束的排序问题 |
| |
| 引用本文： | 王红军,张安,陈永,陈光亭.单机带库存约束的排序问题[J].杭州电子科技大学学报,2014(6):36-38. |
| |
| 作者姓名： | 王红军 张安 陈永 陈光亭 |
| |
| 作者单位： | 杭州电子科技大学理学院,浙江杭州,310018 |
| |
| 摘 要： | 研究了一类单台机上带有库存约束的排序问题,目标函数是极小化加权完工时间总和。针对问题,首先证明了问题是NP-困难的,接着给出贪婪算法,证明了该算法的最坏情况界是无穷大,但随机试验表明算法的平均性能是令人满意的。
|
| 关 键 词： | 排序 库存约束 计算复杂性 贪婪算法 |
Single Machine Scheduling with Inventory Constraints |
| |
| Wang Hongjun,Zhang An,Chen Yong,Chen Guangting.Single Machine Scheduling with Inventory Constraints[J].Journal of Hangzhou Dianzi University,2014(6):36-38. |
| |
| Authors: | Wang Hongjun Zhang An Chen Yong Chen Guangting |
| |
| Affiliation: | ( School of Science, Hangzhou Dianzi University, Hangzhou Zhejiang 310018, China) |
| |
| Abstract: | This paper considers a single-machine scheduling problem subject to inventory constraints, the objective is to minimize the total weighted completion time. For this problem, both an NP-hardness proof and a greedy algorithm are provided. It＇s proved that the algorithm is unbounded in the sense of worst case, but computational experiments show that it performances good in the average sense. |
| |
| Keywords: | scheduling inventory constraints computational complexity greedy algorithm |
| 本文献已被 CNKI 维普 等数据库收录！ |
|
