WO2025007696A1

WO2025007696A1 - Shop scheduling method and system for large-sized complex product, and device and medium

Info

Publication number: WO2025007696A1
Application number: PCT/CN2024/097550
Authority: WO
Inventors: 隋少春; 赵淑军; 吴悠; 唐健钧; 石芹芹; 李尚强; 金筑云; 刘雪豪; 王丹阳
Original assignee: Chengdu Aircraft Industrial Group Co Ltd
Current assignee: Chengdu Aircraft Industrial Group Co Ltd
Priority date: 2023-07-04
Filing date: 2024-06-05
Publication date: 2025-01-09
Anticipated expiration: 2026-01-04
Also published as: CN116540659A; CN116540659B

Abstract

The present invention relates to the technical field of job shop scheduling, and particularly relates to a shop scheduling method and system for a large-sized complex product, and a device and a medium. The method comprises: firstly, determining a scheduling decision problem of assemble, adjusting and debugging shops of a large-sized complex product, and a precondition hypothesis, so as to obtain a maximum workpiece completion time; then, taking the maximum workpiece completion time of the large-sized complex product being as small as possible as an optimization objective, and establishing an assemble, adjusting and debugging shop scheduling optimization model of the large-sized complex product; and finally, using a multi-objective genetic algorithm to perform optimization solving, so as to obtain a target scheduling decision and a target completion time of the assemble, adjusting and debugging shops of the large-sized complex product. Therefore, an assemble, adjusting and debugging process highly matching an actual production process is ensured, and the precision and convergence speed of model solving are improved.

Description

A large-scale complex product workshop scheduling method, system, equipment and medium

Technical Field

本发明涉及作业车间调度技术领域，具体地说，涉及一种大型复杂产品车间调度方法、系统、设备及介质。The present invention relates to the technical field of job shop scheduling, and in particular to a method, system, equipment and medium for scheduling a large-scale complex product shop.

Background Art

复杂产品生产过程中，部件连接方式以装配为主，并且装配完成后的系统调试作为必不可少的加工环节，工时占比高，可见提升装调车间组织运行能力，是保证产品质量与生产效率、提高企业整体经济效益的关键，因此对大型复杂产品制造企业具有重要意义。In the production process of complex products, the main way to connect components is assembly, and system debugging after assembly is an indispensable processing link, which accounts for a high proportion of working hours. It can be seen that improving the organizational and operational capabilities of the assembly and adjustment workshop is the key to ensuring product quality and production efficiency and improving the overall economic benefits of the enterprise. Therefore, it is of great significance to large-scale complex product manufacturing companies.

目前鲜有学者对于同时考虑装配调试设备工具资源和装配调试工人的多资源约束车间问题进行研究，但是所研究的调度问题只适用于简单流水车间，导致建立的数学模型与实际模型之间差别很大，对具有装配工艺结构的大型复杂产品的调度，若仍采用传统的调度算法来处理，必定会分裂制造过程中工艺树内在的可并行关系，致使生产周期延长。At present, few scholars have studied the multi-resource constrained workshop problem that takes into account both the assembly and debugging equipment tool resources and the assembly and debugging workers. However, the scheduling problem studied is only applicable to simple flow workshops, resulting in a large difference between the established mathematical model and the actual model. For the scheduling of large and complex products with assembly process structures, if traditional scheduling algorithms are still used, the inherent parallel relationship of the process tree in the manufacturing process will inevitably be split, resulting in an extension of the production cycle.

在面向大型复杂产品的装配生产中，由于结构件体积庞大，因此每一道工序都需要占用相应的设备工具，同时在装配、系统调试等过程中，需要调度相应技能的工人围绕着操作对象或者设备在对应的工位进行工序处理。同时车间班组工人数量有限，如果不考虑人员资源约束，势必会导致产品在生产时，调度方案与实际生产能力不对应而导致方案不可行。由于问题的复杂度较高，目前鲜有其研究成果的报道，因此，针对大型复杂产品的装配调试车间调度问题的研究存在较大的意义。In the assembly production of large and complex products, due to the large size of the structural parts, each process requires the use of corresponding equipment and tools. At the same time, during the assembly and system debugging process, workers with corresponding skills need to be dispatched to perform process processing around the operation object or equipment at the corresponding workstation. At the same time, the number of workers in the workshop team is limited. If the personnel resource constraints are not considered, it will inevitably lead to the scheduling plan not corresponding to the actual production capacity during the production of the product, making the plan infeasible. Due to the high complexity of the problem, there are few reports on its research results. Therefore, the research on the scheduling problem of the assembly and debugging workshop of large and complex products is of great significance.

发明内容Summary of the invention

本发明针对现有大型复杂工件调度方法中存在求解精度和收敛速度不足的问题，提出一种大型复杂产品车间调度方法、系统、设备及介质，该方法首先确定大型复杂产品装配与调试车间调度决策问题和前提假设，得到工件最长完工时间，然后将最小化大型复杂产品工件最长完工时间作为优化目标，建立大型复杂产品装配与调试车间调度优化模型；最后采用多目标遗传算法优化求解，得到大型复杂产品装配与调试车间目标调度决策和目标完工时间，保证了装配调试过程与实际生产过程的高度匹配，提高了模型求解的精度和收敛速度。In view of the problems of insufficient solution accuracy and convergence speed in existing large-scale complex workpiece scheduling methods, the present invention proposes a large-scale complex product workshop scheduling method, system, equipment and medium. The method first determines the scheduling decision problem and premise assumptions of the large-scale complex product assembly and debugging workshop to obtain the longest completion time of the workpiece, and then takes minimizing the longest completion time of the large-scale complex product workpiece as the optimization goal, and establishes a large-scale complex product assembly and debugging workshop scheduling optimization model; finally, a multi-objective genetic algorithm is used to optimize and solve, and the target scheduling decision and target completion time of the large-scale complex product assembly and debugging workshop are obtained, which ensures a high degree of matching between the assembly and debugging process and the actual production process, and improves the accuracy and convergence speed of the model solution.

本发明具体实现内容如下：The specific implementation contents of the present invention are as follows:

一种大型复杂产品车间调度方法，首先确定大型复杂产品装配与调试车间调度决策问题和前提假设，得到工件最长完工时间，然后将最小化大型复杂产品工件最长完工时间作为优化目标，建立大型复杂产品装配与调试车间调度优化模型；最后采用多目标遗传算法优化求解所述大型复杂产品装配与调试车间调度优化模型，得到大型复杂产品装配与调试车间目标调度决策和目标完工时间。A scheduling method for large-scale complex product workshops first determines the scheduling decision problem and premise assumptions of large-scale complex product assembly and debugging workshops, obtains the longest completion time of workpieces, then takes minimizing the longest completion time of large-scale complex product workpieces as the optimization goal, and establishes a scheduling optimization model for large-scale complex product assembly and debugging workshops; finally, a multi-objective genetic algorithm is used The scheduling optimization model of the large-scale complex product assembly and debugging workshop is optimized and solved to obtain the target scheduling decision and target completion time of the large-scale complex product assembly and debugging workshop.

为了更好地实现本发明，进一步地，所述大型复杂产品车间调度方法具体包括以下步骤：In order to better implement the present invention, further, the large-scale complex product workshop scheduling method specifically includes the following steps:

步骤1：确定大型复杂产品装配与调试车间调度决策问题和前提假设，得到工件最长完工时间；Step 1: Determine the scheduling decision problem and premise assumptions of the large-scale complex product assembly and debugging workshop, and obtain the longest completion time of the workpiece;

步骤2：根据所述工件最长完工时间，以最小化工件最长完工时间和最小化任务总拖期量为优化目标，设置大型复杂产品工序之间的优先级约束条件、装配调试设备及工具资源约束条件和装配调试工人资源约束条件，建立大型复杂产品装配与调试车间调度优化模型；Step 2: According to the longest completion time of the workpiece, with minimizing the longest completion time of the workpiece and minimizing the total delay of the task as the optimization goal, set the priority constraints between the processes of large and complex products, the assembly and debugging equipment and tool resource constraints, and the assembly and debugging worker resource constraints, and establish a large and complex product assembly and debugging workshop scheduling optimization model;

步骤3：采用启发式规则改进多目标遗传算法的初始化操作，得到改进的多目标遗传算法；Step 3: Using heuristic rules to improve the initialization operation of the multi-objective genetic algorithm to obtain an improved multi-objective genetic algorithm;

