【作者】 谢志强；

【导师】 谭光宇；

【作者基本信息】 哈尔滨理工大学 ， 机械制造及其自动化， 2009， 博士

【摘要】 加工和装配是产品制造的主要任务,加工和装配任务调度对产品的生产率和经济性都有很大的影响。加工和装配任务调度算法是研究虚拟制造、敏捷制造和精益制造中设计计算机集成制造系统的基础,不仅是当前调度理论中所研究的重要问题之一,而且在机械制造及自动化等先进制造技术领域发挥重要的作用。此项研究既可以促使调度问题的发展及其相关问题的研究,又可以使企业实现加工和装配调度计划的合理编排,从而减少人们的繁杂劳动,合理优化地组织生产,缩短生产周期,降低成本,提高生产效率。不仅符合当前国家大力发展装备制造业的国情,有重要的理论和社会意义,而且还会产生可观的经济效益。本文针对简单产品工序调度(本文简称产品调度)算法局限于纯加工或纯装配调度,无法考虑工件间存在约束关系的复杂产品制造过程中内在的加工和装配之间的并行关系,影响产品制造效率的问题,通过对工件间存在约束关系的复杂产品调度问题分析,对工件间存在约束关系的复杂单个(多个、动态)产品加工和装配过程综合调度优化、工件间存在约束关系的产品在有相同设备情况时的调度优化、快速判断影响加工与装配过程的可增加瓶颈设备和工件间存在约束关系时工序非紧密衔接的调度优化等4个问题进行了研究,并对提出的算法进行了分析和实例验证:1.对工件间存在约束关系的复杂单个产品,为了实现产品加工和装配过程综合调度,提出采取统一控制加工和装配设备、统一调度加工和装配工序的方法;为了减少工序的选择范围,提高调度效率,提出根据复杂单个产品树状工艺图(工艺树)动态地生成备选的预调度工序集合;通过综合考虑加工树纵(加工路径)横(加工工序层)结构关系,提出短用时、长路径和动态调整等调度策略进行工序调度优化,实现具有纵横双向调度优化的效果。对复杂多产品和多产品动态调度问题采取建立虚拟工艺树的方法向复杂单个产品问题简化,方便复杂多产品问题和复杂多产品动态问题的调度优化算法的实现。2.对工件间存在约束关系的复杂产品在有相同设备情况时的调度优化问题,通过分析产品工艺树结构,利用树状结构具有末端分枝繁衍的特点,对工艺树进行分段,根据末端工序的特点将工序分为相关工序和独立工序,并根据前沿贪心规则和最优适应规则对段内工序设计了调度的目标函数,再利用递归迭代完成整个复杂产品工艺树上工序的调度;对相同设备工序提出进行二次均衡分配的具有互补性的调度函数,使独立工序与相关工序或相关工序与相关工序并行处理,实现相同设备充分并行处理。通过构造成虚拟工艺树的方法,简化并解决相同设备情况时多产品或动态产品调度问题。3.对制约工件间存在约束关系的复杂产品生产效率的单一设备,通过对并行工序的研究,提出为每个工序标记它所在工艺图中的路线号,快速判断设备上并行工序的方法,以并行工序总时间最大设备为可增加的制约产品生产效率单一设备,即可增加的瓶颈设备。当并行工序总时间最大设备不唯一时,考虑紧前工序影响其后继工序开始加工的时间,提出将紧前工序数作为判断可增加瓶颈设备的第二因素。通过设计虚拟工艺树,解决了动态调度中确定可增加瓶颈设备的问题。4.对工件间存在约束关系的复杂产品工序非紧密衔接时的调度优化问题,为了表现工序间空隙的约束关系,提出了该类问题扩展工艺树结构;定义工序非紧密衔接的空隙为虚拟的延迟工序,并为虚拟的延迟工序设计虚拟设备,提出了工序非紧密衔接调度问题向一般调度问题转化的策略,将工序非紧密衔接的调度问题转化为一般工件间存在约束关系的复杂产品调度问题;通过对拟关键路径和最佳适应调度算法的分析,设计了一种通过优先调度延迟工序,对标准工序分批采用拟关键路径法和最佳适应调度法,同时考虑关键设备上标准工序尽量紧凑的非紧密衔接工序的动态调度优化算法。更多还原

