【作者】 赵诗奎；

【导师】 顾新建； 方水良；

【作者基本信息】 浙江大学 ， 工业工程， 2013， 博士

【摘要】 随着加工技术、自动化技术的发展,柔性制造系统和数控加工中心等带有一定柔性的生产系统逐渐出现,具有柔性资源选择的柔性车间逐渐成为企业应对动态突变市场环境和机器故障等突发事件的有力工具。互联网、云计算、物联网等新一代信息技术的迅猛发展,与制造技术相融合,孕育了一种新的先进制造模式：云制造。云制造将巨大的社会制造资源连接在一起,提供各种制造服务,柔性资源调度技术是云制造中的一项关键技术。结合课题组的相关项目,论文围绕柔性资源调度问题展开研究。首先,重点对柔性车间环境的柔性作业车间调度问题(Flexible Job Shop Scheduling Problem,FJSP)进行深入研究,然后,对云制造环境下的柔性资源服务调度问题进行初步的探讨研究。第一章,介绍了课题的研究背景及意义。对调度问题和云制造进行了概述,综述了论文相关领域的国内外研究现状,并对现状进行了总结和分析,提出了论文的研究内容,给出了论文的章节结构。第二章,对FJSP问题研究的总体技术框架进行了研究。首先,对FJSP问题进行了描述,给出了其数学模型；然后,确定选用遗传算法对问题进行求解,研究了基于遗传算法求解FJSP问题的总体技术框架,确定了总体研究思路,为后续各章对FJSP问题的不断深入研究提供指导。第三章,研究了基于遗传算法优化的FJSP问题机器选择初始方法。提出一种基于短用时和设备均衡策略的遗传算法优化初始机器链方法,通过遗传算法计算产生定量优化的机器选择链群体；将上述机器选择链优化群体作为FJSP问题求解遗传算法的机器链初始群体；采用基准算例进行测试,验证了所提方法的有效性。第四章,研究了FJSP问题基于极限调度完工时间最小化的快捷高效机器选择初始方法。初始机器选择链时,宏观上采用全局选择和局部选择分别侧重于实现对最大机器负荷和最大工件加工时间指标的优化；微观上采用随机次序取代工件工艺顺序选择工序,在考虑可选机器负荷基础上,进一步比较加工时间选择机器,兼顾最大机器负荷和最大工件加工时间指标的优化；对基准算例的测试结果验证了所提方法的有效性。第五章,研究了FJSP问题求解遗传算法的工序链种群初始方法和基于工序编码邻域搜索机制。设计了采用主动调度、无延迟调度与启发式规则相结合的工序链群体初始方法；提出了与基于工序编码方式相结合的关键工序邻域搜索方法,避免了不可行解的产生以及染色体的检测修复等工作；提出一种基于调度甘特图的染色体标准化处理方法,对得到的标准化染色体进行邻域搜索提高了算法的搜索质量；对基准算例进行测试,验证了所提方法的有效性。第六章,研究了FJSP问题求解遗传算法的基于空闲时间的邻域搜索机制。设计了一种基于空闲时间的邻域结构,通过查找关键工序的机器空闲时间,确定关键工序的移动位置；给出了工序移动时保证可行解的工序移动条件及证明；分析了同一机器上相邻两工序间的空闲时间,给出了最大限度查找关键工序的机器空闲时间方法；对关键工序查找对应机器所存在的空闲时间,在保证可行解条件下,将关键工序移动到空闲时间位置进行邻域搜索；采用基准算例和企业实际案例进行测试,验证了所提方法的有效性。第七章,对云制造环境下的柔性资源服务调度进行了研究。构建了云制造环境下具有网状结构复杂产品的柔性资源服务调度优化数学模型；基于遗传算法对问题进行求解,设计了一种基于任务级别的分区编码方式；给出了多种针对分区编码可行的交叉与变异操作方式,研究了具有运输时间和任务顺序约束关系的解码方法；采用仿真算例进行测试,验证了所提方法的有效性。第八章,对全文工作和创新点进行了总结,并对进一步的研究进行了展望。更多还原

