Study On Operation Scheduling Of Complex Product With Constraint Among Jobs

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.