基于增强邻域搜索策略的联合型生产调度问题算法研究

In traditional approaches, production scheduling has usually been treated as an isolated optimization problem in the sense that the interactions between the scheduling function and many other decision functions have mostly been neglected. This isolation means that the scheduling decision has to be made separately with the other potentially correlated decisions, and in this case, it is hardly possible to achieve globally optimal performance for the production system as a whole. To overcome the drawback, this project highlights the integration of production scheduling with the decision problems that are tightly coupled with it. The aim is to maximize the overall benefits of the production system by solving such integrated production scheduling problems (IPSPs). With regard to problem definition, we first extract three IPSPs from a vehicle manufacturing plant in Jiangling Motors Company, and then propose a classification scheme for IPSPs (i.e., decision process integration, time frame integration and supply chain integration). In order to ensure the integrity of research, we also provide theoretical scheduling models that are representative for each of the above-mentioned category of integration. With regard to algorithm design, we propose two types of enhanced neighborhood search strategies to effectively handle the huge and complex solution spaces of IPSPs. Neighborhood reduction rules (NRR) aim at excluding inferior solutions in the neighborhood so as to avoid unnecessary search attempts. Neighborhood expansion policies (NEP) aim at escaping from local optima so as to enlarge the search scope in the solution space. If the problem-specific information is properly utilized, the two types of strategies will hopefully be able to promote the general efficiency of meta-heuristics for solving IPSPs to a considerable extent.

传统研究方式将生产调度视为孤立的优化问题，忽略了调度决策与其它相关决策之间的联系，无法实现制造系统的全局优化。本项目对生产调度和与之紧密耦合的决策问题进行必要整合，通过求解这种联合型生产调度问题以实现系统整体利益的最大化。在问题构建方面，首先从江铃全顺厂的汽车制造过程中提炼出三种联合型生产调度问题，经过进一步抽象，给出联合型生产调度问题的分类框架（决策流程整合、时间周期整合、供应链整合）。为保证研究内容的系统性和完整性，对上述三类问题分别构造具有代表性的理论调度模型，以便深入研究。在优化算法方面，针对联合型生产调度问题解空间规模庞大且结构复杂的难点，提出两类增强邻域搜索策略。其中，邻域缩减规则的作用是排除邻域中的劣解，从而避免不必要的搜索尝试；邻域拓展方案的作用是逃离局部最优解，以扩大对解空间的探索范围。在有效利用问题信息的基础上，上述两类增强邻域搜索策略可显著提升智能优化算法的综合效率。

联合型生产调度问题广泛存在于各类制造过程中，本项目对两类问题进行了深入研究。第一类是生产调度与其它决策的联合优化，包括：（1）再制造过程生产调度与工艺规划的联合优化；（2）作业车间调度与机器加工速度设置的联合优化；（3）汽车制造系统中涂装车间调度与缓冲区分配的联合优化。第二类是传统调度目标与节能减排目标的联合优化，包括：（1）并行机加工环境下制造周期与用电成本（分时电价制）的联合优化；（2）流水车间环境下制造周期与碳排放量的联合优化；（3）染整生产中交货期指标与污水排放量的联合优化。在调度问题求解算法设计方面，突出“增强邻域搜索策略”在应对大规模解空间时的重要作用，代表性工作包括：（1）利用线性规划松弛模型的相关特征信息（例如关键决策变量的Reduced Cost等），针对作业车间调度问题提炼出一种“邻域缩减规则”，用于快速排除必然导致劣解的邻域操作；（2）借鉴大邻域构造思想，针对并行批处理机调度问题提出一种基于弹出链（Ejection Chain）的“邻域拓展方案”，将逃离局部最优解的邻域搜索过程转化为图上的最短路问题。本项目提出的优化算法均在大量随机生成实例以及部分实际生产数据上进行了性能测试，结果表明，基于问题特征的增强邻域搜索策略可显著提升算法的综合优化效率。