【Abstract】 With the development of processing technology and automation technology, production systems with a certain flexibilities including flexible manufacturing systems and CNC machining centers appeared. Flexible job shop with flexible resource selection gradually became a powerful tool to cope with dynamic market environment and sudden machine failures. Combining with manufacturing technologies, the improvements of new generation information technologies including internet, cloud computing, internet of things, and so on, gave birth to a new kind of advanced manufacturing modes:cloud manufacturing. The great social manufacturing resources were joined together to provide a variety of manufacturing services by cloud manufacturing. Flexible resource scheduling technology is a key technology in cloud manufacturing. In light of the related projects of our research group, it focused on the study of flexible resource scheduling problem in this dissertation. First, flexible job shop scheduling problem(FJSP) in the flexible workshop environment was studied in depth. Then, a preliminary study was completed on flexible resource service scheduling problem in cloud manufacturing.In Chapter Ⅰ, it introduced the research background and significance, and gave an overview of the shop scheduling problem and cloud manufacturing. The research status of the domestic and foreign were summarized, and the limitations were analyzed. Finanlly, the main research contents and structure were presented for the dissertation.In Chapter Ⅱ, the overall technical framework for FJSP were studied. Firstly, the FJSP problem was described, and its mathematical model was given. Then, genetic algorithm was selected for solving FJSP, and the overall technical framework based on genetic algorithm was studied. The overall research ideas were determined to provide guidance for subsequent chapters on FJSP.In Chapter Ⅲ, optimization initialization method based on genetic algorithm of machine selection chains was studied for FJSP. A novel machine chains initialization method based on short time and workloads balancing strategies using genetic algorithm was proposed. To optimize the quality of machine chains quantitatively based on genetic algorithm. The optimized machine chains were selected and combined together as the initial machine selection population for the FJSP solving genetic algorithm. Finally, the feasibility and validity of the proposed method was demonstrated with some typical scheduling examples.In Chapter Ⅳ, an effective machine initialization method based on the limit scheduling completion time minimization was proposed for FJSP. While initializing machine selection chains, global selection and local selection were adopted macroscopically to optimize maximum machine load and maximum job processing time respectively. Microscopically, to select the operation in random sequence instead of the job processing order, and further to compare the processing time based on considering the optional machine load for selecting machine. It took into account both of the maximum machine load and maximum job processing time optimization. Machine selection results of benchmarks were analyzed, and the effectiveness of proposed method was verified.In Chapter V, it studied the initialization method of operations sequence population and operation-based encoding neighborhood search mechanism of genetic algorithm for FJSP. Initialization method of operations sequence was designed by combining active scheduling, non-delay scheduling with heuristic rules. Neighborhood search moving of key operations was carried out based on operation-based encoding to avoid infeasible solutions and chromosome testing-repair work. A method for chromosome standardization based on the active decoded gantt chart was proposed. Neighborhood search was implemented on the standardized chromosome individuals. Finally, benchmarks were applied to test and verify the effectiveness of the proposed algorithm.In Chapter VI, a kind of neighborhood search genetic algorithm for FJSP based on idle time was proposed. Idle-time-based neighborhood structure was designed. Shift positions of critical operations were identified by finding the machine idle time for critical operations. To ensure the feasible solution, relative position shift conditions of the operation were given and proved. The idle time between two adjacent operations on the same machine was analyzed, and the method of maximum finding critical operation’s machine idle time was provided. To find machine idle time both in front and behind of the critical operation. On condition that guaranteeing feasible solution, neighborhood search was achieved by shifting the critical operation to the idle time. The idle-time-based neighborhood search was implanted in genetic algorithm. Finally, the proposed algorithm was tested on benchmark examples and enterprise actual case, and its effectiveness was verified.In Chapter VII, a preliminary study was completed on flexible resource service scheduling problem in cloud manufacturing. Flexible services scheduling optimization model for complex products with network structure in cloud manufacturing was built. Genetic algorithm was adopted to solve the problem. Task-rank-based zoning encoding method was designed. Several feasible crossover and mutation methods were provided for zoning coding. Decoding method with transportation time and task order constraints were studied. The feasibility and effectiveness of the algorithm were verified by simulation example. It summarized the dissertation and prospected the future research work in Chapter VIII.更多还原