【Abstract】 Processing and assembly are the key tasks of product manufacturing, processing and assembly scheduling have important effect for product productivity and economy. The scheduling algorithm about processing and assembly task is the basic of CIMS (computer integrated manufacturing systems) in the study of virtual manufacturing, agile manufacturing and lean manufacturing. It is one of the most important problems studied in the field of scheduling theory, and it plays an important role in the field of advanced manufacturing technology such as machinery manufacturing and automation. The study not only can accelerate the development of scheduling problem and the research of corresponding problems, but also make enterprise arrange product processing and assembly scheduling designedly, and achieve to reduce workload, optimize production, shorten total processing time, reduce cost and improve product efficiency. Therefor this study accords with the country’s national conditions of vigorously developing the equipment manufacturing industry, has the important theoretical and social significance, and it will also generate considerable economic benefits.The operation scheduling algorithms of simple product (namely simple product scheduling) are limited to solve pure processing or pure assembly scheduling problem, which does not consider the parallel relationship between processing and assembly during the manufacturing process of complex products with constraint among jobs, and affects the manufacturing efficiency of product. Aiming at the above mentioned problems and according to the analysis on complex product scheduling problem with constraint between jobs, four problems have been studied, which are processing and assembly integrated scheduling optimization problem of the complex single-product(multi-product and dynamic product) with constraint among jobs; processing and assembly integrated of complex product with identical machines and non-close-joining operations; and scheduling optimization problem of judging increasable bottleneck machine which effects processing and assembly integrated scheduling optimization problem. Analysis and examples show that the proposed algorithm is feasible and effective.1. Aiming at complex single-product with constraint between jobs, the method which controlling processing machines and assembly machines together and scheduling processing operations and assembly operations together is put forward, implementing the comprehensive scheduling of product processing and assembling. In order to reduce the selection scope of operations and improve the scheduling efficiency, the pre-scheduling set of operation is dynamically generated according to the processing operation chart (processing operation tree) of complex single-product. Short time strategy, long path strategy and dynamic adjustment strategy are proposed for scheduling optimization by considering the vertical (processing path) and horizontal (processing layer) relationship structure of the processing operation tree, implementing an effect of vertical and horizontal scheduling optimization. Aiming at complex multi-product and dynamic multi-product scheduling problem, a virtual processing operation tree is constructed to convert these problems into complex single-product problem, so that the scheduling optimization algorithm of complex multi-product and dynamic multi-product scheduling problem is conveniently implemented.2. Aiming at the scheduling optimization problem with identical machines of complex product with constrain between jobs, by analyzing the structure of product processing operation tree, operations are divided into independent operations and dependent operations according to the characteristic of cyclic nesting and multiply of the end branch. The scheduling objective functions are designed by forward greedy rule and optimum scheduling algorithm. And then use a recursive algorithm to implement the scheduling optimization of the whole complex product processing operation tree. The complementary scheduling functions are proposed to implement the second balanced assignment of operations on identical machines. Its goal is to independently process the independent and dependent operations or the dependent and dependent operations and to achieve the full parallel processing of identical machine. Simplify and solve the multi-product and dynamic product scheduling problem with identical machine by adopting the method of constructing the virtual processing operation tree. 3. Aiming at the single machine of restricting the production efficiency of complex product with constraint between jobs, the method of marking the route numbers for each operation in the processing operation tree and judging parallel operations on the machine is put forward. The machine which has the maximum total time of parallel operations is the increasable single machine of restricting the production efficiency of product, namely increasable bottleneck machine. When devices have the same total time of the parallel operations, a method which takes immediate predecessor into account is presented because immediate predecessor impacts the starting time of its successor operation. The problem of confirming increasable bottleneck machine in dynamic scheduling is solved by constructing virtual processing operation tree.4. Aiming at scheduling optimization problem with non-close-joining operations of complex product with constraint between jobs, the structure of extended processing operation tree is proposed in order to represent the constraint relations between gaps of operations. Defining virtual delay operation for the gap between non-close-joining operations, designing virtual machine for the virtual operation, and proposing the strategy of transferring non-close-joining scheduling problem to general scheduling problem with constrain between jobs. Then the non-close-joining scheduling problem is converted into the general scheduling problem of complex product with constraint between jobs. By analyzing allied critical path method and best fit scheduling method, a dynamic scheduling optimization algorithm of non-close-joining operation is designed. This algorithm is that delay operations are scheduled firstly, and then standard operations are scheduled by ACPM (allied critical path method) and BFSM (best fit scheduling method). The standard operations on the key machine are compacted as soon as possible at the same time.更多还原