步骤4：采用改进的多目标遗传算法优化求解所述大型复杂产品装配与调试车间调度优化模型，得到大型复杂产品装配与调试车间目标调度决策和目标完工时间。Step 4: Use an improved multi-objective genetic algorithm to optimize and solve the scheduling optimization model of the large-scale complex product assembly and debugging workshop to obtain the target scheduling decision and target completion time of the large-scale complex product assembly and debugging workshop.

为了更好地实现本发明，进一步地，所述步骤1具体包括以下步骤：In order to better implement the present invention, further, the step 1 specifically includes the following steps:

步骤11：确定大型复杂产品装配与调试车间调度决策问题和前提假设；Step 11: Determine the scheduling decision problems and assumptions of large and complex product assembly and commissioning workshops;

步骤12：在大型复杂产品的工序满足优先级约束情况下，确定工件的先后装配顺序，在调度过程中选择当前工序的工具或设备，并配置对应数量的工人，得到工件最长完工时间。Step 12: When the processes of large and complex products meet the priority constraints, determine the assembly order of the workpieces, select the tools or equipment for the current process during the scheduling process, and allocate the corresponding number of workers to obtain the longest completion time of the workpiece.

为了更好地实现本发明，进一步地，所述步骤2具体包括以下步骤：In order to better implement the present invention, further, the step 2 specifically includes the following steps:

步骤21：根据所述工件最长完工时间，得到工件最长完工时间目标函数；Step 21: Obtaining a maximum completion time objective function of the workpiece according to the maximum completion time of the workpiece;

步骤22：根据所述工件最长完工时间、工件的交付期、工件的拖期系数，得到任务总拖期量目标函数；Step 22: Obtaining a total task delay objective function according to the longest completion time of the workpiece, the delivery period of the workpiece, and the delay coefficient of the workpiece;

步骤23：根据所述工件最长完工时间目标函数和所述任务总拖期量目标函数，设置大型复杂产品工序之间的优先级约束条件、装配调试设备及工具资源约束条件和装配调试工人资源约束条件，建立大型复杂产品装配与调试车间调度优化模型。Step 23: According to the objective function of the longest completion time of the workpiece and the objective function of the total delay of the task, set the priority constraints between the processes of large and complex products, the assembly and debugging equipment and tool resource constraints, and the assembly and debugging worker resource constraints, and establish a scheduling optimization model for the assembly and debugging workshop of large and complex products.

为了更好地实现本发明，进一步地，所述步骤3的具体操作为：采用多种初始化方式改进多目标遗传算法的初始化操作，所述多种初始化方式包括随机初始化方式、按照交付期规则优先级初始化方式和剩余加工时间优先级初始化方式。In order to better implement the present invention, further, the specific operation of step 3 is: adopt multiple initialization methods to improve the initialization operation of the multi-objective genetic algorithm, and the multiple initialization methods include random initialization method, initialization method according to delivery period rule priority and initialization method according to remaining processing time priority.

为了更好地实现本发明，进一步地，所述步骤4具体包括以下操作：In order to better implement the present invention, further, the step 4 specifically includes the following operations:

步骤41：建立工件工艺结构树；Step 41: Establish a workpiece process structure tree;

步骤42：展开所述工件工艺结构树，得到工件工序工艺结构树信息； Step 42: Expand the workpiece process structure tree to obtain workpiece process structure tree information;

步骤43：根据所述工件工序工艺结构树信息进行染色体编码，得到满足装配调试工艺中工件之间存在的前后加工顺序的约束条件的合法基因结构；Step 43: Perform chromosome encoding according to the workpiece process structure tree information to obtain a legal gene structure that satisfies the constraint condition of the front and back processing sequence between the workpieces in the assembly and debugging process;

步骤44：根据所述合法基因结构进行解码，得到工件大型复杂产品装配与调试车间目标调度决策和目标完工时间。Step 44: Decode according to the legal gene structure to obtain the target scheduling decision and target completion time of the large-scale complex product assembly and debugging workshop of the workpiece.

为了更好地实现本发明，进一步地，所述步骤44具体包括以下步骤：In order to better implement the present invention, further, the step 44 specifically includes the following steps:

步骤441：获取调度任务，根据所述合法基因结构，遍历染色体排序中的工件；Step 441: Obtain a scheduling task, and traverse the artifacts in the chromosome sorting according to the legal gene structure;

步骤442：根据所述工件的编号，检索所述工件类型；Step 442: Retrieve the artifact type according to the artifact number;

步骤443：读取所述工件的工序，并根据所述工序获取所述工序的平台信息；Step 443: reading the process of the workpiece, and acquiring platform information of the process according to the process;

步骤444：根据所述工件类型选择对应的工具，判断所述工具的剩余使用时间，根据所述剩余使用时间，判断工人数量是否满足设定条件，并计算当前完工时间；Step 444: selecting a corresponding tool according to the workpiece type, determining the remaining use time of the tool, determining whether the number of workers meets the set conditions according to the remaining use time, and calculating the current completion time;

步骤445：判断所有工序是否遍历完成，若工序没有遍历完成，则返回步骤443；若所有工序遍历完成，则判断所有工件是否遍历完成，若工件没有遍历完成，则返回步骤441，若所有工件遍历完成，则将当前完工时间作为目标完工时间，输出大型复杂产品装配与调试车间目标调度决策。Step 445: Determine whether all processes have been traversed. If not, return to step 443. If all processes have been traversed, determine whether all workpieces have been traversed. If not, return to step 441. If all workpieces have been traversed, use the current completion time as the target completion time and output the target scheduling decision for large and complex product assembly and debugging workshops.

基于上述提出的大型复杂产品车间调度方法，为了更好地实现本发明，进一步地，提出一种大型复杂产品车间调度系统，包括初始化单元、模型建立单元、计算单元；Based on the above-mentioned large-scale complex product workshop scheduling method, in order to better realize the present invention, further, a large-scale complex product workshop scheduling system is proposed, including an initialization unit, a model building unit, and a calculation unit;

所述初始化单元，用于确定大型复杂产品装配与调试车间调度决策问题和前提假设，得到工件最长完工时间；The initialization unit is used to determine the scheduling decision problem and premise assumptions of the large-scale complex product assembly and debugging workshop to obtain the longest completion time of the workpiece;

所述模型建立单元，用于将最小化大型复杂产品工件最长完工时间作为优化目标，建立大型复杂产品装配与调试车间调度优化模型；The model building unit is used to establish a scheduling optimization model for large-scale complex product assembly and debugging workshops by taking minimization of the longest completion time of large-scale complex product workpieces as an optimization goal;

所述计算单元，用于采用多目标遗传算法优化求解所述大型复杂产品装配与调试车间调度优化模型，得到大型复杂产品装配与调试车间目标调度决策和目标完工时间。The computing unit is used to optimize and solve the scheduling optimization model of the large-scale complex product assembly and debugging workshop by using a multi-objective genetic algorithm to obtain the target scheduling decision and target completion time of the large-scale complex product assembly and debugging workshop.

基于上述提出的大型复杂产品车间调度方法，为了更好地实现本发明，进一步地，提出一种电子设备，包括存储器和处理器；所述存储器上存储有计算机程序；当所述计算机程序在所述处理器上执行时，实现上述的大型复杂产品车间调度方法。Based on the above-mentioned large-scale complex product workshop scheduling method, in order to better realize the present invention, further, an electronic device is proposed, including a memory and a processor; a computer program is stored on the memory; when the computer program is executed on the processor, the above-mentioned large-scale complex product workshop scheduling method is implemented.

基于上述提出的大型复杂产品车间调度方法，为了更好地实现本发明，进一步地，提出一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机指令；当所述计算机指令在上述的电子设备上执行时，实现上述的大型复杂产品车间调度方法。Based on the above-mentioned large-scale complex product workshop scheduling method, in order to better realize the present invention, further, a computer-readable storage medium is proposed, on which computer instructions are stored; when the computer instructions are executed on the above-mentioned electronic device, the above-mentioned large-scale complex product workshop scheduling method is implemented.

本发明具有以下有益效果：The present invention has the following beneficial effects:

(1)本发明采用多种初始化方式组合改进多目标遗传算法的初始化操作，得到的多目标遗传算法的求解精度更高，能在有限的搜索时间内更快更稳定地收敛至近似最优解，加快了模型收敛的速度。(1) The present invention adopts a combination of multiple initialization methods to improve the initialization operation of the multi-objective genetic algorithm, and the obtained multi-objective genetic algorithm has higher solution accuracy and can converge to the approximate optimal solution faster and more stably within a limited search time. Faster model convergence speed.

