基于量子智能算法的复杂车间调度问题研究

发布时间：2018-05-29 02:33

本文选题：零等待流水车间 + 量子进化算法　；参考：《昆明理工大学》2017年硕士论文

【摘要】：生产调度是制造系统的一个研究热点,也是理论研究中最为困难的问题之一。本文通过回顾国内外调度问题研究进展,对序不相关零等待流水车间调度问题和序相关零等待流水车间调度问题进行了详细研究。通过分析问题的特性,设计了针对问题的混合量子进化算法及有针对性的启发式方法,从而有效求解所研究的问题。仿真实验结果显示了算法的有效性能。本文的主要工作总结如下:(1)针对带序不相关设置时间和释放时间的零等待流水车间调度问题,提出了一种有效的混合量子进化算法进行求解,优化目标为最小化最大完工时间。该算法在全局搜索环节中采用自行设计的快速量子概率幅矩阵更新操作以提高算法的进化速度,同时加入4种邻域搜索机制以提高算法的局部搜索能力。仿真实验和算法比较验证了所提算法的有效性。(2)针对带序相关设置时间和释放时间的零等待流水车间调度问题,本文提出了一种高效的混合量子进化算法进行求解,优化目标为最小化总体延迟时间。首先,根据问题的结构性质,给出了解的快速评价方法,使得算法在相同时间内可搜索更多区域;然后,提出了改进的量子概率幅观测操作以增强算法全局搜索对解空间的搜索效率;最后,设计了前端省略快速邻域搜索机制、首次改进跳出策略和子邻域优质解即时更新策略,并将其融入基于Interchange子邻域的局部搜索中,提高了算法对全局搜索发现的优质区域进行细致搜索的能力。在性能测试环节对算法进行了详细的测试,包括参数优化、仅包括全局算法的对比测试、完整算法的对比测试等。通过和6种国际期刊中的有效算法进行仿真比较,验证了所提算法的高效性和鲁棒性。
[Abstract]:Production scheduling is a hot topic in manufacturing system, and it is also one of the most difficult problems in theoretical research. By reviewing the research progress of scheduling problem at home and abroad, this paper makes a detailed study on the scheduling problem of order uncorrelated zero wait flow shop and order-dependent zero wait flow shop scheduling problem. By analyzing the characteristics of the problem, a hybrid quantum evolutionary algorithm and a targeted heuristic method are designed to solve the problem effectively. Simulation results show the effectiveness of the algorithm. The main work of this paper is summarized as follows: (1) aiming at the zero-waiting flow shop scheduling problem with uncorrelated setup time and release time, an effective hybrid quantum evolutionary algorithm is proposed to solve the problem. The optimization goal is to minimize the maximum completion time. In order to improve the evolutionary speed of the algorithm, the algorithm adopts the self-designed fast quantum probability amplitude matrix update operation in the global search link, and adds four neighborhood search mechanisms to improve the local search ability of the algorithm. Simulation experiment and algorithm comparison verify the effectiveness of the proposed algorithm. (2) for the zero-waiting flow shop scheduling problem with sequential correlation setting time and releasing time, this paper proposes an efficient hybrid quantum evolutionary algorithm to solve the problem. The optimization goal is to minimize the total delay time. First of all, according to the structural properties of the problem, a fast evaluation method of solution is given, so that the algorithm can search more areas in the same time. An improved quantum probability amplitude observation operation is proposed to enhance the search efficiency of the global search algorithm for solution space. Finally, a front-end ellipsis fast neighborhood search mechanism is designed, which for the first time improves the jump out strategy and the immediate updating strategy of the sub-neighborhood high quality solution. The algorithm is integrated into the local search based on the Interchange sub-neighborhood, which improves the ability of the algorithm to search the high quality regions found in the global search. In the performance test, the algorithm is tested in detail, including parameter optimization, global algorithm contrast test, complete algorithm contrast test and so on. The effectiveness and robustness of the proposed algorithm are verified by simulation and comparison with the effective algorithms in 6 international journals.
【学位授予单位】：昆明理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18;TB497

【参考文献】