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

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

项目编号： No.61473141

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 自动化技术、计算机技术

项目作者： 张瑞

作者单位： 南昌大学

项目金额： 76万元

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

中文关键词： 生产调度；智能优化算法；Job；Shop调度问题；邻域搜索

英文摘要： 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.

英文关键词： Production scheduling;Meta-heuristics;The Job Shop scheduling problem;Neighborhood search