柔性作业车间调度问题的高效混合算法研究

The flexible job shop scheduling problem is one of the typical NP-hard problems. Designing the quick and efficient algorithms to solve it is the research hot in the computer science and operations research fields.This project will apply two-step scheme to solve this problem, which depends on designing efficient hybrid algorithms. Firstly, to allot the operations to be processed by some certain machine appropriately. Secondly, to create an elastic system model for the problem which transfers the discrete combinatorial optimization problem to compute the minimal of a smooth supersurface. Thirdly, to create the new local structre and design new local search algorithms based on this new model, furthermore, to design globle search algorithms by simulating some social behives of humanbing. At last, to combine the new local structure, the two sort new algorithms and the new structure of the solutions to the Tabu search algorithm and the Genetic algorithm respectively, such as, adopt dynamic Tabu table technique and adopt the Orientation Neighborhood Searching Scheme based on the information of parents in the present generation, some more efficient hybrid algorithms could be designed to solve the problem.The results of this project could bring a new way for solving the flexible job shop scheduling problem, they could give some high efficient algorithms or technique supply for solving the scheduling problem in engineering projects.

柔性作业车间调度问题是一个典型的NP-难问题，设计求解该问题的高效算法是当今计算机科学和运筹学领域的研究热点。本项目拟采用分步求解方法，设计高效混合算法求解这个问题。其一将工序恰当地分配给确定的机器加工，其二建立该问题的弹性系统模型，该模型使得原来的离散型组合最优化问题自然地转化成计算光滑超曲面的最小值问题。其三构造基于这个新模型的新邻域结构、实现新的局部搜索算法，并模拟人类的某些社会生产行为设计全局搜索算法。其四将这两种算法、新的邻域结构和解的结构分别与Tabu搜索算法、遗传算法进行恰当融合，采用动态Tabu表长度技术、借助上一代群体中的相关信息，在本代中实施导向性搜索技术等，设计求解柔性作业车间调度问题的高效混合算法。本项目的研究成果将开辟求解柔性作业车间调度问题的新思路，并可为解决实际工程中的多种调度问题提供有效的算法与技术支持。

时空调度布局问题是典型的 NP-难问题，设计高效求解算法是当今计算机科学和运筹学领域的研究热点。本项目以陶瓷、钢铁锻造、半导体加工等实际生产为背景，研制单机调度问题的普适模型，pir=(pi + αit)ra，其作业加工时间依赖既有的排序序列且带有不同的系数、操作人员的熟练程度会影响操作时间，即使在智能设备广泛使用的环境里，设备需要调试、会出现疲劳，可见该模型具有广泛的应用。对于不带装配时间的单机调度问题求解TWT = ΣwiTi 和TWT2 = ΣwiT i 2的构造算法，这项研究得到了最好的计算结果，而且为其他邻域搜索算法、混合启发式算法中的领域构造、启发规则设计等提供了很有力的支撑。对于带装配时间且作业加工时间依赖既有的排序序列问题（1|sij|ΣwπjTj）求解，我们设计出六个演化算法，对120个国际通用算例的计算结果分析，其性能达到了2014年国际最高水平。对二维空间调度布局研究矩形Packing问题，课题研究中，我们设计出一类不完全枚举算法，分别计算了OR-Labority中的公共算例，其规模分布从10 到 2000。计算结果表明，我们的算法性能达到了世界先进水平。由此可以看出：内蕴性特征对算法效率的影响深刻、有效，对混合启发式算法等具有重要的借鉴意义。至于优化策略在信息安全领域中的应用，我们集中在搜索型分组保序加密、随机策略方面。该加密方案的优点是：① 保证加解密的相似性，在加密、解密以及中间过程中数据类型均为十进制数；② 明文空间和密文空间均为 ZN（109≤N≤1020）；③ 能抵抗敌手的N 次问询；④ 既适用于N 值为偶数又适用于N 值为奇数的情形。本项目的研究成果将开辟求解调度问题的新思路，并为解决实际工程中的多种调度问题提供有效的算法与技术支持。