(2)本发明综合考虑装配工人、调试工人的资源上限，通过多目标遗传算法对模型进行求解得到目标最长完工时间和订单总拖期量，缩短了生产周期。(2) The present invention comprehensively considers the resource upper limit of assembly workers and debugging workers, and solves the model through a multi-objective genetic algorithm to obtain the target maximum completion time and the total order delay, thereby shortening the production cycle.

BRIEF DESCRIPTION OF THE DRAWINGS

图1为本发明实施例提供的多目标遗传算法流程示意图。FIG1 is a schematic diagram of a multi-objective genetic algorithm flow chart provided by an embodiment of the present invention.

图2为本发明实施例提供的工艺结构树示意图。FIG. 2 is a schematic diagram of a process structure tree provided in an embodiment of the present invention.

图3为本发明实施例提供的结构工艺树工序展开结构示意图。FIG. 3 is a schematic diagram of a process expansion structure of a structural process tree provided by an embodiment of the present invention.

图4为本发明实施例提供的编码示例结构示意框图。FIG4 is a schematic block diagram of an example encoding structure provided by an embodiment of the present invention.

图5为本发明实施例提供的解码流程示意图。FIG. 5 is a schematic diagram of a decoding process provided by an embodiment of the present invention.

图6为本发明实施例提供的零部件对应工序的工具/设备选择编码结构示意框图。FIG. 6 is a schematic block diagram of a tool/equipment selection coding structure for a component corresponding to a process provided by an embodiment of the present invention.

图7为本发明实施例提供的生产任务产品工艺树信息结构示意图。FIG. 7 is a schematic diagram of a production task product process tree information structure according to an embodiment of the present invention.

图8为本发明实施例提供的生产任务产品零部件代号结构示意图。FIG8 is a schematic diagram of the code structure of parts of a production task product provided in an embodiment of the present invention.

图9为本发明实施例提供的不同算法求解装配调试调度实例迭代曲线示意图。FIG. 9 is a schematic diagram of iteration curves of different algorithms for solving assembly debugging scheduling examples provided by an embodiment of the present invention.

图10为本发明实施例提供的大型复杂产品车间调度方法流程示意框图。FIG. 10 is a schematic block diagram of the process of a large-scale complex product workshop scheduling method provided by an embodiment of the present invention.

DETAILED DESCRIPTION

为了更清楚地说明本发明实施例的技术方案，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，应当理解，所描述的实施例仅仅是本发明的一部分实施例，而不是全部的实施例，因此不应被看作是对保护范围的限定。基于本发明中的实施例，本领域普通技术工作人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。In order to more clearly illustrate the technical solutions of the embodiments of the present invention, the technical solutions in the embodiments of the present invention will be clearly and completely described below in conjunction with the drawings in the embodiments of the present invention. It should be understood that the described embodiments are only part of the embodiments of the present invention, not all of the embodiments, and therefore should not be regarded as limiting the scope of protection. Based on the embodiments of the present invention, all other embodiments obtained by ordinary technical personnel in this field without making creative work are within the scope of protection of the present invention.

在本发明的描述中，需要说明的是，除非另有明确的规定和限定，术语“设置”、“相连”、“连接”应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或一体地连接；可以是机械连接，也可以是电连接；也可以是直接相连，也可以是通过中间媒介间接相连，可以是两个元件内部的连通。对于本领域的普通技术人员而言，可以具体情况理解上述术语在本发明中的具体含义。In the description of the present invention, it should be noted that, unless otherwise clearly specified and limited, the terms "disposed", "connected", and "connected" should be understood in a broad sense, for example, it can be a fixed connection, a detachable connection, or an integral connection; it can be a mechanical connection or an electrical connection; it can be a direct connection, or it can be an indirect connection through an intermediate medium, or it can be the internal communication of two elements. For ordinary technicians in this field, the specific meanings of the above terms in the present invention can be understood according to specific circumstances.

本发明专利涉及装配与调试车间的优化技术领域，特别是需要同时考虑装配调试设备工具资源和工人资源约束的大型复杂产品装配调试调度优化方法。既包括对车间调度的数学建模，也包括多目标遗传算法求解该数学模型的具体过程。The invention relates to the field of optimization technology for assembly and debugging workshops, especially the optimization method for assembly and debugging scheduling of large and complex products that needs to consider both assembly and debugging equipment and tool resources and worker resource constraints. It includes both mathematical modeling of workshop scheduling and the specific process of solving the mathematical model using a multi-objective genetic algorithm.

本发明实施例中涉及的专业名词的英文全称如下：The English full names of the professional terms involved in the embodiments of the present invention are as follows:

多目标遗传算法：Multi-Objective Genetic Algorithm，MOGA。Multi-Objective Genetic Algorithm: Multi-Objective Genetic Algorithm, MOGA.

装配车间调度：Assemble and Adjusting Shop Scheduling Problem，AASSP。 Assembly shop scheduling: Assemble and Adjusting Shop Scheduling Problem, AASSP.

实施例1：Embodiment 1:

本实施例提出一种大型复杂产品车间调度方法，如图10所示，首先确定大型复杂产品装配与调试车间调度决策问题和前提假设，得到工件最长完工时间，然后将最小化大型复杂产品工件最长完工时间作为优化目标，建立大型复杂产品装配与调试车间调度优化模型；最后采用多目标遗传算法优化求解所述大型复杂产品装配与调试车间调度优化模型，得到大型复杂产品装配与调试车间目标调度决策和目标完工时间。This embodiment proposes a scheduling method for a large and complex product workshop, as shown in Figure 10. First, the scheduling decision problem and premise assumptions of the large and complex product assembly and debugging workshop are determined to obtain the longest completion time of the workpiece. Then, minimizing the longest completion time of the large and complex product workpiece is used as the optimization goal to establish a scheduling optimization model for the large and complex product assembly and debugging workshop. Finally, a multi-objective genetic algorithm is used to optimize and solve the scheduling optimization model for the large and complex product assembly and debugging workshop to obtain the target scheduling decision and target completion time of the large and complex product assembly and debugging workshop.

所述大型复杂产品车间调度方法具体包括以下步骤。The large-scale complex product workshop scheduling method specifically includes the following steps.

步骤1：确定大型复杂产品装配与调试车间调度决策问题和前提假设，得到工件最长完工时间。Step 1: Determine the scheduling decision problem and premise assumptions of the large-scale complex product assembly and debugging workshop, and obtain the longest completion time of the workpiece.

所述步骤1具体包括以下步骤：The step 1 specifically comprises the following steps:

步骤2：根据所述工件最长完工时间，以最小化工件最长完工时间和最小化任务总拖期量为优化目标，设置大型复杂产品工序之间的优先级约束条件、装配调试设备及工具资源约束条件和装配调试工人资源约束条件，建立大型复杂产品装配与调试车间调度优化模型。Step 2: According to the longest completion time of the workpiece, with the optimization goal of minimizing the longest completion time of the workpiece and minimizing the total delay of the task, set the priority constraints between the processes of large and complex products, the assembly and debugging equipment and tool resource constraints, and the assembly and debugging worker resource constraints, and establish a scheduling optimization model for the assembly and debugging workshop of large and complex products.

所述步骤2具体包括以下步骤：The step 2 specifically includes the following steps:

步骤3：采用启发式规则改进多目标遗传算法的初始化操作，得到改进的多目标遗传算法。Step 3: Use heuristic rules to improve the initialization operation of the multi-objective genetic algorithm to obtain an improved multi-objective genetic algorithm.

所述步骤3的具体操作为：采用多种初始化方式改进多目标遗传算法的初始化操作，所述多种初始化方式包括随机初始化方式、按照交付期规则优先级初始化方式和剩余加工时间优先级初始化方式。The specific operation of step 3 is: using multiple initialization methods to improve the initialization operation of the multi-objective genetic algorithm, and the multiple initialization methods include a random initialization method, an initialization method based on the priority of the delivery period rule, and an initialization method based on the priority of the remaining processing time.

步骤4：采用改进的多目标遗传算法优化求解所述大型复杂产品装配与调试车间调度优化模型，得到大型复杂产品装配与调试车间目标调度决策和目标完工时间。 Step 4: Use an improved multi-objective genetic algorithm to optimize and solve the scheduling optimization model of the large-scale complex product assembly and debugging workshop to obtain the target scheduling decision and target completion time of the large-scale complex product assembly and debugging workshop.

所述步骤4具体包括以下操作：The step 4 specifically includes the following operations:

步骤42：展开所述工件工艺结构树，得到工件工序工艺结构树信息；Step 42: Expand the workpiece process structure tree to obtain workpiece process structure tree information;

