• CN:11-2187/TH
  • ISSN:0577-6686

机械工程学报 ›› 2016, Vol. 52 ›› Issue (22): 186-197.doi: 10.3901/JME.2016.22.186

• 交叉与前沿 • 上一篇    下一篇

基于混合的多目标遗传算法的多目标流水车间逆调度问题求解方法*

牟健慧1, 郭前建1, 高亮2, 张伟1, 牟建彩3   

  1. 1. 西华大学流体及动力机械教育部重点实验室 成都 610039;
    2. 江苏大学国家水泵及系统工程技术研究中心 镇江 212013
  • 出版日期:2016-11-15 发布日期:2016-11-15
  • 作者简介:

    牟健慧(通信作者),女,1983年出生,博士研究生。主要研究方向为车间调度与优化。

    E-mail:mjhcr@163.com

  • 基金资助:
    * 国家自然科学基金(51305244)、山东省自然科学基金(ZR2013EEL015)和山东省高等学校科技计划(J16LB04)资助项目; 20160310收到初稿,20160627收到修改稿;

Multi-objective Genetic Algorithm for Solving Multi-objective Flow-shop Inverse Scheduling Problems

MOU Jianhui1, GUO Qianjian1, GAO Liang2, ZHANG Wei1, MOU Jiancai3   

  1. 1. School of Mechanical Engineering, Shandong University of Technology, Zibo 255000;
    2. State Key Lab of Digital Manufacturing Equipment and Technology, Huazhong University of Science & Technology, Wuhan 430074;
    3. Guangzhou Huali Science and Technology Vocational College, Guangzhou 511325
  • Online:2016-11-15 Published:2016-11-15

摘要:

将逆优化理论与方法引入车间调度领域,探讨近年来车间调度领域出现的一种新方法“逆调度”。研究多目标流水车间逆调度问题,建立考虑调度效率和调度稳定性的数学模型,综合考虑了加工参数改变量、系统改变量以及完工时间和等目标。提出一种基于混合的多目标遗传算法(Hybrid multi-objective genetic algorithm, HMGA)的求解方法,将多种策略进行混合以提高算法性能,主要包括快速非支配排序遗传算法(Non-dominated sorting genetic algorithm II, NSGAII)中的快速非支配排序方法、两种多样性保持策略、混合的精英保留策略,以及改进的局部搜索策略等。通过实例测试与方差分析(Analysis of variance, ANOVA),验证了该算法的有效性。

关键词: 多目标进化算法, 局部搜索算法, 逆调度, 车间调度, 定量分析, 动脉粥样硬化, 多元曲线分辨, 光谱成像, 光声光谱

Abstract:

A new method of scheduling fields (Inverse scheduling problem, ISP) is discussed under the theories and methods of inverse optimization. The definition of an inverse scheduling problem is that the exact values of parameters (e.g. processing times, due dates) are controllable and a feasible job sequence is given but not optimal and pre-specified job sequence(s) become optimal through adjusting processing parameters for a target. The model of multi-objective ISP which considers scheduling efficiency and system stability is build. The adjustment of processing parameters, the changing of system and the weighted completion time are considered in this model. A hybrid multi-objective genetic algorithm is proposed to solve this problem. In order to improve the performance of algorithm, the multiple strategies are mixed, including rapid non-dominated sorting method, two kinds of diversity strategy, hybrid elitism strategy and efficient local search strategy. Finally, public problem instances and ANOVA analysis are provided for the proposed algorithm. The results demonstrate the effectiveness of the algorithm.

Key words: inverse scheduling, local search method, multi-objective evolutionary algorithm, shop scheduling, Atherosclerosis, Multivariate Curve Resolution, Photoacoustic Spectroscopy, Quantitative Analysis, Spectroscopic imaging