基于Pareto优化的离散自由搜索算法求解多目标柔性作业车间调度问题  

Discrete Free Search Based on Pareto-optimality for Multi-objective Flexible Job-shop Scheduling Problem

作　　者：彭建刚[1] 刘明周[1] 张玺[1] 张铭鑫[1] 葛茂根[1] 

机构地区：[1]合肥工业大学,合肥230009

出　　处：《中国机械工程》2015年第5期620-626,共7页China Mechanical Engineering

基　　金：国家自然科学基金资助项目(71071046)

摘　　要：针对多目标柔性作业车间调度问题搜索空间的离散性和求解算法的收敛性,提出一种基于Pareto优化的离散自由搜索算法来求解多目标柔性作业车间调度问题。在建立基于Markov链数学模型的基础上,证明了算法以概率1收敛;引入首达最优解期望时间来分析算法收敛速度,并分析了算法时间复杂度。采用基于工序排序和机器分配的个体表达方式,在多目标柔性作业车间离散域,利用自由搜索算法在邻域小步幅精确搜索和在全局空间大步幅勘测进行寻优;通过自由搜索算法自适应赋予个体各异辨别能力和Pareto优化概念来比较个体优劣性,不仅保留优化个体,而且使个体寻优方向沿多目标柔性作业车间调度问题Pareto前沿逼近。通过对搜索过程中产生的伪调度方案进行可行性判定,以确保调度方案可行。采用10×10FJSP和8×8FJSP问题的实例进行寻优测试,验证了所提算法的可行性和有效性。A discrete free search algorithm based on Pareto-optimality was proposed for solving multi-objective flexible job-shop scheduling problem.The convergence with probability one of the proposed algorithm was demonstrated based on Markov chain and the convergence rate was analyzed based on expected first hitting time.The computational complexity of algorithm was also analyzed.Individuals of algorithm were represented based on job operation and machine assignment,and updated either with small precise steps for local search or with large steps for global exploration in discrete domain.The individuals were compared through adaptive sensibility and Pareto-optimality concept.The proposed algorithm was to retain the optimization individuals,and to guide individuals taking exploration walks towards Pareto-optimality front of multi-objective flexible job-shop scheduling problem.The feasibility and effectiveness of the proposed algorithm were verified by both 10×10FJSP and8×8FJSP instance.

关 键 词：多目标柔性作业车间调度问题 自由搜索 MARKOV链 PARETO优化 

分 类 号：TH186[机械工程—机械制造及自动化]