所述步骤44具体包括以下步骤：The step 44 specifically includes the following steps:

工作原理：本实施例首先将同时考虑大型复杂产品装配与调试调度决策问题转化为组合优化的数学模型问题，其次以复杂产品最大完工时间最小为优化目标，同时考虑大型复杂产品工序之间的优先级约束、装配调试设备及工具资源、装配调试工人资源等约束条件，构建大型复杂产品装配与调试车间调度决策模型；最后采用多目标遗传算法进行求解，在求解过程中，针对装配调试调度问题对工人资源的需求设计了能在装配调试过程满足工人资源的分配调度算法，保证在装配调试过程能与实际生产过程高度匹配。通过本实施例所求得的调度方案可有效求解具有多资源需求的大型复杂产品装配调试的调度问题。Working principle: This embodiment first transforms the scheduling decision problem of assembling and debugging large and complex products into a mathematical model problem of combinatorial optimization. Secondly, the optimization goal is to minimize the maximum completion time of complex products. At the same time, the priority constraints between the processes of large and complex products, assembly and debugging equipment and tool resources, assembly and debugging worker resources and other constraints are considered to build a scheduling decision model for the assembly and debugging workshop of large and complex products. Finally, a multi-objective genetic algorithm is used for solving. In the solving process, an allocation scheduling algorithm that can meet the needs of worker resources in the assembly and debugging process is designed according to the demand for worker resources in the assembly and debugging scheduling problem, ensuring that the assembly and debugging process can be highly matched with the actual production process. The scheduling scheme obtained by this embodiment can effectively solve the scheduling problem of assembly and debugging of large and complex products with multiple resource requirements.

实施例2：Embodiment 2:

本实施例在上述实施例1的基础上，如图1、图2、图3、图4、图5、图6所示，以一个具体的实施例对步骤1-步骤4的具体操作进行详细说明。Based on the above-mentioned embodiment 1, this embodiment, as shown in Figures 1, 2, 3, 4, 5 and 6, describes in detail the specific operations of steps 1 to 4 with a specific embodiment.

步骤1：确定装配调试调度决策问题的描述和相关假设。Step 1: Determine the description and related assumptions of the assembly debugging scheduling decision problem.

装配车间调度问题AASSP是在大型复杂产品装配调试过程加工过程中考虑装配调试设备工具和工人资源的多资源调度问题。大型复杂产品的装配过程首先需要按照产品各工序之间的存在优先级先后关系的工艺结构，然后在调度过程中需要为该工件的每道工序选择合适的装配调试设备工具，其次根据工艺信息调度相应需要的装配工人，直到完成对大型复杂产品所有工序的资源调度。The Assembly Shop Scheduling Problem (AASSP) is a multi-resource scheduling problem that considers assembly and debugging equipment, tools, and worker resources during the assembly and debugging process of large and complex products. The assembly process of large and complex products first needs to follow the process structure with a priority relationship between the various processes of the product, and then in the scheduling process, it is necessary to select a schedule for each process of the workpiece. Appropriate assembly and debugging equipment and tools are used, and then the required assembly workers are scheduled according to the process information until the resource scheduling of all processes of large and complex products is completed.

装配车间调度问题AASSP建立的前提假设包括：The premise assumptions for the assembly shop scheduling problem AASSP include:

(1)每个设备工具资源同一时刻只能允许一道工序的装配或调试。(1) Each equipment tool resource can only allow one process to be assembled or debugged at a time.

(2)在作业过程中，除非发生质量问题，否则被工序不会中断。(2) During the operation, the process will not be interrupted unless quality problems occur.

(3)车间内每种工人资源的数量是有限的，在满足工序对设备工具资源的占用时，还需要考虑当日工人是否充足，未达到开工条件，则延迟开工。(3) The number of each type of worker resource in the workshop is limited. When satisfying the occupation of equipment and tool resources by the process, it is also necessary to consider whether there are enough workers on that day. If the conditions for starting work are not met, the start of work will be delayed.

(4)已调度到某一工序上的工人，在该工序没有完成时，不可被调度到其他工序上加工，避免该工序的中断。(4) Workers who have been assigned to a certain process cannot be assigned to other processes before the process is completed, so as to avoid interruption of the process.

(5)物流时间忽略不计。因为运输时间相对于作业时间而言较小，且实际车间通常运输能力充足，所以忽略运输时间。(5) Logistics time is negligible. Because transportation time is relatively small compared to operation time and actual workshops usually have sufficient transportation capacity, transportation time is negligible.

(6)作业之间的优先级根据工艺树确定，即后继作业所有工序必须等其前序作业所有工序全部完工后才能开始。(6) The priority between operations is determined according to the process tree, that is, all processes of the subsequent operation must wait until all processes of the predecessor operation are completed before they can begin.

(7)所有工具/设备和工人在零时刻都可被占用和调度。(7) All tools/equipment and workers can be occupied and dispatched at time zero.

装配车间调度问题AASSP描述如下：在某车间内有m种类型的装配设备/工具、k类不同技能的工人和n个待装配的大型复杂工件集，工件之间具有基于BOM的工艺层次结构，即之间有紧前紧后关系和优先级，每个工件包含相同或不同的工序数量，其工序信息已知，且每道工序可选择工具/设备至少一个。在考虑大型复杂产品的工序满足优先级约束情况下，为所有工件确定一个合理的先后装配顺序，在调度过程中为每道工序选择一个合适的工具/设备，并配置合理数量的工人，以使得所有工件的最大完工时间最小。The assembly shop scheduling problem AASSP is described as follows: In a workshop, there are m types of assembly equipment/tools, k types of workers with different skills, and n large and complex workpieces to be assembled. The workpieces have a process hierarchy based on BOM, that is, there is a close relationship and priority between them. Each workpiece contains the same or different number of processes, and its process information is known, and at least one tool/equipment can be selected for each process. Considering that the processes of large and complex products meet the priority constraints, a reasonable assembly sequence is determined for all workpieces. In the scheduling process, a suitable tool/equipment is selected for each process, and a reasonable number of workers are allocated to minimize the maximum completion time of all workpieces.

J表示工件的集合{1,2,3…,j}，其中j代表索引；Inf表示一个极大值；i∈O_j表示是属于工件j包含工序i；表示工件j的第i道工序使用工具/设备M_p加工；M_i,j表示工件j的第i道工序的可选工具/设备集合；表示工件j的第i道工序使用工具/设备p、加工的开始时间；表示为工件j的第i道工序使用工具/设备p的完工时间；t_j,i表示工件j的第i道工序所需加工时间；F_j表示工件j的前置工件集合{1,2,3…,j’}，其中j’表示前置工件的索引；i’∈O_j’表示前置工件j’包含工序i’；表示第k类工人在时间a的可用数，其中a表示时间索引；H_k表示第k类资源的上限；工件j的第i道工序在第a时刻(小时)所占用第k种工人的数量；Q_i,j表示工件j的第i道工序前置工序集合{1,2,3…,i’}；决策变量，工件j的工序O_j,i选择工具/设备M_p进行加工，则否则决策变量，如果工件j的工序O_j,i在使用工具/设备M_p的加工顺序比工件j'的工序O_j’,i’使用工具/设备M_p加工的早，则否则 J represents the set of workpieces {1, 2, 3…, j}, where j represents the index; Inf represents a maximum value; i∈O _j means that workpiece j contains process i; represents the i-th process of workpiece j processed by tool/equipment M _p ; M _i,j represents the set of optional tools/equipment for the i-th process of workpiece j; It indicates the start time of the i-th process of workpiece j using tool/equipment p; represents the completion time of the i-th process of workpiece j using tool/equipment p; t _j,i represents the processing time required for the i-th process of workpiece j; F _j represents the set of predecessor workpieces of workpiece j {1,2,3…,j'}, where j' represents the index of the predecessor workpiece; i'∈O _j' means that the predecessor workpiece j' contains process i'; represents the number of workers of the kth category available at time a, where a represents the time index; H _k represents the upper limit of the kth category resources; The number of workers of the kth type occupied by the i-th process of workpiece j at the a-th time (hour); Qi _,j represents the set of predecessor processes {1,2,3…,i'} of the i-th process of workpiece j; Decision variables, If the process _Oj,i of part j selects tool/equipment _Mp for processing, then otherwise Decision variables, if the process O _j,i of workpiece j is processed earlier using tool/equipment M _p than the process O _j',i' of workpiece j' is processed earlier using tool/equipment M _p , then otherwise

