提出了一种结合混合进化算法和知识的新型多目标车间调度方法,在有限的时间或迭代次数下可以得到更好的非支配Pareto解以服务于生产调度。由优化目标和属性归纳演绎法确定了知识挖掘的工件属性,通过优先级权重得到了规则初始种群。所提出的增减排序方法通过重新局部排序初始种群中工序的位置来克服优先级下工序不足或过饱和的问题。最后由一标准案例和非支配排序遗传算法-Ⅱ(NSGA-Ⅱ)混合模拟退火算法对所提调度方法进行了验证,得到的结果无论是优化目标值还是解集的分布在不同迭代次数和初始种群尺寸下都要优于传统随机进化方法。
A new multi-objective job shop scheduling method was proposed based on hybrid evolutionary algorithm and knowledge, the better non-dominant Pareto solutions might be obtained for production scheduling with limited time or iterations. The knowledge mining attributes were determined by the optimized objects and attribute-oriented induction and deduction method. Then, the rule-based initial population was acquired by the priority weight. The proposed addition-deletion sorting method overcame the problems of insufficient or oversaturated operations by re-assigning the positions in the initial population locally. Finally, a benchmark and non-dominated sorted genetic algorithm-Ⅱ (NSGA-Ⅱ) hybrid simulated annealing algorithm were used to verify the proposed scheduling method. The results obtained are superior to the traditional stochastic evolutionary method in terms of the optimized function values or the distribution of solution set under different iterations and initial population sizes.
[1]张洁,汪俊亮,吕佑龙,等.大数据驱动的智能制造[J].中国机械工程,2019,30(2):127-133.
ZHANG Jie, WANG Junliang, LYU Youlong, et al. Big Data on Intelligent Manufacturing[J]. China Mechanical Engineering, 2019, 30(2):127-133.
[2]林诗洁,董晨,陈明志,等.新型群智能优化算法综述[J]. 计算机工程与应用. 2018,54(12):1-9.
LIN Shijie, DONG Chen, CHEN Mingzhi, et al. Summary of New Group Intelligent Optimization Algorithm[J]. Computer Engineering and Applications, 2018, 54(12):1-9.
[3]HUANG Xiaobo, YANG Lixi. A Hybrid Genetic Algorithm for Multi-objective Flexible Job Shop Scheduling Problem Considering Transportation Time[J]. International Journal of Intelligent Computing and Cybernetics, 2019, 12(2):154-174.
[4]SOUIER M, DAHANE M, MALIKI F. An NSGA-Ⅱ-based Multiobjective Approach for Real-time Routing Selection in a Flexible Manufacturing System under Uncertainty and Reliability Constraints[J]. The International Journal of Advanced Manufacturing Technology, 2019, 100(9/12):2813-2829.
[5]ZHANG R, CHINONG R. Solving the Energy-efficient Job Shop Scheduling Problem:a Multi-objective Genetic Algorithm with Enhanced Local Search for Minimizing the Total Weighted Tardiness and Total Energy Consumption[J]. Journal of Cleaner Production, 2016, 112:3361-3375.
[6]SHEIKHALISHAHI M, ESKANDARI N, MAS-HAYEKHI A, et al. Multi-objective Open Shop Scheduling by Considering Human Error and Preventive Maintenance[J]. Applied Mathematical Modelling, 2019, 67:573-587.
[7]LU Chao, GAO Liang, PAN Quanke, et al. A Multi-objective Cellular Grey Wolf Optimizer for Hybrid Flowshop Scheduling Problem Considering Noise Pollution[J]. Applied Soft Computing, 2019, 75:728-749.
[8]QIN Hongbin, FAN Pengfei, TANG Hongtao, et al. An Effective Hybrid Discrete Grey Wolf Optimizer for the Casting Production Scheduling Problem with Multi-objective and Multi-constraint[J]. Computers & Industrial Engineering, 2019, 128:458-476.
[9]ZHOU Yong, YANG Jianjun, ZHENG Lianyu. Multi-agent Based Hyper-heuristics for Multi-objective Flexible Job Shop Scheduling:a Case Study in an Aero-engine Blade Manufacturing Plant[J]. IEEE Access, 2019, 7:21147-21176.
[10]FU Yaping, WANG Hongfeng, HUANG Min. Integrated Scheduling for a Distributed Manufacturing System:a Stochastic Multi-objective Model[J]. Enterprise Information Systems, 2019, 13(4):557-573.
[11]LI X N, OLAFSSON S. Discovering Dispatching Rules Using Data Mining[J]. Journal of Scheduling, 2005, 8(6):515-527.
[12]JUN S, LEE S, CHUN H. Learning Dispatching Rules Using Random Forest in Flexible Job Shop Scheduling Problems[J]. International Journal of Production Research, 2019, 57(10):3290-3310.
[13]KUMAR S, RAO C S P. Application of Ant Colony, Genetic Algorithm and Data Mining-based Techniques for Scheduling[J]. Robotics and Computer-Integrated Manufacturing, 2009, 25(6):901-908.
[14]NASIRI M M, SALESI S, RAHBARI A, et al. A Data Mining Approach for Population-based Methods to Solve the JSSP[J]. Soft Computing, 2019, 23(21):11107-11122.
[15]CAI Yandong. Attribute-oriented Induction in Relational Databases, Knowledge Discovery in Databases[D]. Burnaby:Simon Fraser University, 1989.
[16]KOONCE D A, TSAI S C. Using Data Mining to Find Patterns in Genetic Algorithm Solutions to a Job Shop Schedule[J]. Computers & Industrial Engineering, 2000, 38(3):361-374.
[17]LAWRENCE S. An Experimental Investigation of Heuristic Scheduling Techniques[D]. Pittsburgh:Carnegie-Mellon University, 1984.
[18]DEB K, PRATAP A, AGARWAL S, et al. A Fast and Elitist Multiobjective Genetic Algorithm:NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197.
[19]KIRKPATRICK S, GELATT C D, VECCHI M P. Optimization by Simulated Annealing[J]. Science, 1983, 4598(220):671-680.
[20]ARROYO J E C, LEUNG J Y T. An Effective Iterated Greedy Algorithm for Scheduling Unrelated Parallel Batch Machines with Non-identical Capacities and Unequal Ready Times[J]. Computers & Industrial Engineering, 2017, 105:84-100.
[21]ZITZLER E, THIELE L. Multiobjective Evolutionary Algorithms:a Comparative Case Study and the Strength Pareto Approach[J]. IEEE Transactions on Evolutionary Computation, 1999, 3(4):257-271.
[22]SCHOTT J R. Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization[D]. Boston:Massachusetts Institute of Technology, 1995.
[23]COBOS C, ERAZO C, LUNA J, et al. Multi-objective Memetic Algorithm Based on NSGA-Ⅱ and Simulated Annealing for Calibrating CORSIM Micro-simulation Models of Vehicular Traffic Flow[C]∥ Conference of the Spanish Association for Artificial Intelligence.Cham:Springer, 2016:468-476.