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

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

Research on bi-objectives parallel machines scheduling problem with special process constraint

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 population's diversity.The bi-objectives evaluation function of maximum Make Span and production cost was presented.Finally,the hybrid algorithm was validated by computation.