遗传算法求解混合流水车间调度问题(HFSP)一:问题介绍

混合流水车间调度问题(Hybrid Flow-shop Scheduling Problem, HFSP)是车间调度中的一类经典问题。混合流水车间调度问题,在一道工序有一台或多台机器,工件的加工需要满足一定的工艺顺序。

假设和约束

  1. 一个工件在一道工序上被任意一个机器加工。
  2. 一个机器在某一时刻只能空闲或加工一个工件。
  3. 工件必须按照加工工序顺序进行加工。
  4. 同一道工序中机器都相同。
  5. 工件加工过程不允许中断。
  6. 如果多个工件同时需要被加工,则按优先级顺序进行加工。

需要解决的问题

确定零件的加工优先级,以使整体加工时间最短。

解决思路

在第一道工序中,所有的工件同时等待被加工,则按照优先级进行加工;在第二道和之后的工序中,由于上一道工序中工件完工时间不同,上一道工序先加工完的工件先进行本工序加工。求出整体完工时间作为目标函数值,运用遗传算法求解以使目标函数值最小。

“遗传算法求解混合流水车间调度问题(HFSP)一:问题介绍”的4个回复

  1. 您好!我在学习混合流水车间调度问题,运行了您的代码后发现每代最优解并不收敛,想请教一下 这个现象 的原因。

    1. 您好,非常开心能与您交流。但是您的问题较为模糊,不收敛的可能性有很多,如果算法运行过程中没出错,那么可能是目标函数值/适应度按错误方向排序,或者选择算在在选择时按错误方向选择。

      1. 感谢您的回复!
        我运行了您给出的源码,根据最优时间变化图发现每代最优时间随着迭代次数增长并没有很好的收敛,波动性较大。
        请问您看这个现象?

        1. 你好。这种情况可能是例子过于简单造成的,由于例子过于简单,所以很可能最开始几代就找到了较好的解(俗话说“蒙对了”)。我一般通过两种方法确定算法究竟有没有正确运转:
          1. 绘制目前找到的最优目标函数值随代数变化图,而不是每代最优目标函数值变化曲线。如果算法运转正常,那么曲线应该是收敛的。
          2. 绘制中群内平均目标函数值随代数变化图。如果算法运转正常,那么曲线应该是收敛的。

          我现在回看原文,发现原文并没有收敛图,我想我当时应该也有这个问题,可能是通过上面两种方法解决的。

          ======

          我在博客回复您后,博客没有自动发邮件功能,有时我会手动发送回复到您的邮箱,您可以直接通过邮箱与我交流,这样快些。

发表评论

电子邮件地址不会被公开。 必填项已用*标注