步骤2：建立装配车间调度优化的数学模型。Step 2: Establish a mathematical model for assembly workshop scheduling optimization.

目标函数：最小化最大完工时间和任务总拖期量。
min f₁＝max{C_j|1≤j≤n} (1-1)
Objective function: Minimize the maximum completion time and the total delay of the task.
min f ₁ =max{C _j |1≤j≤n} (1-1)

式(1-1)中：f₁是最小化制造产品最大完工时间，C_j代表工件j的完工时间。In formula (1-1): f ₁ is the maximum completion time of the minimized manufacturing product, and C _j represents the completion time of workpiece j.

式(1-2)中，f₂是任务的总拖期量，d_j代表零部件j的交付期，w_j代表零部件j的拖期系数，C_j代表工件j的完工时间。In formula (1-2), _f2 is the total delay of the task, _dj represents the delivery time of component j, _wj represents the delay coefficient of component j, and _Cj represents the completion time of workpiece j.

约束条件如下：

The constraints are as follows:

式(3)中，表示为工件j的第i道工序在平台p上的完工时间；表示工件j的第i道工序在平台p上加工的开始时间。

In formula (3), It is expressed as the completion time of the i-th process of workpiece j on platform p; It indicates the start time of the i-th process of workpiece j on platform p.

式(5)中，t_j,i表示工件j的第i道工序加工时间。
In formula (5), tj _,i represents the processing time of the i-th process of workpiece j.

式(6)C_j，i′为工件j的第i道工序的前一道工序的完工时间。

S_j，i，C_j，i≥0，j∈J，i∈O_j (10)

Formula (6) _Cj,i′ is the completion time of the previous process of the i-th process of workpiece j.

S _j,i ,C _j,i ≥0,j∈J,i∈O _j (10)

其中：约束(2)表示工件每道工序只能占用一个工具或设备；约束(3)和约束(4)表示工序占用工具/设备的开工时间早于或等于该工序使用该设备的完工时间；约束(5)表示工件的开工时间需晚于或等于其所有前序工件所有工序的完工时间；约束(6)表示同一工件所有前道工序的完工时间均早于或等于后一道工序的开工时间；约束(7)和约束(8)表示不同工件的工序可占用同一个工具/设备时，不可同时进行工作，即在任何时候同一工具/设备正在使用的工件不能超过一个；约束(9)表示在任何时刻对每种工人的调用数量不能超过当前时间其实际车间该种工人数量上限；约束(10)～约束(12)表示决策变量为0-1变量。Among them: constraint (2) means that each process of a workpiece can only occupy one tool or equipment; constraints (3) and (4) mean that the start time of a process occupying a tool/equipment is earlier than or equal to the completion time of the process using the equipment; constraint (5) means that the start time of a workpiece must be later than or equal to the completion time of all processes of its predecessor workpieces; constraint (6) means that the completion time of all previous processes of the same workpiece is earlier than or equal to the start time of the next process; constraints (7) and (8) mean that when processes of different workpieces can occupy the same tool/equipment, they cannot work at the same time, that is, at any time, no more than one workpiece can be used by the same tool/equipment; constraint (9) means that the number of calls for each type of worker at any time cannot exceed the upper limit of the number of workers of that type in the actual workshop at the current time; constraints (10) to (12) mean that the decision variables are 0-1 variables.

步骤3：改进多目标遗传算法。Step 3: Improve the multi-objective genetic algorithm.

种群初始化是遗传算法求解装配车间综合调度问题中的重要环节，它不仅决定了在初始化阶段产生种群的质量，还对算法后期搜索效率和收敛速度有很大的影响。鉴于本发明数学模型目标函数包括最大完工时间、任务总拖期量，由于多目标搜索的解空间更复杂，给算法搜索增加了难度，因此需要对遗传算法的初始化操作进行改进，使其在对问题进行多目标求解时具有更高的效率和更好的求解效果。具体改进如下：Population initialization is an important step in solving the assembly workshop comprehensive scheduling problem with genetic algorithms. It not only determines the quality of the population generated in the initialization stage, but also has a great impact on the algorithm's later search efficiency and convergence speed. In view of the fact that the objective function of the mathematical model of the present invention includes the maximum completion time and the total delay of the task, the solution space of the multi-objective search is more complex, which increases the difficulty of the algorithm search. Therefore, it is necessary to improve the initialization operation of the genetic algorithm so that it has higher efficiency and better solution effect when solving the problem with multiple objectives. The specific improvements are as follows:

为控制遗传算法在求解时的全局上界，尽可能地使初始化得到的种群更靠近全局最优解，以提升算法在多目标搜索中的效率，采用现有启发式规则对多目标遗传算法的初始化操作进行改进，对此采用了三种方式的初始化操作，分别是随机初始化，按照交付期规则优先级初始化，按照交付期减去零部件生产周期剩余加工时间得到的优先级。In order to control the global upper bound of the genetic algorithm when solving the problem and make the initialized population closer to the global optimal solution as much as possible, so as to improve the efficiency of the algorithm in multi-objective search, the initialization operation of the multi-objective genetic algorithm is improved by using the existing heuristic rules. Three initialization operations are adopted, namely random initialization, priority initialization according to the delivery period rule, and priority obtained by subtracting the remaining processing time of the component production cycle from the delivery period.

采用以交付期优先级为参考产生的初始解，基于交付期优先级排序初始化规则产生的基因个体X₂和基于剩余加工时间优先级排序规则产生的基因个体X₃更容易分布在以任务总拖期量为目标的解空间附近，而随机初始化产生的初始种群则无太多规律地散落在整个解空间。Using the initial solution generated with the delivery date priority as a reference, the gene individuals _X2 generated based on the delivery date priority sorting initialization rule and the gene individuals _X3 generated based on the remaining processing time priority sorting rule are more likely to be distributed near the solution space with the total task delay as the target, while the initial population generated by random initialization is scattered throughout the solution space without much regularity.

采用后两种启发式规则初始化产生的解可以为部分基因个体提供一个朝交付期优先级爆炸的方向，并且采用规则初始化得到的基因个体X₂、X₃与包含最大完工时间和任务总拖期量的多目标近似最优解的距离d₂、d₃相较d₁可能更短，这样可以为算法节省大量时间来搜索满足任务总拖期量最小的优质解。为了在不影响烟花种群多样性的前提下引入规则初始化操作，本实施例设置的三种初始化方式的占比分别为随机初始化占40％、基于交付期优先级排序初始化占30％、基于剩余加工时间优先级初始化占30％。基于上述初始化改进方案，本发明提出了一种多目标遗传算法，流程如图1所示。The solutions generated by initializing with the latter two heuristic rules can provide a direction for some gene individuals to explode in the delivery priority, and the distances d ₂ and d ₃ between the gene individuals X ₂ and X ₃ initialized with the rules and the multi-objective approximate optimal solutions including the maximum completion time and the total delay of the task may be shorter than d ₁ , which can save a lot of time for the algorithm. Search for a high-quality solution that satisfies the minimum total delay of the task. In order to introduce regular initialization operations without affecting the diversity of the fireworks population, the three initialization methods set in this embodiment account for 40% of random initialization, 30% of initialization based on delivery period priority sorting, and 30% of initialization based on remaining processing time priority. Based on the above initialization improvement scheme, the present invention proposes a multi-objective genetic algorithm, and the process is shown in Figure 1.

步骤4：结合编码解码方式求解。Step 4: Solve by combining encoding and decoding methods.

(1)编码设计(1) Coding design

编码和解码在求解该特殊问题是影响算法性能的关键问题。与普通的车间调度问题不同，装配调试的调度决策问题的编码需考虑在装配调试工艺中工件之间存在的前后加工顺序的约束，为了产生满足该约束的合法基因结构，本实施例设计了一种基于产品BOM相关的结构工艺树的适用于综合调度问题求解的编码方法。以如图2所示的简单产品工艺树为例。每种工件在各道工序的加工时间以及对工人种类及需求情况如表表1所示。根据表表1信息将如图2所示工艺树进行展开，可得到如图3所示的详细工序工艺树信息。图3中箭头的指向代表工艺的顺序，被指向的工序需要在前序工件的所有工序完成后才能进行调度，当无箭头输入时则代表此工序无前序工件，如首次可调度工件集为{J₁,J₂,J₄,J₅,J₆,J₈,J₉,J₁₀}，其对应的可调度工序集为{O_1,1,O_2,1,O_4,1,O_5,1,O_6,1,O_8,1,O_9,1,O_10,1}。Encoding and decoding are key issues that affect the performance of the algorithm when solving this special problem. Different from ordinary workshop scheduling problems, the encoding of the scheduling decision problem of assembly and debugging needs to take into account the constraints of the forward and backward processing order between the workpieces in the assembly and debugging process. In order to generate a legal gene structure that meets this constraint, this embodiment designs a coding method suitable for solving comprehensive scheduling problems based on a structural process tree related to the product BOM. Take the simple product process tree shown in Figure 2 as an example. The processing time of each workpiece in each process and the types and requirements of workers are shown in Table 1. According to the information in Table 1, the process tree shown in Figure 2 is expanded to obtain the detailed process tree information shown in Figure 3. The direction of the arrows in Figure 3 represents the order of the processes. The pointed process can only be scheduled after all processes of the predecessor workpiece are completed. When there is no arrow input, it means that this process has no predecessor workpiece. For example, the first schedulable workpiece set is {J ₁ , J ₂ , J ₄ , J ₅ , J ₆ , J ₈ , J ₉ , J ₁₀ }, and its corresponding schedulable process set is {O _1,1 , O _2,1 , O _4,1 , O _5,1 , O _6,1 , O _8,1 , O _9,1 , O _10,1 }.

