共查询到10条相似文献,搜索用时 406 毫秒
1.
研究了机器带有一个不可用时间段的单机最小化最大完工时间调度问题,并假定被中断工件是部分可续的,即其已加工部分在机器重新可用之后需部分进行重新加工.文中简单说明了此问题为NP-难问题,并证明了最大加工时间优先LPT规则的误差上限是α/2(其中α为重加工系数),且举例说明该界限是紧的。在此基础上,简单地说明了该算法对不可续型问题的误差上限是1/2,而不是有关文献所证明的1/3,同时上例也是1/3误差上限的反例。还提出了一个启发式算法,实验结果证明了此算法的高效性,对不同参数对此算法性能的影响也进行了分析。 相似文献
2.
3.
集约生产计划问题参数规划模型的转换与分解算法 总被引:1,自引:0,他引:1
为求解模糊的集约生产计划问题,从模糊集约生产计划已清晰化后的参数规划模型着手,将参数规划模型进行分解,提出了分解算法,并将分解算法与分枝定界法进行了比较分析,仿真结果验证了这种算法的有效性与优越性. 相似文献
4.
5.
调整时间与顺序相关的flowshop调度的精确算法 总被引:2,自引:1,他引:1
调整时间与顺序相关的流水车间调度问题(flowshop scheduling with sequence dependent setup times,FSSDST)在过程制造业中有着广泛的应用背景,是一类比较复杂的调度问题,对目标函数是最小化最大流程时间(makespan)的同排列流水车间FSSDST调度问题进行了研究,建立了FSSDST的混合整数线性规划模型(MILP),提出了两种确定原问题的下界方法:(1)按照第m台机器(最后一台机器)定界;(2)按照全部机器定界,根据这两个下界,提出并实现了分支定界算法,为了提高分支定界算法的效率,提出了两种改进上界的策略:(1)改进初始上界法;(2)改进动态上界法,实现了上述所有算法,并通过随机产生的例子获得了各种算法的性能。 相似文献
6.
并行加工经济批量问题的最优算法 总被引:1,自引:0,他引:1
考察了 n - period经济加工批量问题并给出一种复杂度 O(mnlogn )的优化算法 .对于无能力约束的动态经济加工批量问题 (Wagner- Whitin问题 ) ,最早由 Wagner和 Whitin(195 8)提出 ,并给出一个基于动态规划 ,复杂度为 O(n2 )的算法 .最近 ,有许多人重新对该问题进行了研究 ,并以多种方式给出了复杂度为 O(nlogn )的算法 .本文在以上研究的基础上 ,针对柔性加工多机并行加工情况 ,给出了一种复杂度为 O(mnlogn )的 Wagner- Whitin问题的解法 . 相似文献
7.
8.
研究了家庭护理中的医疗服务人员调度问题,考虑了随机的客户服务时间和最迟开始服务时间约束.建立了带补偿的随机规划模型,得到了客户期望迟到惩罚成本的近似计算表达式,并分析了期望惩罚成本的性质.根据问题的特点,基于列生成算法思想建立问题的集分割最优化主问题模型和生成新列的最短路子问题模型,并设计标签算法对子问题加以求解.将列生成算法嵌入到分枝定界过程中形成分枝定价算法得到问题整数可行解.通过数值实验,验证了所提出客户期望迟到惩罚成本近似表达式和分枝定价算法的有效性. 相似文献
9.
10.
束搜索(Beam search)方法是在分枝定界方法基础上发展起来的一种启发式优化方法,由于这类方法在确定分枝搜索方向时仅考虑了当前的局部信息,因此易陷入局部极值.在过滤束搜索(filteredbeam search)方法的基础上提出了一种改进思路,即在局部评价和全局评价的基础上增加部分回溯.通过引入有效的部分回溯策略,部分被舍弃的结点被重新评估并最终找到更好的解,从而可避免过早陷入局部极值.通过对48个标准问题的计算和比较,结果显示改进后的方法能有效提高解的质量. 相似文献