Abstract: For high-dimensional multi-objective Permutation Flow-shop Scheduling Problems (PFSP),an Optimal Foraging Algorithm (OFA) based on Cumulative Prospect Theory (CPT-OFA) was presented to minimize the makespan,maximum delay time,inventory cost and delay cost.In this algorithm,the grey relational analysis,the entropy theory and cumulative prospect theory were combined.The comprehensive-prospect-value model of the Pareto solution was established by setting reference points,defining the value function and the attribute weight.The weights of different objectives were evaluated with entropy theory.The prospect value was adopted to evaluate the quality of the Pareto solution and used as the fitness value to guide the evolution of the algorithm.Moreover,the opposite search mechanism was applied in OFA to avoid the entrapment into local optima and to enhance the search ability.The simulation experiments were carried out with PFSP benchmark instances and a practical PFSP to check the validity of the proposed algorithm.The experimental results demonstrated that CPT-OFA was superior to three relatively novel multi-objective optimization algorithms,and could obtain high-quality Pareto solution for the multi-objective PFSPs.

Key words: permutation flow-shop scheduling, cumulative prospect theory, optimal foraging algorithm, prospect value, multi-objective optimization

摘要： 针对高维多目标置换流水车间调度问题,以最大的完工时间、最大的延迟时间、库存成本和拖期成本为最小化优化目标,提出基于累积前景理论的最优觅食算法(CPT-OFA)求解该问题。算法将灰色关联分析法、信息熵理论和累积前景理论融合,通过设置参照点、确定价值函数和属性权重的方式来建立Pareto解的综合前景价值模型,利用信息熵理论计算各目标的评价权重。以价值的大小来判断Pareto解的好坏,将该值作为最优觅食算法的适应度值来引导算法进化。在标准最优觅食算法的基础上,引入逆向搜索机制来避免陷入局部最优解,增强种群的搜索能力,建立改进的最优觅食算法。通过仿真实例实验及生产案例,表明CPT-OFA算法的寻优性能明显优于3种较为新颖的多目标优化算法,且在多目标置换流水车间调度问题上能够获得较高质量的Pareto解。

关键词: 置换流水车间调度, 累积前景理论, 最优觅食算法, 前景价值, 多目标优化