表1零部件各工序对工人的需求及加工时间
Table 1 The demand for workers and processing time for each process of parts

基于图2所示工艺树，可按照以下步骤执行个体编码以产生如图4所示的合法基因结构：Based on the process tree shown in FIG2 , individual coding can be performed according to the following steps to generate a legal gene structure as shown in FIG4 :

步骤S1：录入工艺树和对应工具/设备及工人信息，设置备选零部件集Can，初始化当前维度z＝1，总维度为Z，即总零部件数；Step S1: Enter the process tree and the corresponding tools/equipment and worker information, set the candidate parts set Can, initialize the current dimension z=1, and the total dimension is Z, that is, the total number of parts;

步骤S2：扫描工艺树所有零部件，将入度为0的零部件放入备选零部件集Can，更新备选零部件集；Step S2: Scan all parts in the process tree, put the parts with in-degree 0 into the candidate parts set Can, and update the candidate parts set;

步骤S3：在备选零部件集合中产生随机数来确定此次调度的零部件j，将该零部件j放到烟花的维度z；Step S3: Generate a random number in the candidate component set to determine the component j to be scheduled this time, and place the component j in the dimension z of the fireworks;

步骤S4：在工艺树上检索当前被调度零部件的后继零部件，该后继零部件入度减1，当前维度z加1； Step S4: searching the process tree for the successor component of the currently scheduled component, the in-degree of the successor component is reduced by 1, and the current dimension z is increased by 1;

步骤S5：判断所有零部件是否调度完毕，即当前维度z是否超过总维度Z，如果是则转步骤S6，否则转向步骤S2；Step S5: Determine whether all parts have been scheduled, that is, whether the current dimension z exceeds the total dimension Z. If yes, go to step S6, otherwise go to step S2;

步骤S6：输出烟花个体。Step S6: Output individual fireworks.

按照上述流程过后，可以得到图6所示的结果，比如位于染色体的第七位的零部件J₃，结合表1，其工序1选用属于L₃的工具/设备M₅，占用装配工人2人；工序2选用工具或设备类型属于L₃的工具/设备M₅，占用调试工人4人；工序3选用工具/设备类型属于L₁的工具/设备M₁，占用打磨工人2人。After following the above process, the result shown in FIG6 can be obtained. For example, for component J ₃ located at the seventh position of the chromosome, combined with Table 1, its process 1 selects tool/equipment M ₅ belonging to L ₃ , which occupies 2 assembly workers; process 2 selects tool/equipment M ₅ belonging to L ₃ , which occupies 4 debugging workers; process 3 selects tool/equipment M ₁ belonging to L ₁ , which occupies 2 polishing workers.

按照图5所示流程过后，可以得到图5所示的结果，比如位于染色体的第七位的零部件J₃，结合表表1，其工序1选用属于L₃的工具或设备M₅，占用装配工人2人；工序2选用工具/设备类型属于L₃的工具/设备M₅，占用调试工人4人；工序3选用工具/设备类型属于L₁的工具/设备M₁，占用打磨工人2人。After following the process shown in FIG5 , the result shown in FIG5 can be obtained. For example, for component J ₃ located at the seventh position of the chromosome, combined with Table 1, its process 1 selects tool or equipment M ₅ belonging to L ₃ , which occupies 2 assembly workers; process 2 selects tool/equipment M ₅ belonging to L ₃ , which occupies 4 debugging workers; process 3 selects tool/equipment M ₁ belonging to L ₁ , which occupies 2 polishing workers.

本实施例的其他部分与上述实施例1相同，故不再赘述。The other parts of this embodiment are the same as those of the above-mentioned embodiment 1, and thus will not be described in detail.

实施例3：Embodiment 3:

本实施例在上述实施例1-实施例2任一项的基础上，以某生产复杂产品的大型装备制造企业分厂车间为例，该车间主要工具/设备信息组成：线束敷设工具L₁＝{M₁,M₂}，数量为2；线束安装工具L₂＝{M₃,M₄,M₅,M₆,M₇,M₈}；管路安装工具L₃＝{M₉,M₁₀,M₁₁,M₁₂,M₁₃,M₁₄}，数量为6；导通检测设备L₄＝{M₁₅}，数量为1；气密检测设备L₅＝{M₁₆}，数量为1；打磨工具L₆＝{M₁₇,M₁₈,M₁₉,M₂₀}，数量为4；紧固工具L₇＝{M₂₁,M₂₂,M₂₃,M₂₄}，数量为4；涂胶工具L₈＝{M₂₅}，数量为1；搭铁电阻检测工具L₉＝{M₂₆,M₂₇,M₂₈,M₂₉}，数量为4。各个工具/设备类型下的详细信息以及对应可加工工序如表2所示。Based on any one of the above-mentioned embodiments 1 to 2, this embodiment takes a branch workshop of a large-scale equipment manufacturing enterprise producing complex products as an example. The main tool/equipment information of the workshop is as follows: wire harness laying tool L ₁ = {M ₁ , M ₂ }, the quantity is 2; wire harness installation tool L ₂ = {M ₃ , M ₄ , M ₅ , M ₆ , M ₇ , M ₈ }; pipeline installation tool L ₃ = {M ₉ , M ₁₀ , M ₁₁ , M ₁₂ , M ₁₃ , M ₁₄ }, the quantity is 6; conduction detection equipment L ₄ = {M ₁₅ }, the quantity is 1; airtightness detection equipment L ₅ = {M ₁₆ }, the quantity is 1; grinding tool L ₆ = {M ₁₇ , M ₁₈ , M ₁₉ , M ₂₀ }, the quantity is 4; fastening tool L ₇ = {M 21 , M ₂₂ }, the quantity is 4; , M ₂₂ , M ₂₃ , M ₂₄ }, the quantity is 4; glue coating tool L ₈ = {M ₂₅ }, the quantity is 1; ground resistance detection tool L ₉ = {M ₂₆ , M ₂₇ , M ₂₈ , M ₂₉ }, the quantity is 4. The detailed information of each tool/equipment type and the corresponding process steps are shown in Table 2.

表2工具/设备详细信息
Table 2 Tool/Equipment Details

如表3所示，车间包含的工人班组有调试班组、装配班组、打磨班组、导通班组，其中装配班组有6人，焊接班组有26人，打磨班组有4人，导通班组为2人。每种工人可加工与技能对应的工序。As shown in Table 3, the workshop includes debugging team, assembly team, grinding team, and conduction team. The assembly team has 6 people, the welding team has 26 people, the grinding team has 4 people, and the conduction team has 2 people. The process that corresponds to work and skills.

表3工人信息
Table 3 Worker information

1、生产任务分析1. Production task analysis

(1)现有产品工艺信息(1) Existing product process information

每道工序生产实际和生产周期如表4所示。据调研，车间原排程调度计划是由排程调度人员按照以往生产经验根据产品的生产周期与交付期来确定生产计划，对车间设备工具资源以及工人资源的全局把控不足，为了满足产品交付，经常导致车间加班以及对设备工具和工人的调度不均衡。与此同时在生产过程中存在急件插单、装配调试过程中质量问题导致中断、检测出质量问题导致返工等干扰因素，这些车间中常见的动态扰动给车间计划生产决策增添了很大的难度，频繁的扰动会导致任务中大量任务完工时间滞后于约定交付期，从而造成效益上的损失。The actual production and production cycle of each process are shown in Table 4. According to the survey, the original scheduling plan of the workshop was determined by the scheduling personnel according to the previous production experience and the production cycle and delivery period of the product. The overall control of the workshop equipment, tool resources and worker resources was insufficient. In order to meet the product delivery, the workshop often worked overtime and the scheduling of equipment, tools and workers was unbalanced. At the same time, there are interference factors such as urgent orders, interruptions caused by quality problems during assembly and debugging, and rework caused by quality problems in the production process. These common dynamic disturbances in the workshop have added great difficulty to the workshop's production planning decisions. Frequent disturbances will cause the completion time of a large number of tasks in the task to lag behind the agreed delivery period, resulting in a loss of benefits.

