带特殊工艺约束的双目标并行多机调度问题研究

摘要/Abstract

摘要： 港口的拖轮调度过程是一类带特殊工艺约束的并行多机调度问题。采用基于进化策略的混合算法，设计了基于工件的编码方式，对次序杂交算子进行了扩展，设计了一种扩展“倒位”变异算子，并采用相邻不同基因多次交换的局部搜索方法。算法的设计自动满足了工艺约束，保证了种群的多样性。设计了最大完工时间和生产加工成本双目标评价函数，最后通过计算对混合算法进行了验证。

关键词: 港口拖轮调度, 并行多机调度, 特殊工艺约束, 进化策略

Abstract: The port tugboat operation scheduling is a kind of parallel machines scheduling problem with special process constraint. The hybrid algorithm based on the evolutionary strategy was employed to create coding method oriented to workpieces. In this hybrid algorithm, the inversion mutation operator was extended, an extended order crossover operator was presented, and the local search method of many times of exchanges among adjacent different genes was introduced. The hybrid algorithm automatically satisfied the process constraint and kept populations diversity. The bi-objectives evaluation function of maximum Make Span and production cost was presented. Finally, the hybrid algorithm was validated by computation.

Key words: port tugboat scheduling, parallel machines scheduling, special process constraint, evolutionary strategy

中图分类号:

TP18

刘志雄，王少梅. 带特殊工艺约束的双目标并行多机调度问题研究[J]. .

LIU Zhi-xiong, WANG Shao-mei. Research on bi-objectives parallel machines scheduling problem with special process constraint[J]. .

参考文献

［1］ LIU Min,WU Cheng,YANG Yingjie.New algorithm in parallel machine optimization scheduling problem［J］.Jounal of Tsinghua University(Sci&Tech),1999，39（5）：115-117(in Chinese).［刘民，吴澄，杨英杰. 并行机优化调度问题的新算法［J］.清华大学学报（自然科学版），1999，39（5）：115-117.］

[2] LIU Min,WU Cheng,YANG Yingjie.Genetic algorithm method based on combinatorial rules in identical parallel machine scheduling problem［J］.Acta Electronica Sinica,2000,28(5):52-54(in Chinese). ［刘民，吴澄，杨英杰.并行多机调度问题的一种基于组合规则的遗传算法［J］.电子学报，2000,28（5）:52-54.］

[3] SHI Weiguo,SONG Cunli,HUANG Ming.Study of multi-machine scheduling problem based on heuristic algorithm［J］.Journal of Dalian Railway Institute,2003，24（4）：55-57(in Chinese).［时维国，宋存利，黄明.基于启发式算法的并行多机调度问题研究［J］.大连铁道学院学报,2003，24（4）：55-57.］

[4] CHANG Junlin,ZHANG Chunkai,SHAO Huihe.A hybrid heuristic algorithm for a kind of identical parallel machines scheduling problem［J］.Journal of Computer Simulation,2004，21（3）：121-124(in Chinese).［常俊林，张春慨，邵惠鹤.求解一类并行多机调度问题的混合启发式算法［J］.计算机仿真,2004，21（3）：121-124.］

[5] SONG Cunli,SHI Weiguo, HUANG Ming.Multi-machine scheduling problem based on genetic algorithm［J］.Journal of Dalian Railway Institute,2004，25（2）：42-45(in Chinese).［宋存利，时维国，黄明.遗传算法在并行多机调度问题中的应用［J］.大连铁道学院学报，2004，25（2）：42-45.］

[6] YIN Wenjun,LIU Min,WU Cheng.A new genetic algorithm for parallel machine scheduling with process constraint［J］.Acta Electronica Sinica,2001,29(11)：1482-1485(in Chinese).［尹文君，刘民，吴澄.带工艺约束并行机调度问题的一种新的遗传算法［J］.电子学报,2001,29(11)：1482-1485.］

[7] LIU Min,WU Cheng,YIN Wenjun.Solving identical parallel machine production line scheduling problem with special procedure constraint genetic algorithm［J］.Journal of Automation,2001,27(3)：381-386(in Chinese).［刘民，吴澄，尹文君.带特殊工艺约束并行机器生产线调度问题的一种遗传算法［J］.自动化学报，2001,27(3)：381-386.］

[8] LIU Zhixiong,WANG Shaomei.The computer simulation study of port tugboat operation［J］.Journal of System Simulation,2004,16(1)：45-47(in Chinese).［刘志雄，王少梅.港口拖轮作业的计算机仿真研究［J］.系统仿真学报,2004,16(1)：45-47.］

[9] LI Huaizu.Direction of decision theory［M］.Beijing:China Machine Press，1993.53-54(in Chinese).［李怀祖.决策理论导引［M］.北京：机械工业出版社，1993.53-54.］

[1]	何杰光,陈新度,陈新,刘强. 求解资源受限项目调度的动态多样性进化策略[J]. 计算机集成制造系统, 2015, 21(第8期): 2089-2098.
[2]	杨波. 生长型设计中的复杂度设计策略[J]. , 2008, 14(10): 0-0.
[3]	刘志雄,，王少梅. 基于粒子群算法的并行多机调度问题研究[J]. , 2006, 12(02): 0-0.