排序方式： 共有3条查询结果，搜索用时 31 毫秒
1
1.
机器在一段时间不可用条件下的单机调度问题 总被引：1，自引：0，他引：1
文章对机器在一段给定时间内不可用情况下部分可恢复模式的单机调度问题进行了研究,当目标函数是最小化调度长度时,首先证明了LPT规则的误差上限是α/2,并举例说明该界限是紧的;同理可证该规则对不可恢复模式调度问题的误差上限是1/2,而不是有关文献所证明的1/3,同时上例也是1/3误差上限的反例;其次提出了一个启发式算法,该算法以LPT规则得到的解作为初始解,并结合基于成对交换技术的邻域搜索对解进行改进;当目标函数是最小化加权完成时间之和时,首先证明了最优调度的一个性质,并据此提出了动态规划算法。 相似文献
2.
研究了机器带有一个不可用时间段的单机最小化最大完工时间调度问题,并假定被中断工件是部分可续的,即其已加工部分在机器重新可用之后需部分进行重新加工.文中简单说明了此问题为NP-难问题,并证明了最大加工时间优先LPT规则的误差上限是α/2（其中α为重加工系数）,且举例说明该界限是紧的。在此基础上,简单地说明了该算法对不可续型问题的误差上限是1/2,而不是有关文献所证明的1/3,同时上例也是1/3误差上限的反例。还提出了一个启发式算法,实验结果证明了此算法的高效性,对不同参数对此算法性能的影响也进行了分析。 相似文献
3.
研究了机器带有一个不可用时间段的单机最小化加权完工时间和调度问题,并假定被中断工件是部分可续的,即其已加工部分在机器重新可用之后需进行部分重新加工.文中简单说明此问题为NP-难问题,并提出了一种动态规划算法和一种分枝定界算法来求得此问题的最优解.实验结果证实了这两种算法的正确性及有效性,且表明分枝定界算法要优于动态规划算法. 相似文献
1