Construction method of genetic algorithms for large-scale complex production scheduling problems

大规模复杂生产调度问题的遗传算法构建方法

• 批准号: 11450154
• 负责人: SANNOMIYA Nobuo
• 金额: $ 4.22万
• 依托单位: Kyoto Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 1999
• 资助国家: 日本
• 起止时间: 1999 至 2001
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-11450154/
• 关键词: scheduling; job shop process; flowshop process; genetic algorithm; large-scale system; production system; diversity; multi-objective optimization; 多目的; 分解法; 組合せ最適化; 大規模性; 柔軟性

1. Proposition of a new selection procedure capable of keeping a diverse populationIt was shown that the proposed selection procedure (called Partial Enumeration Selection Method : PESM) can keep a high diversity population through the generations without deteriorating the accuracy of the solution. The robustness of the algorithm was also shown for variations of several schedule parameters.2. Proposition of decomposition and search space reduction methodsIt was shown from computational experiments for large-scale scheduling problems that the proposed decomposition and search space reduction methods work well with genetic algorithms.3. Design of genetic algorithms capable of dealing flexibly with complex constraintsThe design of genetic algorithms was proposed in such a way that the scheduling problems can be solved by only adding a module related to the added constraints. The scheduling problems of a job shop process with parallel machines and the worker allocation problem in a job shop process were solved by the proposed algorithm. Moreover a new decoding method was proposed for no-buffer job shop problems.4. Application to multi-objective optimization problemsThe PESM-based genetic algorithm was applied to solving multi-objective flowshop problems and smooth Pareto fonts were obtained.

1. 提出一种保持种群多样性的新选择方法。研究表明，所提出的选择方法（称为部分枚举选择法：PESM）可以在不降低解的准确性的情况下保持种群的高多样性。对多个调度参数的变化也证明了该算法的鲁棒性。分解和搜索空间约简方法的提出针对大规模调度问题的计算实验表明，所提出的分解和搜索空间约简方法可以很好地与遗传算法配合使用。能够灵活处理复杂约束的遗传算法设计提出了只需增加与所增加的约束相关的模块即可解决调度问题的遗传算法设计。该算法解决了并行作业车间的调度问题和作业车间的工人分配问题。此外，针对无缓冲作业车间问题，提出了一种新的解码方法。在多目标优化问题中的应用将基于pesm的遗传算法应用于多目标流水作业问题的求解，得到了光滑的Pareto字体。

项目成果

Y.Zhao: "An Improvement of Genetic Algorithms by Search Space Reductions in Solving Large-scale Flowshop Problems"電気学会論文誌C. 121C巻6号. 1010-1015 (2001)

Y.Zhao：“通过减少搜索空间来解决大规模流水作业问题的遗传算法”，日本电气工程师协会学报 C. Vol. 121C No. 6. 1010-1015 (2001)

H.Iima: "Genetic Algorithm for a Scheduling Problem in an Electric Wire Production System with Three Subprocesses"Preprints of 14th World Congress of IFAC. A. 279-284 (1999)

H.Iima：“具有三个子流程的电线生产系统中的调度问题的遗传算法”，IFAC 第 14 届世界大会预印本。

C.A.Brizuela: "Controlling Selection Pressure and Diversity in GA's by Partial Enumeration"計測自動制御学会論文集. 36巻4号. 367-369 (2000)

C.A. Brizuela：“通过部分枚举控制 GA 的选择压力和多样性”，仪器与控制工程师学会汇刊，第 36 卷，第 4 期，367-369 (2000)。

C.A.Brizuela: "From the Classical Job Shop to a Real Problem : A Genetic Algorithm Approach"Proc.of 39th IEEE Conf.on Decision and Control. 4174-4180 (2000)

C.A.Brizuela：“从经典作业车间到实际问题：遗传算法方法”第 39 届 IEEE Con​​f.on 决策与控制会议论文集。

N.Sannomiya: "Application of Genetic algorithm to a Large-scale Scheduling Problem for a Metal Mold Assembly Process"Proc. of 38th IEEE Conf. on Decision and Control. 2283-2293 (1999)

N.Sannomiya：“遗传算法在金属模具装配过程的大规模调度问题中的应用”Proc。