解の類似度を考慮した生産再スケジューリング問題に対する遺伝アルゴリズムの開発

考虑解相似性的生产调度问题遗传算法的开发

基本信息

批准号：
15760292
负责人：
飯間等
金额：
$ 1.41万
依托单位：
Kyoto Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2003
资助国家：
日本
起止时间：
2003 至 2005
项目状态：
已结题

项目摘要

まず、並列機械工程において、納期遅れ和とスケジュール変更量を最小化する二目的再スケジューリング問題に対する遺伝アルゴリズムの個体表現法を考察した。並列機械問題では、各製品を処理する機械と各機械上の処理順序を決定する必要がある。したがって、通常の並列機械問題に対する遺伝アルゴリズムの個体表現法には、(1)処理順序を遺伝子列で与えて処理機械をヒューリスティックに定める方法、(2)処理機械を遺伝子列で与えて処理順序をヒューリスティックに定める方法、(3)処理順序と処理機械の両方を遺伝子列で与える方法の3種類が考えられる。そこで、通常の問題に(1)あるいは(2)を用いた後の再スケジューリング問題に適切な個体表現法を調査した結果、(1)の場合には(1)が、(2)の場合には(1),(3)が良いことを確認した。次に、これまで対象としてきたジョブショップ工程と並列機械工程が組み合わされたフレキシブルジョブショップ工程に対する遺伝アルゴリズムの構成法を提案した。基本的なアルゴリズムの構成は従来有効とされているものを用い、そのアルゴリズムに本研究で提案した個体表現法および選択則を導入して全体のアルゴリズムを完成させた。また、より良いパレート解集合を得るために、複数の個体群を用いた分散遺伝アルゴリズムを提案した。特に、多様なパレート解集合を発見するために、他の部分個体群が発見したパレート解との変更量を計算し、その変更量が大きい解を選択することで他の部分個体群と異なる領域で解を探索させる選択則を提案し、計算例によりその有効性を確認した。最後に、スケジューリングソフトウェアの試作に着手し、その入出力部分の設計を検討した。

首先，我们考虑了遗传算法的个体表示方法，用于最小化并行机器进程中的交付延迟和调度变化之和的双目标重新调度问题。在并行机器问题中，需要确定将加工每种产品的机器以及每台机器上的加工顺序。因此，遗传算法针对普通并行机问题的个体表示方法包括（1）将处理顺序作为基因序列给出并启发式地确定处理机的方法，以及（2）将处理机作为基因给出的方法存在三种可能的方法：(3)确定启发式的方法，以及(3)使用基因序列提供处理顺序和处理机器的方法。因此，在对正常问题使用（1）或（2）之后，研究了重新安排问题的适当个体表示方法的结果，我们发现证实（1）和（3）是好的。接下来，我们提出了一种为灵活的作业车间流程配置遗传算法的方法，该方法结合了我们一直瞄准的作业车间流程和并行机器流程。我们使用了过去被认为有效的基本算法配置，并通过引入本研究提出的个体表示方法和选择规则来完成整体算法。我们还提出了一种使用多个群体的分布式遗传算法来获得更好的帕累托解集。特别是，为了发现多样化的Pareto解集，我们计算了其他子群体找到的Pareto解的变化量，并选择变化量较大的解，我们提出了一种搜索解的选择规则并证实了其有效性。通过计算实例。最后，我们开始创建调度软件的原型，并考虑其输入和输出部分的设计。