Abstract: Aiming at the multi-page invoice order scheduling problem, a Multi-Objective Hybrid Genetic Algorithm (MOHGA) was presented by minimizing the maximum order completion time, average order completion time, maximum tardiness and average tardiness of all orders. A complete solution generation algorithm was proposed based on the problem characteristic, and a random weight vector was used at each iteration of selection to realize various search directions. To find more and better non-dominated solutions, a local search algorithm based on non-dominated ranking was proposed, and a global non-dominated solution archive was updated to keep the best approximate Pareto solutions. To validate the performance of the proposed algorithm, MOHGA was compared with two prominent multi-objective genetic algorithms based on a Pareto-compliant quality indicator-Hypervolumn. Numerical experiment indicated that a reasonable approximation of Pareto optimal set was obtained by MOHGA.

Key words: order scheduling, flexible, multi-objective, hybrid genetic algorithms, Pareto optimal

摘要： 针对多联票据订单调度问题进行研究，考虑最小化所有订单的最大完成时间、平均完成时间、最大延迟时间和平均延迟时间四个目标函数，提出一种多目标混合遗传算法。基于问题自身的特点提出完整解的构造算法，使用随机变动的权重实现多维多方向的搜索，设计了基于非主导性比较的局部搜索算法以寻找更多更好的非主导解，建立与更新全局非主导解集档案以保留最好的Pareto近似最优解。采用Pareto兼容的衡量参数，将该算法与两种对照算法进行了比较。大量算例的试验结果表明，该算法能够得到更接近于Pareto前沿且多样性分布更好的Pareto近似最优解集。

关键词: 订单调度, 柔性, 多目标, 混合遗传算法, Pareto最优