| 机器在一段时间不可用条件下的单机调度问题 |
| |
| 引用本文： | 马英,杨善林,储诚斌. 机器在一段时间不可用条件下的单机调度问题[J]. 合肥工业大学学报(自然科学版), 2007, 30(8): 1010-1014 |
| |
| 作者姓名： | 马英 杨善林 储诚斌 |
| |
| 作者单位： | 合肥工业大学,管理学院,安徽,合肥,230009;合肥工业大学,管理学院,安徽,合肥,230009;特鲁瓦工业大学,工业系统优化实验室,法国,特鲁瓦,100100 |
| |
| 摘 要： | 文章对机器在一段给定时间内不可用情况下部分可恢复模式的单机调度问题进行了研究,当目标函数是最小化调度长度时,首先证明了LPT规则的误差上限是α/2,并举例说明该界限是紧的;同理可证该规则对不可恢复模式调度问题的误差上限是1/2,而不是有关文献所证明的1/3,同时上例也是1/3误差上限的反例;其次提出了一个启发式算法,该算法以LPT规则得到的解作为初始解,并结合基于成对交换技术的邻域搜索对解进行改进;当目标函数是最小化加权完成时间之和时,首先证明了最优调度的一个性质,并据此提出了动态规划算法。
|
| 关 键 词： | 单机调度 部分可恢复模式 LPT规则 动态规划 |
| 文章编号： | 1003-5060(2007)08-1010-05 |
| 修稿时间： | 2006-08-29 |
Single machine scheduling with an availability constraint |
| |
| MA Ying,YANG Shan-lin,CHU Cheng-bin. Single machine scheduling with an availability constraint[J]. Journal of Hefei University of Technology(Natural Science), 2007, 30(8): 1010-1014 |
| |
| Authors: | MA Ying YANG Shan-lin CHU Cheng-bin |
| |
| Abstract: | |
| |
| Keywords: | single machine scheduling semiresumable case longest processing time(LPT) rule dynamic programming algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