表4产品零部件工序装配时间(单位：小时)

Table 4 Product parts process assembly time (unit: hours)

每道工序需要占用相应的设备工具，其中每种设备工具的数量至少为1个，如表5所示，产品类别为1的工序1需要的设备工具类型为L₉，从表5中读取到该类型的可选设备工具为{M₂₆,M₂₇,M₂₈,M₂₉}。Each process needs to occupy corresponding equipment tools, and the number of each equipment tool is at least 1. As shown in Table 5, the equipment tool type required for process 1 with product category 1 is L ₉ . The optional equipment tools of this type read from Table 5 are {M ₂₆ , M ₂₇ , M ₂₈ , M ₂₉ }.

表5产品零部件工序工具类型需求
Table 5 Product parts process tool type requirements

车间的各类工人资源是有限的，在一些工序的加工中需要对这些工人在当日可调度的余量进行考虑，一般在装配工序需要的工人类型为H₁，在焊接工序需要的工人类型为H₂，在打磨工序需要的工人类型为H₃，在油漆工序需要的工人类型为H₄，对于每种类型产品对于工人的具体需求数量如表6所示。The various types of worker resources in the workshop are limited. In the processing of some processes, it is necessary to consider the margin of these workers that can be dispatched on the day. Generally, the type of worker required in the assembly process is _H1 , the type of worker required in the welding process is _H2 , the type of worker required in the grinding process is _H3 , and the type of worker required in the painting process is _H4 . The specific number of workers required for each type of product is shown in Table 6.

表6产品零部件工序工人需求
Table 6 Product parts process worker requirements

基于以上不同类型的产品零部件装配需求，在实际生产中，某次任务计划采用工艺树表示，零部件之间的工艺顺序约束如图7所示。图中对多批量同种类型的产品进行了简化，例如工艺树第一行从左往右第一个矩形框中“线束2×4”代表该类型产品的需求量为4。该任务原计划装配总周期为160小时。对图7所示的工艺树进行零部件编号，编号后的结果如图8所示，其中第一行从左往右第一个方框中J₃₉-J₄₂代表零部件类型为线束2的零部件装配工序包括{J₃₉,J₄₀,J₄₁,J₄₂}，最末行从左往右第一个方框J₁代表零部件类型为氧气管路1的零部件装配工序包括{J₁}。所有任务对应安装完成期限如表1所示，J₁对应安装完成期限为生产进行的第50小时。Based on the above different types of product component assembly requirements, in actual production, a certain task plan is represented by a process tree, and the process sequence constraints between components are shown in Figure 7. The figure simplifies multiple batches of the same type of products. For example, the "wire harness 2×4" in the first rectangular box from left to right in the first row of the process tree represents that the demand for this type of product is 4. The original total assembly cycle of the task was 160 hours. The components of the process tree shown in Figure 7 are numbered, and the numbered result is shown in Figure 8, where the first row from left to right in the first box J ₃₉ -J ₄₂ represents that the component type is wire harness 2, and the component assembly process includes {J ₃₉ , J ₄₀ , J ₄₁ , J ₄₂ }, and the last row from left to right in the first box J ₁ represents that the component type is oxygen pipeline 1. The corresponding installation completion deadlines for all tasks are shown in Table 1, _{and the corresponding installation completion deadline for J 1} _is production. The production is in its 50th hour.

表7交付期信息
Table 7 Delivery period information

2、问题求解及分析2. Problem solving and analysis

对以上车间实例进行分析可以发现，在实际生产调度过程中需要在排程计划阶段考虑工具/设备资源与工人资源上限和复杂工艺约束影响，即本发明所提出装配调试调度建模和求解。因此将综合调度问题模型应用到此问题上，可解决车间的初始排程调度问题。本节采用基于python 3.7的pycharm软件工具进行仿真优化求解，多目标遗传算法参数设置如下：By analyzing the above workshop examples, it can be found that in the actual production scheduling process, it is necessary to consider the upper limit of tool/equipment resources and worker resources and the influence of complex process constraints in the scheduling planning stage, that is, the assembly debugging scheduling modeling and solution proposed in this invention. Therefore, applying the comprehensive scheduling problem model to this problem can solve the initial scheduling problem of the workshop. This section uses the pycharm software tool based on python 3.7 for simulation optimization and solution, and the multi-objective genetic algorithm parameters are set as follows:

根据相关经验设置初始化种群参数：烟花种群数量K为50，爆炸次数IT为100，高斯概率Pm为0.25；三种初始化分配方案为随机初始化40％，按交付期初始化30％，按交付期与生产周期之间的差值优先级初始化30％。The initialization population parameters are set according to relevant experience: the number of fireworks population K is 50, the number of explosions IT is 100, and the Gaussian probability Pm is 0.25; the three initialization allocation schemes are random initialization of 40%, initialization by delivery period of 30%, and initialization by priority of the difference between the delivery period and the production cycle of 30%.

3、工程实例调度求解3. Engineering example scheduling solution

首先采用本实施例提出的多目标遗传算法MOGA对初始调度问题模型进行求解，在考虑上述设备工具资源、工人资源以及复杂工艺的约束条件下，连续计算10次，计算结果如表8所示，为验证本发明所提的多目标遗传算法在求解有效性，采用前文提出的三种对比算法遗传算法GA、离散烟花算法DFWA、以及独立框架的烟花算法CoFFA分别对本实例进行求解，设置实验次数为10次，最后取每种算法在10次求解结果的平均值和最优值进行对比，对比结果如表8所示。
First, the multi-objective genetic algorithm MOGA proposed in this embodiment is used to solve the initial scheduling problem model. Considering the constraints of the above-mentioned equipment and tool resources, worker resources and complex processes, 10 consecutive calculations are performed. The calculation results are shown in Table 8. In order to verify the effectiveness of the multi-objective genetic algorithm proposed in the present invention in solving the problem, the three comparative algorithms proposed in the previous text, namely the genetic algorithm GA, the discrete fireworks algorithm DFWA, and the independent framework fireworks algorithm CoFFA, are used to solve this example respectively. The number of experiments is set to 10 times. Finally, the average value and the optimal value of the 10 solution results of each algorithm are compared. The comparison results are shown in Table 8.

从表8中的对比结果可以看出，本发明提出多目标遗传算法在对面向复杂产品生产的带有设备工具资源和工人资源约束的车间综合调度问题上，在与车间原定生产周期的对比中，求得最大完工时间近似最优值较原定交付期提前9.9％；在与其他智能算法的对比中，求解得到的以最大完工时间和订单总拖期量为目标的最小值和平均值均优于另外几种算法，在连续求解10次的实验结果表示MOGA相比于FA、GA、CoFFA求解结果完工时间与总拖期量平均值分别优化1.29％、1.43％、2.15％，由此可得出多目标遗传算法求解精度更高。From the comparison results in Table 8, it can be seen that the multi-objective genetic algorithm proposed in the present invention is used in the comprehensive scheduling problem of workshops with equipment, tool resources and worker resources constraints for the production of complex products. In comparison with the original production cycle of the workshop, the approximate optimal value of the maximum completion time is obtained, which is 9.9% ahead of the original delivery date; in comparison with other intelligent algorithms, the minimum and average values obtained with the maximum completion time and the total order delay as the target are better than those of several other algorithms. The experimental results of 10 consecutive solutions show that the completion time and the average value of the total delay of MOGA are optimized by 1.29%, 1.43% and 2.15% respectively compared with those of FA, GA and CoFFA. It can be concluded that the multi-objective genetic algorithm has higher solution accuracy.

四种算法对于最优解的搜寻迭代曲线如图9所示，可看出本发明的多目标遗传算法能在有限的搜索时间内更快更稳定地收敛至近似最优解。The search iteration curves of the four algorithms for the optimal solution are shown in FIG9 . It can be seen that the multi-objective genetic algorithm of the present invention can converge to the approximate optimal solution faster and more stably within a limited search time.

