互联网 qkzz.net
全刊杂志网:首页 > 女性 > 文章正文
刊社推荐

作业车间调度转换瓶颈算法可行性研究


□ 黄 志 胡卫军

  收稿日期:2007-11-23;修回日期:2008-03-14

  基金项目:国家“973”计划资助项目( 2004CB318000)

  作者简介:黄志(1976-),男,河南信阳人,博士,主要研究方向为NP难高效算法、人工智能、计算机图形学、生物计算、运筹学(huangzhi9@gmail.com); 胡卫军(1973-),男, 湖北天门人,讲师,博士研究生,主要研究方向为高效算法、计算机图形学、人工智能.*

  (华中科技大学 计算机学院,武汉 430074)

  摘 要:讨论了转换瓶颈(SB)算法在解作业车间调度问题时需要解决的子问题。转换瓶颈算法是解决作业车间调度最小makespan(完工时间)问题的有效启发式算法。它是基于反复地解决某些单机调度问题这样的子问题。然而所解决的单机调度问题的解可能会导致算法最终得不到可行解,即使是单机调度最优解也可能得到不可行解。为此,给出了一个简单的反例证明了产生不可行解的情况,并对产生不可行解的原因作了详细分析。该研究有利于对转换瓶颈技术进行更好的理解和应用。

  关键词:作业车间调度; NP-难; 转换瓶颈

  中图分类号:TP301

  文献标志码:A

  文章编号:1001-3695(2008)10-2932-02

  Note on infeasibility problem of shifting bottleneck procedure

  for job shop scheduling

  HUANG Zhi, HU Wei-jun

  (School of Computer Science, Huazhong University of Science & Technology, Wuhan 430074, China)

  Abstract:This paper discussed the subproblem in job shop scheduling problem solved by shifting bottleneck procedure. Shif-ting bottleneck (SB) algorithm was a prominent algorithm for the minimum makespan problem of job shop scheduling. It was based on solving a series of one-machine scheduling problem. However the solution to the one-machine problem might result in the infeasible solution for the job shop scheduling problem. Even the solution was optimal, infeasibility could still be reached. This paper gave a simple counterexample to illustrate the infeasible case. It analyzed the reason of the infeasibility in details. The research is helpful in understanding and utilizing the shifting bottleneck technique.

......
很抱歉,暂无全文,若需要阅读全文或喜欢本刊物请联系《计算机应用研究》杂志社购买。
欢迎作者提供全文,请点击编辑
分享:
 

了解更多资讯,请关注“木兰百花园”
分享:
 
精彩图文


关键字
支持中国杂志产业发展,请购买、订阅纸质杂志,欢迎杂志社提供过刊、样刊及电子版。
关于我们 | 网站声明 | 刊社管理 | 网站地图 | 联系方式 | 中图分类法 | RSS 2.0订阅 | IP查询
全刊杂志赏析网 2017