多目标模糊作业车间调度问题研究

• 论文 •

多目标模糊作业车间调度问题研究

雷德明，吴智铭

上海交通大学自动化研究所，上海 200030

收稿日期:2004-11-23 修回日期:2005-05-10 出版日期:2006-02-15 发布日期:2006-02-25
基金资助:
国家自然科学基金资助项目(70071017)

Research on Multi-objective fuzzy job shop scheduling

LEI De-ming, WU Zhi-ming

Inst. of Automation, Shanghai Jiaotong Univ., Shanghai 200030,China

Received:2004-11-23 Revised:2005-05-10 Online:2006-02-15 Published:2006-02-25
Supported by:
Project supported by the National Natural Science Foundation,China(No.70071017).

摘要/Abstract

摘要： 研究了具有模糊加工时间和模糊交货期的多目标作业车间调度问题，首先给出了基于模糊优先规则的编码新方式，染色体的每一位表示在GT算法迭代过程中，对应机器上发生的某次冲突，根据该基因位对应的优先规则消除。然后设计了基于个体密集距离的多目标进化算法，该算法利用密集距离进行外部档案维护和适应度赋值。最后将多目标进化算法应用于模糊作业车间调度问题，以最大化最小一致指标和最小化模糊最大完成时间，并和其他算法比较。计算结果验证了多目标进化算法在模糊调度方面良好的搜索性能。

关键词: 模糊作业车间调度, 密集距离, 优先规则, 多目标进化算法

Abstract: Multi-objective job shop scheduling with fuzzy processing time and fuzzy due date was studied. A new fuzzy priority rules-based representation method was firstly presented. Each gene in the chromosome represented that in the procedure of GT algorithm, the conflict occurred in the corresponding machine was resolved by the corresponding priority rule. Secondly, Multi-Objective Evolutionary Algorithm (CMOEA) based on individual crowding measurement was designed, and external archives maintenance and fitness assignment were conducted through this crowding measurement. Finally, CMOEA was applied to six fuzzy job shop scheduling to maximize the minimum agreement index and minimize the maximum fuzzy complete time and was compared with other algorithms. The computational results demonstrated the good performance (in fuzzy scheduling) of CMOEA.

Key words: fuzzy job shop scheduling, crowding measurement, priority rule, multi-objective evolutionary algorithm

中图分类号:

TP278

雷德明，吴智铭. 多目标模糊作业车间调度问题研究[J]. .

LEI De-ming, WU Zhi-ming. Research on Multi-objective fuzzy job shop scheduling[J]. .

参考文献

［1］ DAVIS L.Job shop scheduling with genetic algorithms［A］.Proceedings of the First International Conference on Genetic Algorithms［C］.Hillsdale:Lawrence Erlbaum Associates,1985.136-140.

[2] SRIDHAR J,RAJENDRAN C S.Scheduling in flow shop and cellular manufacturing with multiple objectives－a genetic algorithm approach［J］.Production Planning and Control,1996,7(4): 374-382.

[3] ISHIBUCHI H,MURATA T.A multi-objective genetic local search algorithm and its application to flow shop scheduling［J］.IEEE Transactions on Systems,Man and Cybernetics(Part C),1998,28(3): 392-403.

[4] PONNAMBALAM S G,RAMKUMAR V,JAWAHAR N.A multi-objective genetic algorithm for job shop scheduling［J］.Production Planning and Control,2001,12(8):764-774.

[5] SAKAWA M,KUBOTA R.Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy due date through genetic algorithm［J］.European Journal of Operational Research,2000,12(2): 393-407.

[6] ESQUIVEL S,FERRERO S,GALLARD R,et al.Enhanced evolutionary algorithm for single and multiobjective optimization in job shop scheduling problem［J］.Knowledge-Based System,2002,15(1):13-25.

[7] SAKAWA M,MORI T.An efficient genetic algorithm for job shop scheduling problems with fuzzy processing time and fuzzy due date［J］.Computers and Industrial Engineering,1999,36(2):325-341.

[8] GENG Zhaoqiang,ZOU Yiren.Study on job shop fuzzy scheduling based on genetic algorithm［J］.Computer Integrated Manufacturing Systems,2002,8(8):616－620(in Chinese).［耿兆强，邹益仁.基于遗传算法的作业车间模糊调度的研究［J］.计算机集成制造系统，2002,8(8):616-620.］

[9] KNOWLES J D,CORNE D W.Approximating the non-dominated front using the Pareto archive evolutionary strategy［J］.Evolutionary Computation,2000,8(2):149-172.

[10] ZITZLER E,LAUMANNS M,THIELE L.SPEA2:improving the strength Pareto evolutionary algorithm［R］.Lausanne,Switzerland:Swiss Federal Institute of Technology,2001.

[11] ZITZLER E,THIELE L.Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach［J］.IEEE Transaction on Evolutionary Computation,1999,3(4):257-271.

[12] DBE K,PRATAP A,AGARWAL S,et al.A fast and elitist multiobjective genetic algorithms: NSGA-Ⅱ［J］.IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.

[13] FIELDSEND J E,EVERSON R M,SINGH S,et al.Using unconstrained elicit archives for multiobjective optimization［J］.IEEE Transactions on Evolutionary Computation,2003,7(3):302-323.

[14] WANG Ling.Shop scheduling with genetic algorithm［M］.Beijing：Tsinghua University Press,2003(in Chinese).［王凌.车间调度及其遗传算法［M］.北京：清华大学出版社，2003.］

[15] ISHII H,TADA M,MASUDA T.Two scheduling problem with fuzzy due dates［J］.Fuzzy Sets and Systems,1992,46(2):339-347.

[1]	陈志远,伍章俊,童珊珊,刘晓. 基于改进双归档进化算法的多目标动态软件项目调度[J]. 计算机集成制造系统, 2021, 27(9): 2565-2574.
[2]	段黎明,涂玉林,李中明,罗雪清,任华桥. 基于密度的进化算法的机械产品选配方法[J]. 计算机集成制造系统, 2020, 26(第2): 312-319.
[3]	吴佳伟,宋华明,万良琪,黄甫,马东升,杨加猛. 微机电系统产品非正态多质量特性的稳健设计方法[J]. 计算机集成制造系统, 2020, 26(7): 1771-1781.
[4]	王小明,陈庆新,毛宁. 基于近似动态规划的模具项目调度[J]. 计算机集成制造系统, 2020, 26(6): 1691-1701.
[5]	彭乘风,陈庆新,毛宁,黎展滔. 具有无序工序生产特征的混合柔性流水车间在线调度[J]. 计算机集成制造系统, 2019, 25(第11): 2775-2787.
[6]	张影,翟丽丽,王京. 大数据背景下的云联盟数据资源服务组合模型[J]. 计算机集成制造系统, 2016, 22(第12期): 2920-2929.
[7]	杨涛,杨育,张东东. 考虑客户需求偏好的产品创新概念设计方案生成[J]. 计算机集成制造系统, 2015, 21(第4期): 875-884.
[8]	任水平,刘检华,何永熹,蒋科,郭崇颖. 机械产品多质量要求下的选择装配方法[J]. 计算机集成制造系统, 2014, 20(09): 2117-2126.
[9]	王小明，陈庆新，毛宁，刘建军. 随机环境下的模具项目交货期预测方法[J]. , 2012, 18(02): 0-0.
[10]	徐赐军，，李爱平，刘雪梅. 基于资源推拉技术的多项目调度算法[J]. , 2010, 16(06): 0-0.