由于加工过程中不仅需要考虑设备工具的空闲，还需要考虑装配工人、调试工人的资源上限，当所有零部件都需要进行装配时，装配工人就成了瓶颈资源，此时会造成一些零部件无法进行装配工序，导致部分设备工具处于空闲的状态。本实施例以某大型复杂产品制造企业车间的生产实例为背景，将带有50个零部件的生产任务为输入，应用本实施例所提模型以及算法进行求解，最后在静态实例中求得最大完工时间为142小时，订单总拖期量为4，比原本计划生产周期节省了9.9％。Since the processing process not only needs to consider the idleness of equipment and tools, but also the resource limit of assembly workers and debugging workers, when all parts need to be assembled, assembly workers become bottleneck resources, which will cause some parts to be unable to be assembled, resulting in some equipment and tools being idle. This embodiment takes the production example of a workshop of a large complex product manufacturing enterprise as the background, takes the production task with 50 parts as input, and applies the model and algorithm proposed in this embodiment to solve it. Finally, in the static example, the maximum completion time is obtained as 142 hours, and the total order delay is 4, which saves 9.9% compared with the originally planned production cycle.

本实施例的其他部分与上述实施例1-实施例2任一项相同，故不再赘述。The other parts of this embodiment are the same as any one of the above-mentioned embodiments 1-2, so they will not be repeated here.

实施例4：Embodiment 4:

本实施例在上述实施例1-实施例3任一项的基础上，提出一种大型复杂产品车间调度系统，包括初始化单元、模型建立单元、计算单元； This embodiment, based on any one of the above-mentioned embodiments 1 to 3, proposes a large-scale complex product workshop scheduling system, including an initialization unit, a model building unit, and a calculation unit;

本实施例还提出一种电子设备，包括存储器和处理器；所述存储器上存储有计算机程序；当所述计算机程序在所述处理器上执行时，实现上述的大型复杂产品车间调度方法。This embodiment also proposes an electronic device, including a memory and a processor; a computer program is stored in the memory; when the computer program is executed on the processor, the above-mentioned large-scale complex product workshop scheduling method is implemented.

本实施例还提出一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机指令；当所述计算机指令在上述的电子设备上执行时，实现上述的大型复杂产品车间调度方法。This embodiment also proposes a computer-readable storage medium, on which computer instructions are stored; when the computer instructions are executed on the above-mentioned electronic device, the above-mentioned large-scale complex product workshop scheduling method is implemented.

本实施例的其他部分与上述实施例1-实施例3任一项相同，故不再赘述。The other parts of this embodiment are the same as any one of the above-mentioned embodiments 1 to 3, so they will not be repeated here.

以上所述，仅是本发明的较佳实施例，并非对本发明做任何形式上的限制，凡是依据本发明的技术实质对以上实施例所作的任何简单修改、等同变化，均落入本发明的保护范围之内。 The above description is only a preferred embodiment of the present invention and does not limit the present invention in any form. Any simple modification or equivalent change made to the above embodiment based on the technical essence of the present invention shall fall within the protection scope of the present invention.

Claims

A scheduling method for a large-scale complex product workshop, characterized in that the scheduling decision problem and premise assumptions of the large-scale complex product assembly and debugging workshop are first determined to obtain the longest completion time of the workpiece, and then minimizing the longest completion time of the large-scale complex product workpiece is used as the optimization goal to establish a scheduling optimization model for the large-scale complex product assembly and debugging workshop; finally, a multi-objective genetic algorithm is used to optimize and solve the scheduling optimization model for the large-scale complex product assembly and debugging workshop to obtain the target scheduling decision and target completion time of the large-scale complex product assembly and debugging workshop.

The method for scheduling a large and complex product workshop according to claim 1 is characterized in that the method for scheduling a large and complex product workshop specifically comprises the following steps:

Step 1: Determine the scheduling decision problem and premise assumptions of the large-scale complex product assembly and debugging workshop, and obtain the longest completion time of the workpiece;

Step 2: According to the longest completion time of the workpiece, with minimizing the longest completion time of the workpiece and minimizing the total delay of the task as the optimization goal, set the priority constraints between the processes of large and complex products, the assembly and debugging equipment and tool resource constraints, and the assembly and debugging worker resource constraints, and establish a large and complex product assembly and debugging workshop scheduling optimization model;

Step 3: Using heuristic rules to improve the initialization operation of the multi-objective genetic algorithm to obtain an improved multi-objective genetic algorithm;

Step 4: Use an improved multi-objective genetic algorithm to optimize and solve the scheduling optimization model of the large-scale complex product assembly and debugging workshop to obtain the target scheduling decision and target completion time of the large-scale complex product assembly and debugging workshop.

The method for scheduling a large complex product workshop according to claim 2 is characterized in that step 1 specifically comprises the following steps:

Step 11: Determine the scheduling decision problems and assumptions of large and complex product assembly and commissioning workshops;

Step 12: When the processes of large and complex products meet the priority constraints, determine the assembly order of the workpieces, select the tools or equipment for the current process during the scheduling process, and allocate the corresponding number of workers to obtain the longest completion time of the workpiece.

The method for scheduling a large complex product workshop according to claim 2 is characterized in that step 2 specifically comprises the following steps:

Step 21: Obtaining a maximum completion time objective function of the workpiece according to the maximum completion time of the workpiece;

Step 22: Obtaining a total task delay objective function according to the longest completion time of the workpiece, the delivery period of the workpiece, and the delay coefficient of the workpiece;

Step 23: According to the objective function of the longest completion time of the workpiece and the objective function of the total delay of the task, set the priority constraints between the processes of large and complex products, the assembly and debugging equipment and tool resource constraints, and the assembly and debugging worker resource constraints, and establish a scheduling optimization model for the assembly and debugging workshop of large and complex products.

According to claim 2, a large-scale complex product workshop scheduling method is characterized in that the specific operation of step 3 is: using multiple initialization methods to improve the initialization operation of the multi-objective genetic algorithm, the multiple initialization methods include random initialization, initialization according to the delivery period rule priority, and initialization according to the remaining processing time priority. Mode.

The method for scheduling a large complex product workshop according to claim 2 is characterized in that step 4 specifically comprises the following operations:

Step 41: Establish a workpiece process structure tree;

Step 42: Expand the workpiece process structure tree to obtain workpiece process structure tree information;

Step 43: Perform chromosome encoding according to the workpiece process structure tree information to obtain a legal gene structure that satisfies the constraint condition of the front and back processing sequence between the workpieces in the assembly and debugging process;

Step 44: Decode according to the legal gene structure to obtain the target scheduling decision and target completion time of the large-scale complex product assembly and debugging workshop of the workpiece.

The method for scheduling a large complex product workshop according to claim 6 is characterized in that step 44 specifically comprises the following steps:

Step 441: Obtain a scheduling task, and traverse the artifacts in the chromosome sorting according to the legal gene structure;

Step 442: Retrieve the artifact type according to the artifact number;

Step 443: reading the process of the workpiece, and acquiring platform information of the process according to the process;

Step 444: selecting a corresponding tool according to the workpiece type, determining the remaining use time of the tool, determining whether the number of workers meets the set conditions according to the remaining use time, and calculating the current completion time;

Step 445: Determine whether all processes have been traversed. If not, return to step 443. If all processes have been traversed, determine whether all workpieces have been traversed. If not, return to step 441. If all workpieces have been traversed, use the current completion time as the target completion time and output the target scheduling decision for large and complex product assembly and debugging workshops.

A large-scale complex product workshop scheduling system, characterized by comprising an initialization unit, a model building unit, and a calculation unit;

The initialization unit is used to determine the scheduling decision problem and premise assumptions of the large-scale complex product assembly and debugging workshop to obtain the longest completion time of the workpiece;

The model building unit is used to establish a scheduling optimization model for large-scale complex product assembly and debugging workshops by taking minimization of the longest completion time of large-scale complex product workpieces as an optimization goal;

The computing unit is used to optimize and solve the scheduling optimization model of the large-scale complex product assembly and debugging workshop by using a multi-objective genetic algorithm to obtain the target scheduling decision and target completion time of the large-scale complex product assembly and debugging workshop.

An electronic device, characterized in that it includes a memory and a processor; a computer program is stored on the memory; when the computer program is executed on the processor, the large-scale complex product workshop scheduling method as described in any one of claims 1-7 is implemented.

A computer-readable storage medium, characterized in that computer instructions are stored on the computer-readable storage medium; when the computer instructions are executed on the electronic device as described in claim 9, the large-scale complex product workshop scheduling method as described in any one of claims 1-7 is implemented.