CN1529209A - Integrated Optimal Control Method for Mixed Batch Assembly Line - Google Patents

Abstract

The integrated optimization control method of mixed batch assembly line involves the integrated optimization control method of production planning, scheduling and simulation of mixed batch assembly line (that is, one assembly line can assemble multiple products at the same time). use the branch and bound algorithm to solve the mixed integer programming model of the mixed-batch assembly line; respectively obtain the best production plan of the mixed-batch assembly line with the rough production plan as the initial solution, that is, the product type and quantity, and the scheduling, that is, the assembly sequence; Observe the optimal scheduling process of the mixed-batch assembly line through animation scheduling simulation; judge whether it meets the customer's product requirements; if it is considered to meet the product requirements after animation scheduling simulation, it can be used as a formal plan and scheduling for execution; according to the formal plan And scheduling, arrange production and control the on-line of the products to be loaded, and control the operation of the mixed-batch assembly line according to the moving speed of the assembly line determined during the animation scheduling simulation.

Description

Integrated Optimal Control Method for Mixed Batch Assembly Line

Technical field

The invention relates to an integrated optimization control method for production planning, scheduling and simulation of a mixed-batch assembly line (that is, multiple products can be assembled on one assembly line at the same time), and can arrange production and control the operation of the mixed-batch assembly line accordingly. The invention belongs to the technical field of production line optimization control methods.

Background technique

Most of the existing production planning, scheduling and optimization literatures on mixed-batch assembly lines only involve production scheduling ^[1-8] , and rarely involve production planning ^[9] . In actual production, the production plan is often optimized first, and then the production scheduling is optimized on the basis of the optimized plan. As a result, the planning and scheduling cannot achieve overall optimization, and even the production plan leads to scheduling infeasibility or poor performance ^{.[ 10, 11]} . Tabu Search (Tabu Search) is an advanced heuristic method proposed by Glover ^{[12, 13]} to obtain approximate solutions to combinatorial optimization problems. At present, the tabu search method is mainly used in flow shop scheduling, job shop scheduling and manufacturing unit formation ^[14,15] , but its application in production planning and scheduling of mixed batch assembly lines is very rare. There are very few literatures on Petri net modeling of mixed batch assembly line. At present, it is only found that Kuo et al. used Colored Timed Petri Net (Colored Timed Petri Net) to establish a model of automobile mixed batch assembly system, and developed a model with different A real-time simulator of dispatch rules ^[16] . However, the model lacks decision points, and it is inconvenient to integrate scheduling rules into it. In contrast, the Extended Stochastic Advanced Judgment Petri Net (ESHLEP-N) includes decision points, and it is easier to integrate scheduling rules into it, so it is more suitable for establishing a scheduling simulation model of a mixed-batch assembly line.

[1]Agnetis A, Pacifici A, Rossi F, Lucertini M, Nicoletti S, Nicolo F, Oriolo G, Pacciarelli D, Pesaro E. Scheduling of flexible flow lines in an automobile assembly plant. European Journal of Operational Research, 1997, 97( 2), 348-362.

[2] Karabati S, Tan B. Stochastic cyclic scheduling problem in synchronous assembly and production lines. Journal of the Operational Research Society, 1998, 49(11), 1173-1187.

[3]Bolat A. Stochastic procedures for scheduling minimum job sets on mixed model assembly lines. Journal of the Operational Research Society, 1997, 48(5), 490-501.

[4]Hyun C J, Kim Y, Kim Y K.A genetic algorithm for multiple objective sequencing problems inmixed model assembly lines. Computers and Operations Research, 1998, 25(7/8), 675-690.

[5] Xiaobo Z, Ohno K. Algorithms for sequencing mixed models on an assembly line in a JIT production system. Computers and Industrial Engineering, 1997, 32(1), 47-56.

[6] Zhang Y, Luh P B, Yoneda K, Kano T, Kyoya Y. Mixed-model assembly line scheduling using the Lagrangian relaxation technique. IIE Transactions, 2000, 32(2), 125-134.

[7] Korkmazel T, Meral S. Bicriteria sequencing methods for the mixed-model assembly line injust-in-time production systems. European Journal of Operational Research, 2001, 131(1), 188-207.

[8] Ventura J A, Radhakrishnan S. Sequencing mixed model assembly lines for a just-in-time production system. Production Planning and Control, 2002, 13(2), 199-210.

[9] Balakrishnan A, Vanderbeck F. Tactical planning model for mixed-model electronics assembly operations. Operations Research, 1999, 47(3), 395-409.

[10]Lasserre J B. An integrated model for job-shop planning and scheduling. Management Science, 1992, 38(8), 1201-1211.

[11] Caridi M, Sianesi A. Multi-agent systems in production planning and control: an application to the scheduling of mixed-model assembly lines. International Journal of Production Economics, 2000, 68(1), 29-42.

[12] Glover F. Tabu search-part I. ORSA Journal on Computing, 1989, 1(3), 190-206.

[13] Glover F. Tabu search-part II. ORSA Journal on Computing, 1990, 2(1), 4-32.

[14] Nowicki E. The permutation flow shop with buffers: a tabu search approach. European Journal of Operational Research, 1999, 116(1), 205-219

[15] Armentano V A, Ronconi D P. Tabu search for total tardiness minimization in flowshop scheduling problems. Computers and Operations Research, 1999, 26(3), 219-235.

[16]Kuo C H, Huang H P, Wei K C, Tang S S H. System modeling and real-time simulator for highlymodel-mixed assembly systems. Journal of Manufacturing Science and Engineering, Transactions of the ASME, 1999, 121(2 ), 282-289.

Contents of Invention

Technical problem: the purpose of this invention is to provide a kind of assembly line that can assemble multiple products at the same time, and make the overproduction, underproduction and preparation cost of the product, the idle time of each assembly station, the scheduling span and the relationship between each assembly station An integrated optimization control method for a mixed batch assembly line to minimize the load deviation among them.

Technical solution: The present invention establishes a mixed integer programming model of a mixed-batch assembly line to use a branch-and-bound algorithm to obtain a rough production plan that minimizes the preparation cost and idle time of each assembly station and satisfies product requirements as much as possible. Then, on the basis of considering the details of the assembly line, an integrated optimization model for production planning and scheduling of the mixed-batch assembly line is established, and three simulation methods, including the embedded tabu search simulation method, the alternate tabu search simulation method, and the serial tabu search simulation method, are proposed. Different methods are used to solve the integrated optimization problem of production planning, scheduling and simulation of mixed-batch assembly line with rough production plan as the initial solution, and the computational complexity of these three methods is given. The integrated optimization control method of mixed batch assembly line of the present invention is characterized in that the method comprises the following steps (see Fig. 3):

(1) Smooth customer product demand;

(2) According to the smoothed product demand, the branch and bound algorithm is used to solve the mixed integer programming model of the mixed-batch assembly line, so as to obtain the rough plan that minimizes the preparation cost and idle time of each assembly station and satisfies the product demand as much as possible. Production Plan;

(3) On the basis of the integrated optimization model of production planning and scheduling of the mixed batch assembly line, aiming at three different levels of product types and quantities, such as small, medium and large, respectively use the embedded tabu search simulation method and the alternate tabu search The simulation method and the serial tabu search simulation method are used to obtain the best production plan of the mixed-batch assembly line with the rough production plan as the initial solution, that is, the product type and quantity, and the scheduling, that is, the assembly sequence;

(4) Observe the optimal scheduling process of the mixed-batch assembly line through animation scheduling simulation;

(5) Judging whether the product requirements of customers are met;

(6) If after animation simulation, it is considered that the requirements are not met, the best plan and scheduling can be properly modified and then simulated;

(7) If it is considered to meet the requirements after animation simulation, it can be used as a formal plan and schedule to be issued for execution;

(8) According to the formal plan and scheduling, arrange the production and control the on-line of the products to be installed, and control the operation of the mixed-batch assembly line according to the moving speed of the assembly line determined during the animation simulation.

Since the customer's product demand (order) is random and sudden, and product production needs to be carried out evenly and smoothly, it is necessary to smooth the customer's random and sudden demand into a demand that can make the production run smoothly and continuously. The method of demand smoothing is to smoothly allocate product orders to each planning interval according to the delivery date, importance and production capacity required by the product order, and according to the principle of the earliest delivery date and the most important priority.

The basic idea of the embedded tabu search simulation method is to use the rough production plan as the initial production plan to find a feasible plan and schedule, then use the tabu search to find the best plan at the planning layer, and use Another tabu search looks for the scheduling with the best performance index after fast simulation calculation, until the production planning and scheduling are optimized at the same time. Because a tabu search nests another tabu search and uses fast simulation to calculate the scheduling index, it is called the embedded tabu search simulation method. The basic idea of the alternate tabu search simulation method is: (1) use the rough production plan as the initial production plan to find a feasible plan and schedule; (2) given the schedule, use the tabu search to find the best performance index after fast simulation calculation. Plan; (3) Given the plan in turn, use another tabu search to find the schedule with the best performance index after fast simulation calculation; (4) Use (2) and (3) alternately until the best plan is found with scheduling. Since two tabu searches are alternately used for planning and scheduling respectively and their performance indicators are calculated by fast simulation, it is called alternate tabu search simulation method. The basic idea of the serial tabu search simulation method is: (1) use the rough production plan as the initial production plan to find a feasible plan and schedule; (2) start from the feasible plan, use tabu search to find a rule-based schedule and perform fast simulation calculations The plan with the best performance index; (3) For the best plan, use another tabu search to find the schedule with the best performance index after fast simulation calculation. Because tabu search is used sequentially for planning and scheduling and its performance index is calculated by fast simulation, it is called serial tabu search simulation method. The fast simulation of these three methods is realized by using the extended stochastic high-level judgment Petri net to establish the scheduling simulation model and the object-oriented technology meter, and the variable time flow is used to control the simulation process. The meaning of fast here is that there is no dynamic display of text and graphics, and only the performance index of a given schedule is calculated through fast simulation. The above methods and simulations are compiled into software with Microsoft VisualC ⁺⁺ 5.0. After obtaining the production plan and scheduling with the best performance index by the above method, the production can be arranged accordingly and the operation of the mixed batch assembly line can be controlled. Compared with the traditional method, the present invention has the advantage of organically combining the analysis method, tabu search and fast scheduling simulation, effectively solving the integrated optimization problem of production planning, scheduling and simulation of the mixed-batch assembly line, and ensuring that at least one Feasible solution. The problem solving speed of the embedded tabu search simulation method is the slowest, but the performance index obtained is often the best; the problem solving speed and the obtained performance index of the serial tabu search simulation method are just opposite to the embedded tabu search simulation method; The formula tabu search simulation method is between the embedded tabu search simulation method and the serial tabu search simulation method. The embedded tabu search simulation method is suitable for solving small problems, the alternating tabu search simulation method is suitable for solving medium-scale problems, and the serial tabu search simulation method is suitable for solving large-scale problems.

Beneficial effects: the present invention solves the problem of integrated optimization control of production planning, scheduling and simulation of mixed-batch assembly line, provides the generation method of rough production plan, proposes embedded tabu search simulation method, alternate tabu search simulation method and serial The tabu search simulation methods are presented and their computational complexity and implementation methods are given. The ESHLEP-N model of the mixed-batch assembly line is established for the scheduling simulation and an object-oriented implementation method is given. On this basis, an integrated optimization software for production planning, scheduling and simulation of mixed batch assembly line was developed by using Microsoft Visual C ⁺⁺ 5.0. With the help of these software, a comparative study has been carried out with a large number of calculation examples, and the results show that:

(1) Compared with the traditional method, the advantage of the present invention is that the analysis method, tabu search and fast scheduling simulation are organically combined, effectively solving the integrated optimization problem of production planning and scheduling of mixed batch assembly lines, and ensuring that at least one Feasible solution.

(2) The problem solving time of the embedded tabu search simulation method and the alternating tabu search simulation method is 38.69 and 1.73 times longer than the serial tabu search simulation method respectively, but the embedded tabu search simulation method and the alternating tabu search simulation method The best performance index and average less than the serial tabu search simulation method were 7.78% and 5.16%.

(3) The embedded tabu search simulation method is suitable for solving small problems, the alternating tabu search simulation method is suitable for solving medium-scale problems, and the serial tabu search simulation method is suitable for solving large-scale problems. If the problem is very large, it is recommended to use Step 1-2 of Algorithm 4 to find the feasible plan and scheduling as the solution of the problem.

(4) The average performance index improvement rates of embedded tabu search simulation method, alternating tabu search simulation method and serial tabu search simulation method from feasible planning and scheduling to best planning and scheduling are 18.87% and 22.05% respectively. % and 25.49%.

(5) The integrated optimization problem of production planning and scheduling of mixed-batch assembly line with random characteristics can be solved by Monte Carlo operation of embedded tabu search simulation method, alternate tabu search simulation method and serial tabu search simulation method.

(6) ESHLEP-N has the advantages of intuitive image, simple structure, few nodes, good description, strong decision-making ability, double token and double identification, etc., which is very suitable for modeling and scheduling simulation of mixed batch assembly line.

In addition, the embedded tabu search simulation method, alternate tabu search simulation method and serial tabu search simulation method of the present invention can also be used to solve models whose objective functions and constraints are different from equations (9)-(11).

After using the embedded tabu search simulation method, alternate tabu search simulation method and serial tabu search simulation method to obtain the best plan and scheduling, you can observe the optimal scheduling process of the mixed-batch assembly line through animation scheduling simulation to judge whether it meets the customer's requirements product demand. If after animation simulation, it is considered that the requirements are not met, the best plan and scheduling can be modified appropriately and then simulated. If it is considered to meet the requirements after animation simulation, it can be used as a formal plan and schedule to be issued for execution. Then, the production can be arranged according to the formal plan (product type and quantity) and scheduling (assembly sequence) of the above-mentioned mixed-batch assembly line, and the operation of the mixed-batch assembly line can be controlled according to the moving speed of the assembly line determined during animation simulation.

Description of drawings

Figure 1 is a schematic diagram of a linear assembly line.

Figure 2 is a schematic diagram of a U-shaped assembly line.

Fig. 3 is a schematic diagram of the overall flow of the integrated optimization control method of planning, scheduling and simulation of the mixed batch assembly line.

Fig. 4 is a flowchart of the embedded tabu search simulation method.

Fig. 5 is a flowchart of scheduling optimization based on tabu search.

Fig. 6 is a flow chart of the alternate tabu search simulation method.

Fig. 7 is a flow chart of the serial tabu search simulation method.

Fig. 8 is a flowchart of a schedule determination algorithm corresponding to a given plan.

Figure 9 is the ESHLEP-N graph model of the mixed batch assembly line.

FIG. 10 is a main flowchart of system transition processing.

Fig. 11 is a processing flow chart of transition t ₁ of "products to be loaded onto the assembly line".

Fig. 12 is a processing flow chart of the "start assembly" transition _t2 .

Fig. 13 is a processing flow chart of the "assemble complete" transition _t3 .

Fig. 14 is a processing flow chart of the transition _t4 of "fault occurrence".

Fig. 15 is a flowchart of the transition "failure end" _t5 .

Fig. 16 is a flow chart of transition processing in the blocked state.

Figure 17 is a structural diagram of integrated optimization software for production planning, scheduling and simulation of a mixed-batch assembly line.

Detailed ways

The technical solution adopted by the present invention to solve its technical problems and the specific implementation methods are as follows

1. Mixed batch assembly line:

The mixed batch assembly line that the present invention relates to has two kinds, promptly linear assembly line (see Fig. 1) and U-shaped assembly line (see Fig. 2). In the figure, stations 1 and m (1<k<m) represent the on-line assembly station and the off-line assembly station of the product respectively, and the arrows represent the moving direction of the product during the assembly process. Each assembly station can be distributed on both sides of the assembly line, or on one side, with a buffer zone. Each station can only hold at most one product at any time. The total number of products on the line is at most equal to the number m of stations on the line at any time, that is, if there is one product at each station at a certain moment, the only way to wait is for a product to be installed and placed at the last station m. A product to be loaded (that is, a product waiting to be assembled) can be put on the line at station 1 only after it has been online. The synchronous moving speed of the assembly line is variable and is determined by the assembly speed of the last station m when there is no full buffer on the line, and determined by the assembly speed of the bottleneck station when there is a full buffer. Since it may take different time for each station to assemble different products, the bottleneck station may be transferred when the product type and mixed batch change. The buffer here is a logical and virtual concept. In fact, there is no real buffer zone, but a virtual buffer zone is logically formed by allowing assembly workers to go beyond their own work area and complete assembly tasks in the work area of other stations.

2. Rough production plan:

As mentioned earlier, a mixed-batch assembly line has m assembly stations in total. According to the assembly order, a total of n products are required to be installed in the planning interval of the current design, and d _i products are required for the i-th product. Then the assembly line is simplified as a flow shop problem, and the goal of the optimal plan is to satisfy the product demand to the greatest extent and to minimize the preparation cost and idle time of each assembly station, then a hybrid solution for the optimal rough production plan can be established The integer programming model is as follows:

$\mathrm{<span\; class="notranslate">\; min</span>}\mathrm{<span\; class="notranslate">\; J</span>}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; [</span>{\mathrm{<span\; class="notranslate">\; a</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{<span\; class="notranslate">\; +</span>}{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>}^{<span\; class="notranslate">\; +</span>}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; a</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{<span\; class="notranslate">\; -</span>}{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>}^{<span\; class="notranslate">\; +</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; +</span>\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}\mathrm{<span\; class="notranslate">\; sgn</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; \&tau;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

$\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; .</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; .</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; +</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\mathrm{<span\; class="notranslate">\; \&Delta;</span>}{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}\mathrm{<span\; class="notranslate">\; sgn</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; \&tau;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; \&beta;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

x _i ≥ 0 and an integer, τ _j ≥ 0, j=1, 2, ..., m (3) In the formula: n is the number of product types to be assembled in the planning interval; m is the number of assembly stations on the mixed batch assembly line ; x _i is the output of the i-th product assembled in the planning interval, which is an integer; sgn(xi ₎ is a sign function, when x _i > 0, sgn( _xi ) takes 1, otherwise it takes 0; d _i is the plan The demand for the i-th product in the interval is an integer; τ _j is the idle time of the j-th assembly station in the planning interval; β _j is the available time of the j-th assembly station in the planning interval, which is from the planning interval The remaining time after deducting equipment failure maintenance time from the total production _time ; a _i ⁺ is the cost of storing and occupying ^working capital for overproduction of one i-th product; cost; b _ij is the preparation cost of the i-th product at the j-th assembly station; c _j is the cost coefficient related to the idle resources of the j-th assembly station; t _ij is the j-th assembly station to assemble the i-th The time required for a product; Δt _ij is the preparation time of the i-th product at the j-th assembly station; (c) ⁺ is max(0, c).

The mixed integer nonlinear programming model of formulas (1)-(3) can be transformed into a mixed integer linear programming model as follows:

$\mathrm{<span\; class="notranslate">\; min</span>}\mathrm{<span\; class="notranslate">\; J</span>}<span\; class="notranslate">\; =</span>$ $\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}$ $<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; a</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{<span\; class="notranslate">\; +</span>}{\mathrm{<span\; class="notranslate">\; \&Delta;</span>}}^{<span\; class="notranslate">\; +</span>}{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; a</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{<span\; class="notranslate">\; -</span>}{\mathrm{<span\; class="notranslate">\; \&Delta;</span>}}^{<span\; class="notranslate">\; -</span>}{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; +</span>\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; \&tau;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; )</span>$

$\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; .</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; .</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; +</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\mathrm{<span\; class="notranslate">\; \&Delta;</span>}{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; \&tau;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; \&beta;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; )</span>$

x _i -Δ ⁺ x _i +Δ ^- x _i =d _i (6)

By _i ≥ x _i (7)

x _i ≥ 0 and an integer, y _i ∈ (0, 1), τ _j ≥ 0, Δ ⁺ x _i ≥ 0, Δ ^- x _i ≥ 0, j = 1, 2, ..., m (8)

In the formula: y _i is a Boolean variable, it is 1 when _xi > 0, otherwise it is 0; B is a large positive number.

At this point, the mixed integer linear programming model of formulas (4)-(8) can be solved by the branch and bound method to obtain a rough solution that minimizes the preparation cost and idle time of each assembly station and satisfies the product demand as much as possible. Production Plan.

3. The integrated optimization method of production planning, scheduling and simulation and its realization:

In order to speed up the solution of the problem, the details of the assembly line are ignored in the model of equations (4)-(8), and the rough production plan is obtained as the initial plan for the iterative solution of the integrated optimization problem of subsequent production planning, scheduling and simulation. On the other hand, synchronous assembly line scheduling considering details is often an unstructured problem, which is difficult to solve analytically. A more feasible way is to use fast scheduling simulation based on variable time flow. The meaning of fast here is that there is no dynamic display of text and graphics, and only the performance index of a given schedule is calculated through fast simulation. As for the iterative selection problem of optimal planning and scheduling, it is solved by three different methods: embedded tabu search simulation method, alternate tabu search simulation method, and serial tabu search simulation method.

3.1 Embedded tabu search simulation method and its realization:

In order to save product assembly preparation time, the same product is assembled in a centralized manner without being divided into multiple assembly tasks, and only occupies one sorting position during scheduling. Referring to formulas (1)-(3), the mathematical model for solving the integrated optimization problem of production planning, scheduling and simulation of mixed-batch assembly line can be described as follows:

$\underset{\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; S</span>}}{\mathrm{<span\; class="notranslate">\; Min</span>}}\mathrm{<span\; class="notranslate">\; G</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; S</span>}}{\mathrm{<span\; class="notranslate">\; Min</span>}}<span\; class="notranslate">\; \{</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; [</span>{\mathrm{<span\; class="notranslate">\; a</span>}}_{\mathrm{<span\; class="notranslate">\; \&mu;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span>}^{<span\; class="notranslate">\; +</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; \&mu;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; \&mu;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span>}{<span\; class="notranslate">\; )</span>}^{<span\; class="notranslate">\; +</span>}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; a</span>}}_{\mathrm{<span\; class="notranslate">\; \&mu;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span>}^{<span\; class="notranslate">\; -</span>}{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; \&mu;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; \&mu;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; )</span>}^{<span\; class="notranslate">\; +</span>}<span\; class="notranslate">\; ]</span>$

$<span\; class="notranslate">\; +</span>\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; \&mu;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; j</span>}}\mathrm{<span\; class="notranslate">\; sgn</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; \&mu;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; \&tau;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; rf</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; )</span>$

$<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; q</span>}\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; [</span><span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; \&beta;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; \&tau;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; m</span>}}\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; \&beta;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; \&tau;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span>{<span\; class="notranslate">\; ]</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; \}</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 9</span>}<span\; class="notranslate">\; )</span>$

$\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; .</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; .</span>$ $\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; \&mu;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; \&mu;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; +</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\mathrm{<span\; class="notranslate">\; \&Delta;</span>}{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; \&mu;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; j</span>}}$ $\mathrm{<span\; class="notranslate">\; sgn</span>}$ $<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; \&mu;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; )</span>$ $<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; \&tau;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}$ $<span\; class="notranslate">\; =</span>$ ${\mathrm{<span\; class="notranslate">\; \&beta;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 10</span>}<span\; class="notranslate">\; )</span>$

x _{μ(S, i)} ≥0 and an integer, τ _j ≥0, j=1, 2,..., m (11)

In the formula: μ(S, i) is n kinds of products or the product category corresponding to the i-th position in the sequence (scheduling) S of n products or some of them passing through the assembly line, if for h≤i≤n there is μ(S,i) = 0, it means that the scheduling S only contains at most h-1 products; b _{μ(S, i)j} is the preparation cost of the μ(S, i)th product at the j assembly station; Δt _{μ( S, i)j} is the preparation time of the μ(S, i)th product at the j assembly station; x=(x _{μ(S, 1)} , x _{μ(S, 2),…} , x _{μ (S, n)} ) ^T is the production plan vector; f(x, S) is the time (schedule span) for the completion of the product assembly task, which is determined by the corresponding planning and scheduling; r is the weight coefficient of task completion time; Assembly station load balancing weight coefficient.

Tabu search is an advanced heuristic method proposed by Glover for obtaining approximate solutions to combinatorial optimization problems. Before applying the tabu search method to solve the integrated optimization problems (9)-(11) of production planning, scheduling and simulation, two concepts, namely adjacent planning and adjacent scheduling, are introduced first. Design plan p ^** =(x ₁ , x ₂ ,...,x _n ) ^T and for some i has τ _j >t _ij >0, for j=1, 2,..., m, then define p=(x ₁ , x ₂ , ..., x _i-1 , x _i+1 , x _i+1 , ..., x _n ) ^T , p=(x ₁ , x ₂ , ..., x _i ±1, ..., x _l  1, ..., x _n ) ^T and p=(x ₁ , x ₂ , ..., x _i-1 , x _i-1 , x _i+1 , ..., x _n ) ^T is an adjacent plan of p ^** . ^Otherwise define p=(x ₁ , x ₂ , . _. . , _xi ± ₁ , . . _. , x _{l 1} , _{. -1} , x _i+1 , ..., x _n ) ^T is the adjacent plan of p ^** . It can be seen that there may be at most n ² +n adjacent plans of p ^** .

For a schedule S ^** , we define a schedule formed by exchanging only two elements in S ^** as a schedule adjacent to S ^** . Without loss of generality, suppose that the initial schedule S ₀ contains three products, that is, S ₀ = {a, b, c}, then by definition, there are three types of schedules adjacent to S ₀ : S ₁ = {b, a , c}, S ₂ ={c,b,a}, S ₃ ={a,c,b}. Note that adjacent schedules are obtained by exchanging only two elements in the original schedule S ₀ . For example, S ₁ is obtained by exchanging only two elements a and b in S ₀ , which is a schedule adjacent to S ₀ ; but {c, a, b} is obtained by exchanging two elements a and c in S ₃ and obtained, cannot be obtained by directly exchanging two elements in S ₀ , so {c, a, b} is not adjacent to S ₀ . Generally, for a schedule S ^** containing n products, there are n(n-1)/2 adjacent schedules.

At present, the tabu search method is mainly used in flow shop scheduling, job shop scheduling and manufacturing unit formation, but its application in production planning and scheduling of mixed batch assembly lines is very rare. What the present invention is to solve is the integrated optimization problem of planning, scheduling and simulation, so a new embedded tabu search simulation method needs to be proposed to solve it. The basic idea is to use the rough production plan as the initial solution and use the simplified tabu search simulation method to find a feasible plan and schedule, then use the tabu search to find the best plan at the planning layer, and use Another tabu search looks for the scheduling with the best performance index after fast simulation calculation, until the production planning and scheduling are optimized at the same time. Because a tabu search nests another tabu search and uses fast simulation to calculate the scheduling index, it is called the embedded tabu search simulation method.

Algorithm 1: Embedded Tabu Search Simulation Method for Integrated Optimization Problems (9)-(11) of Production Planning, Scheduling and Simulation

Step 1Initialization

(1) Read various data and parameters in formulas (9)-(10).

(2) Read the algorithm parameters, including the length PT_size of the production plan taboo table, the given number of planned moves PM-max, the length of the scheduling taboo table ST_size and the given number of scheduled moves SM_max.

(3) Set G_best=M_big, PM_ctr=0, PT_list={φ}, P_best=φ, S_best={φ}.

Step 2 Search for initial feasible plan and scheduling

(1) Set the initial production plan p ₀ =x.

(2) Set the current plan p=p ₀ , and call Algorithm 2 to search for a feasible schedule for a given plan p.

(3) If SC_flag=1 and G(p, S ^*** )<G_best, then set p ^** ←p, P_best←p, S_best←S ^*** , G_best←G(p, S ^*** ) . Then go to Step 3.

(4) Generate an adjacent plan p of p ₀ and set p ₀ =p. Then turn to Step 2 (2).

Step 3 Search for the best plan and schedule

(1) Generate a set of all possible plans adjacent to p ^** , and set G(p ^* , S ^*** )=M_big.

(2) For a plan p in this set, if p is not in PT_list, call Algorithm 2 to search for the best schedule for a given plan p, and update the best plan in the current adjacent set: p ^* ←p, G(p ^* , S ^*** )←G(p,S ^*** ), if SC_flag=1 and G(p,S ^*** )<G(p ^* ,S ^*** ); otherwise discard p . If the number of plans in the plan taboo table PT_list is less than PT_size, add p to the top of PT_list. Repeat this until all adjacent plans of p ^** are completed.

(3) Make a planned move: set p ^** ←p ^* , G(p ^** , S ^*** )←G(p ^* , S ^*** ) and if p ^** is not in the PT_list, set p ^{* *} Add to the top of PT_list; if the number of plans in PT_list>PT_size, delete the oldest plan from the bottom of PT_list.

(4) If the plan is improved, that is, if G(p ^** , S ^*** )<G_best, update the best solution: P_best←p ^** , S_best←S ^*** , G_best←G(p ^** , S ^*** ).

(5) Update the number of planned moves made so far: PM_ctr←PM_ctr+1. If PM_ctr>PM_max, stop iteration and go to Step 4, otherwise go to (1) of Step 3.

Step 4 output result

Output P_best, S_best and G_best.

Here: M_big is a very large number; SC_flag is a sign of whether there is a scheduling that satisfies constraints (10)-(11) for a given plan p, SC_flag=1 means that it exists, and SC_flag=0 means that it does not exist; p ^* is in The best plan in the current adjacent planning set; p ^** is the best plan in the immediately preceding adjacent planning set: P_best is the best production plan found so far; S ^*** is the best scheduling of the corresponding plan; S_best is the best scheduling found for the best production plan found so far; G(p, S) is the performance index corresponding to the production plan p and scheduling S: G_best is the best achieved so far index.

Algorithm 2: Scheduling Optimization Based on Tabu Search

Step 1Initialization

Set SM_ctr=0, scheduling taboo table ST_list={φ}.

Step 2 Find the initial schedule

(1) For a given current production plan p, determine the initial schedule S ₀ according to priority rules such as the earliest delivery date and the smallest batch, and set S ^** = S ₀ , S ^*** = S ₀ , SC_flag = 0 .

(2) Calculate the performance index G(p, S ₀ ) corresponding to p and S ₀ through fast scheduling simulation, and set G(p, S ^*** )=G(p, S ₀ ).

If S ₀ is feasible (ie satisfying constraints (10)-(11)), set SC_flag=1.

Step 3 Schedule search

(1) Generate all possible scheduling sets adjacent to the best scheduling S ^** in the immediately preceding adjacent scheduling set, and set G(p, S ^* )=M_big.

(2) For a schedule S in this set, if S is not in ST_list, calculate the scheduling performance index G(p, S) through fast scheduling simulation, and update the best schedule in the current adjacent set: S ^* ← S , G(p, S ^* ) ← G(p, S), SC_flag=1 if S is feasible and G(p, S)<G(p, S ^* ); S ^* ←S, G(p, S ^* ) ←G(p,S) if neither S nor S ^* is feasible and G(p,S)<G(p,S ^* ); otherwise discard S. Repeat this until all adjacent scheduling of S ^** is done.

(3) Make a scheduling move; set S ^** ←S ^* , G(p, S ^** )←G(p, S ^* ), and add S ^** to the top of ST_list;

If the number of schedules in ST_list > ST_size, delete the oldest schedule from the bottom of ST_list.

(4) If the scheduling is improved, that is, S ^** is feasible and G(p, S ^** ) < G(p, S ^*** ) or neither S ^** nor S ^*** is feasible and G(p, S ** ^** )<G(p, S ^*** ), update the best solution: S ^*** ← S ^** , G(p, S ^*** ) ← G(p, S ^** ).

(5) Update the number of scheduling moves made on the current plan: SM_ctr←SM_ctr+1. If SM_ctr>SM_max, stop iteration and go to Step 4; otherwise go to (1) of Step 3.

Step 4Return

The x in Algorithm 1 Step 2 is the rough production plan obtained by solving equations (4)-(8) and is used as the initial solution of the algorithm to speed up the solution of the problem, because the rough production plan is often better than the randomly selected initial solution It is closer to the true solution of equations (9)-(11). However, since formulas (4)-(8) ignore details such as assembly line scheduling, the rough production plan thus obtained is often infeasible for formulas (9)-(11). In addition, the effective way to evolve from a rough production plan to a feasible plan is undoubtedly to reduce the load on the assembly line, so the adjacent plan in Algorithm 1 Step 2 can only be defined as p=(x ₁ , x ₂ ,…,xi _-1 , x _i-1 , x _i+1 ,…, x _n ) ^T to speed up the speed of obtaining the initial feasible solution.

If the mixed-batch assembly line has random characteristics (such as equipment failure, assembly time changes, etc.), the integrated optimization problem can be solved by the Monte Carlo operation of Algorithm 1. The specific method is: (1) Before each Monte Carlo run, calculate the respective sample values according to the distribution function of each random variable and replace the corresponding values in formulas (9)-(10) with these sample values, and then call the algorithm 1; (2) In the first Monte Carlo run, x in Algorithm 1 Step 2 is the rough production plan, but in the second and subsequent Monte Carlo runs, x is the value after the previous Monte Carlo run The best production plan obtained to speed up its solution. Because although the sample value of the current Monte Carlo operation is likely to be different from that of the previous Monte Carlo operation, the best production plan of the previous time is often closer to the optimal solution than the rough production plan; (3) all Monte Carlo After running Luo, it is necessary to calculate the average value of all results except the best schedule, and use the rounded average value of the best plan and the average value of random parameters as input to call Algorithm 2 again to obtain the corresponding best schedule, and finally Together with the rounded average of the best plan and the average of other results, it is the solution of the integrated optimization problem of production planning and scheduling of mixed batch assembly line with stochastic characteristics.

The program flowcharts of Algorithm 1 and Algorithm 2 are shown in Figures 4 and 5, respectively. Thus, according to Algorithm 1 and Algorithm 2 and their program flow charts, the inventor has implemented the embedded tabu search simulation method for solving the above-mentioned mixed-batch assembly line production planning and scheduling integration optimization problem by using Microsoft Visual C ⁺⁺ 5.0 programming.

The computational complexity of Algorithm 1 is o(0.5n ² (n ² −1)×SM_max×PM_max) simulations. If n is relatively large, using Algorithm 1 to solve equations (9)-(11) will take too much time to obtain the optimal solution within an acceptable time. For this reason, we will propose another algorithm for solving equations (9)-(11), that is, the alternate tabu search simulation method.

3.2 Alternate tabu search simulation method and its realization:

The basic idea of the alternate tabu search simulation method is: (1) use the rough production plan as the initial production plan and use the simplified tabu search simulation method to find a feasible plan and schedule; (2) given the schedule, use the tabu search to find Calculate the plan with the best performance index; (3) Given the plan in turn, use another tabu search to find the schedule with the best performance index after fast simulation calculation; (4) Use (2) and (3) alternately step until the best plan and schedule is found. Since two tabu searches are alternately used for planning and scheduling respectively and their performance indicators are calculated by fast simulation, it is called alternate tabu search simulation method.

Alternative Tabu Search Simulation Method for Integrated Optimization Problems of Algorithm 3 Production Planning, Scheduling and Simulation

Step 1Initialization

(1) Read various data and parameters in formulas (9)-(10).

(2) Read the algorithm parameters, including the length PT_size of the production plan taboo table, the given number of planned moves PM-max, the length of the scheduling taboo table ST_size and the given number of scheduled moves SM_max.

(3) Set G_best=M_big, PM_ctr=0, PT_list={φ}, P_best=φ, S_best={φ}.

Step 2 Search for initial feasible plan and scheduling

(1) Set the initial production plan p ₀ =x.

(2) Set the current plan p=p ₀ , and call Algorithm 2 to search for a feasible schedule for a given plan p.

(3) If SC_flag=1 and G(p, S ^*** )<G_best, then set p ^** ←p, P_best←p, S_best←S ^*** , G_best←G(p, S ^*** ) . Then go to Step 3.

(4) Generate an adjacent plan p of p ₀ and set p ₀ =p. Then turn to Step 2 (2).

Step 3 Search for the best plan and schedule

(1) Generate a set of all possible plans adjacent to p ^** , and set G(p ^* , S ^*** )=M_big.

(2) For a plan p in the set, if p is not in the PT_list, calculate the performance index G(p, S ^*** ) corresponding to p and S ^*** through fast scheduling simulation, and update the current adjacent set The best plan for : p ^* ← p, G(p ^* , S ^*** ) ← G(p, S ^*** ), if SC_flag=1 and G(p, S ^*** )<G(p ^* , S ^*** ); otherwise discard p. If the number of plans in the plan taboo table PT_list is less than PT_size, add p to the top of PT_list. Repeat this until all adjacent plans of p ^** are completed.

(3) Algorithm 2 is invoked to search for the best schedule S ^*** for a given p ^* .

(4) Make a planned move: set p ^** ←p ^* , G(p ^** , S ^*** )←G(p ^* , S ^*** ) and if p ^** is not in the PT_list, set p ^{* *} Add to the top of PT_list; if the number of plans in PT_list>PT_size, delete the oldest plan from the bottom of PT_list.

(5) If the plan is improved, that is, if G(p ^** , S ^*** )<G_best, update the best solution: P_best←p ^** , S_best←S ^*** , G_best←G(p ^** , S ^*** ).

(6) Update the number of planned moves made so far: PM_ctr←PM_ctr+1. If PM_ctr>PM_max, stop iteration and go to Step 4, otherwise go to (1) of Step 3.

Step 4 output result

Output P_best, S_best and G_best.

The program flow chart of Algorithm 3 is shown in Figure 6. In this way, according to Algorithm 3 and its program flow chart, the inventor has implemented the alternate tabu search simulation method for solving the above-mentioned mixed-batch assembly line production planning and scheduling integration optimization problem by using MicrosoftVisual C ⁺⁺ 5.0 programming.

The computational complexity of Algorithm 3 is o((n ² +n+0.5n(n-1)SM_max)PM_max) simulations. If n is large enough, the complexity of Algorithm 1 is O(n ⁴ ), while Algorithm 3 is O(n ² ). So Algorithm 3 is much faster than Algorithm 1, but the latter tends to get better solutions than the former. If n is very large, even Algorithm 3 cannot achieve optimal or suboptimal solutions in acceptable time. To this end, we will propose a serial tabu search simulation method to solve equations (9)-(11).

3.3 Serial tabu search simulation method and its realization

Undoubtedly, an effective way to speed up the solution process is to reduce the computational complexity of the algorithm, that is, to reduce the total number of simulations done to obtain the best schedule. For this reason, the basic idea of the serial tabu search simulation method is: (1) use the rough production plan as the initial plan and use the rule scheduling simulation method to find a feasible plan and schedule; (2) start from the feasible plan, use the tabu search to find the Regular scheduling and the plan with the best performance index calculated by fast simulation; (3) For the best plan, another tabu search is used to find the schedule with the best performance index calculated by fast simulation. Because tabu search is used sequentially for planning and scheduling and its performance index is calculated by fast simulation, it is called serial tabu search simulation method.

Algorithm 4 A serial tabu search simulation method for integrated optimization problems of production planning, scheduling and simulation

Step 1Initialization

(1) Read various data and parameters in formulas (9)-(10).

(2) Read the algorithm parameters, including the length PT_size of the production plan taboo table, the given number of planned moves PM-max, the length of the scheduling taboo table ST_size and the given number of scheduled moves SM_max.

(3) Set G_best=M_big, PM_ctr=0, PT_list={φ}, P_best=φ, S_best={φ}.

Step 2Search for feasible plans

(1) Set the initial production plan p ₀ =x.

(2) Set the current plan p=p ₀ , and call Algorithm 5 to determine the schedule corresponding to p.

(3) If SC_flag=1 and G(p, S)<G_best, set p ^** ←p, P_best←p, S_best←S, G_best←G(p, S). Then go to Step 3.

(4) Generate an adjacent plan p of p ₀ and set p ₀ =p. Then go to (2) of Step2.

Step 3 Search for the best plan

(1) Generate a set of all possible plans adjacent to p ^** , and set G(p ^* , S)=M_big.

(2) For a plan p in this set, if p is not in the PT_list, call Algorithm 5 to determine the schedule corresponding to p, and update the best plan in the current adjacent set: P ^* ← p, G(p ^* ,S)←G(p,S), if SC_flag=1 and G(p,S)<G(p ^* ,S); otherwise p is discarded. If the number of plans in the plan taboo table PT_list is less than PT_size, add p to the top of PT_list. Repeat this until all adjacent plans of p ^** are completed.

(3) Make a planned move: set p ^** ←p ^* , G(p ^** , S)←G(p ^* , S) and add p ^** to the top of PT_list if p ^** is not in PT_list ; If the number of plans in PT_list > PT_size, delete the oldest plan from the bottom of PT_list.

(4) If the plan is improved, that is, if G(p ^** , S) < G_best, update the best solution: P_best←p ^** , S_best←S, G_best←G(p ^** , S).

(5) Update the number of planned moves made so far: PM_ctr←PM_ctr+1. If PM_ctr>PM_max, go to Step 4, otherwise go to (1) of Step 3.

Step 4 Search for the best schedule

(1) Set p=P_best, and call Algorithm 2 to search for the best schedule corresponding to p.

(2) If the scheduling is improved, that is, G(p, S ^*** )<G_best, update the best solution: S_best←S ^*** , G_best←G(p, S ^*** ).

Step 5 output result

Output P_best, S_best and G_best.

Here, S is a schedule determined by Algorithm 5.

Algorithm 5 corresponds to the scheduling determination algorithm for a given plan

Step 1 Determine the schedule

(1) For a given plan p, determine the schedule S according to priority rules such as the earliest delivery date and the smallest batch.

(2) Calculate G(p, S) corresponding to p and S through fast scheduling simulation.

(3) If S is not feasible, set SC_flag=0, otherwise set SC_flag=1.

Step 2Return

The computational complexity of Algorithm 4 is o((n ² +n)PM_max+0.5n(n-1)SM_max) simulations. If n is large enough, the complexity of Algorithm 4 is O(n ² ) same as Algorithm 3. However, using Algorithm 4 to search for the best plan and schedule from the initial feasible plan requires less [1+0.5n(n-1)SM_max](PM_max-1) simulations than using Algorithm 3. Therefore, Algorithm 4 is faster than Algorithm 3, but the latter tends to obtain better solutions than the former.

The program flowcharts of Algorithm 4 and Algorithm 5 are shown in Figures 7 and 8, respectively. In this way, according to Algorithm 4 and Algorithm 5 and their program flow charts, the inventor has implemented a serial tabu search simulation method for solving the above-mentioned integrated optimization problem of production planning and scheduling of the mixed-batch assembly line by using Microsoft Visual C ⁺⁺ 5.0 programming.

In the integrated optimization of production planning, scheduling and simulation, the function of planning is to determine the assembly batch of each product, the function of scheduling is to determine the order in which each product will be assembled online, and the function of simulation is to calculate the performance of a given schedule index.

4. Fast simulation method of production scheduling and its realization

The above-mentioned embedded tabu search simulation method, alternating tabu search simulation method, and the fast scheduling simulation of the serial tabu search simulation method are all realized by using the extended random high-level judgment Petri net to establish a scheduling simulation model and object-oriented technology, and use the available Vary the flow of time to control the progress of the simulation. The meaning of fast here is that there is no dynamic display of text and graphics, and only the performance index of a given schedule is calculated through fast simulation.

4.1 Extended Stochastic Advanced Judgment Petri Net

Due to the rapidly changing market demand, it is necessary to timely complete orders with changing varieties and batches on a mixed-batch assembly line, so how to compile and optimize the production plan and scheduling of the mixed-batch assembly line is very important. In order to obtain integrated optimized planning and scheduling, it is necessary to calculate the performance index of each scheduling of each feasible plan. However, due to the complexity of mixed-batch assembly line scheduling, it is difficult to use analytical methods to consider various factors of the assembly line. A more feasible method is simulation. Therefore, it is necessary to establish a simulation model, that is, a modeling tool that can describe the structure and operation status of the mixed-batch assembly line is needed. The present invention adopts the Extended Random Advanced Judgment Petri Net (ESHLEP-N) proposed by the inventor and successfully applied in flexible manufacturing system (FMS) modeling, scheduling and simulation to model the mixed batch assembly line to solve the problem of mixed batch An assembly line scheduling simulation problem.

The main advantages of ESHLEP-N are: (1) In order to make the tokens in the warehouse not only convenient for user observation and performance analysis, but also convenient for FMS scheduling simulation, double tokens and double identification are defined in ESHLEP-N; (2) Introduce scheduling and other rules into ESHLEP-N to improve its reasoning and decision-making ability. However, the original definition of ESHLEP-N is for FMS modeling, so it needs to be modified and perfected to make it suitable for the modeling of mixed batch assembly line. The modified Petri net is still called ESHLEP-N, and its definition is as follows:

Definition 1 ESHLEP-N can be defined as a 16-tuple:

ESHLEP-N={P, T(R), F, A _p , C, I ₋ , I ₊ , I _a , I _s , I _r , DI _a , DI _s , DI _r , K, M ₀ , CM ₀ }in:

P={P _g , R}={p ₁ , p ₂ ,..., p _h , r ₁ , r ₂ ,..., r _k } is a finite place set, p _i ∈ P _g , r _j ∈ R, _Pg is the general place set, and R is the decision point set.

T(R)={t ₁ (r ₁ ), t ₂ (r ₂ ),...,t _k (r _k )} is a finite transition set T(R)∩P=φ, φ is an empty set.

FP×T(R)∪T(R)×P is a flow relation.

A _p : P _g →A _p (P _g ), R→A _p (R). A _p (P _g ) is a set of parameter tables on P _g . A _p (R)=S={S ₁ , S ₂ , . . . , S _k } represents a set of rules (decision logic) on R. S _j is the rule set that controls the enabling and triggering of transition t _j (r _j ). A _p (P _g )∪A _p (R) is the token set of ESHLEP-N.

C: A _p (P)∪T(R)→The power set of known colors, such that p∈P, C(A _p (p)) is a set of all possible token colors on p: t( r)∈T(R), C(t(r)) is a set of all possible colors on t(r).

I _- is a negative function such that

(p, t(r))∈P _g ×T(R): I _- (p, t(r))∈[C(t(r)) _MS →C(A _p (p)) _MS ] _L And the sufficient condition for I _- (p, t(r)) = 0 is $(p,t\left(r\right))\&NotElement;f.$ Here, C(...) _MS is the multiset, C(A _p (p)) _MS is the set of colored tokens on p, [...] _L is the set of linear functions.

I ₊ is a positive function such that

(t(r), p)∈T(R)×P _g : I ₊ (p, t(r))∈[C(t(r)) _MS →C(A _p (p)) _MS ] _L And the sufficient condition for I ₊ (p, t(r))=O is $(t\left(r\right),p)\&NotElement;f.$

I _a : A _p (P _g )→φ∪R _a ⁺ , R _a ⁺ is a non-negative real number set, which represents the assembly time set of all products at each assembly station. If r∈R _a ⁺ , then r represents the assembly time of a certain product at a certain assembly station.

I _s : A _p (P _g )→φ∪R _s ⁺ . R _s ⁺ is a set of non-negative real numbers, representing the set of trouble-free service time of service desks (assembly stations, assembly robots, equipment, tools, etc.).

I _r : A _p (P _g )→φ∪R _r ⁺ . R _r ⁺ is a non-negative real number set, which represents the maintenance time set of the service desk.

DI _a : A _p (P _g )→φ∪{N(μ ₁₁ , σ ₁₁ ² ), N(μ ₁₂ , σ ₁₂ ² ),..., N(μ ₂₁ , σ ₂₁ ² ),...}. Among them, N(μ _ij , σ _ij ² ) is the normal distribution function obeyed by the assembly time of product i at the jth assembly station, μ _ij is the mean value, and σ _ij ² is the variance.

DI _s : A _p (P _g )→φ∪{exp(λ ₁ ), exp(λ ₂ ), . . . , exp(λ _m )}. Among them, exp(λ _j ) is the negative exponential distribution function obeyed by the failure interval of service station j, and λ _j is the failure rate.

DI _r : A _p (P _g )→φ∪{exp(θ ₁ ), exp(θ ₂ ), . . . , exp(θ _m )}. Among them, exp(θ _j ) is the negative exponential distribution function that the maintenance time of service station j obeys, and θ _j is the maintenance rate.

K: P _g →N ⁺ ∪{ω}, where N ⁺ is a positive integer set, ω represents positive infinity, and K is a positive capacity function. p∈P _g , K(p) is a subset of N ⁺ ∪{ω}, each element of which represents an upper bound on the number of corresponding colored tokens in p. Obviously, K(p) has the same dimension as C(A _p (p)). If an element of K(p) is ω, the number of colored tokens corresponding to this element in p is unlimited.

M ₀ is the initial identity formed by the initial token of ESHLEP-N, satisfying p∈P: _{M 0} ∈A _p (p).

CM ₀ is the initial colored identity of ESHLEP-N for users to observe the distribution of colored tokens and performance statistics, satisfying

p∈P _g : M ₀ (p)∈A _p (p)→CM ₀ (p)∈C(A _p (p)) _MS

It should be pointed out that the trigger of a transition is to take some tokens and the corresponding colored tokens of the same amount from a subset of places according to the rules in the decision point related to the transition, and add them to other places Subset. Whenever a transition has tokens in a certain subset of input places and a certain subset of output places that match certain rules in its decision points, the transition is enabled. This means: (1) These input pools hold enough suitable tokens; (2) The upper bound of the number of certain tokens (colored tokens that can be mapped to the same color) in these output pools will not be due to The increase of such tokens after the transition is triggered is exceeded; (3) These tokens should stay in the input warehouse for a sufficient time. Transitions are triggered as soon as they are enabled.

4.2 Modeling of mixed batch assembly line based on ESHLEP-N

A mixed batch assembly line has a total of m (=33) assembly stations. Since assembling a product requires many assemblies (parts, components, components, etc.), in order to simplify modeling, we use the assembly time of the product at each assembly station to represent the assembly process of each assembly station, instead of Each specific assembly is modeled. Since the assembly time of products at each assembly station can vary, the assembly time for individual products even at some assembly stations can be zero, that is, only pass through these assembly stations without specific assembly. The products pass through each assembly station in turn according to the predetermined schedule (sequence), and after the previous station is assembled, they are sent to the next station to continue assembly. Since the product assembly is completed by workers, if the assembly task at the previous station has been completed and the assembly task at this station has also been completed, the worker can freely cross the interval limit of the assembly station and directly assemble the next product. Similarly, if the product at a certain station has not been assembled, and the product has moved beyond the boundary of the station along with the assembly line, the workers at this station are allowed to postpone the task to the next station to continue to complete, Thus logically forming a virtual buffer. However, it should be noted that workers cannot cross stations indefinitely, and failures may occur at various assembly stations. Each station can only hold at most one product at any time. The total number of products on the line is at most equal to the number m of stations on the line at any time, that is, if there is one product at each station at a certain moment, the only way to wait is for a product to be installed at the last station m and placed. A product to be loaded can be put online at station 1 only after it is online. The synchronous moving speed of the assembly line is variable, determined by the assembly speed of the last station when there is no full buffer on the line, and determined by the assembly speed of the bottleneck station when there is a full buffer. Since it may take different time for each station to assemble different products, the bottleneck station may be transferred when the product type and mixed batch change.

According to the previous description of the mixed batch assembly line and the definition of ESHLEP-N, we first determine the number, location and meaning of ESHLEP-N general warehouses. Then draw transitions, decision points, and arcs between nodes in sequence. Finally, the ESHLEP-N graphical model of the mixed-batch assembly line shown in Figure 9 is obtained. In Figure 9, the meanings of common places, decision points and transitions are explained as follows:

p ₁ is the "assembly station free" place. When place _p1 only holds colored tokens, the corresponding assembly station is idle.

p ₂ is the storehouse of "to-be-loaded goods storehouse". When the warehouse p ₂ holds colored tokens, there are goods waiting to be assembled in the warehouse.

p ₃ is the "queuing" place. When the place p ₃ holds a colored token, there are corresponding products waiting to be assembled in the buffer of the corresponding assembly station.

p ₄ is the "assembly" place. When the warehouse p ₄ holds a colored token, the corresponding assembly station is assembling (including preparing) the corresponding product.

p ₅ is the "failure" place. When the place p ₅ holds a colored token, the corresponding assembly station is in a fault state and is being repaired.

p ₆ is the "finished product warehouse" warehouse. When the warehouse p ₆ holds colored tokens, there are assembled finished products in the finished product warehouse.

r _1-5 are decision points. These nodes specify where in the ESHLEP-N diagram decisions are to be introduced. The rule set S _j in the decision point r _j (j=1-5) is the rule set enabling and triggering the control transition t _j (r _j ).

t ₁ is t ₁ (r ₁ ), which is the change of "the assembly line of the goods to be loaded". Its triggering indicates that there is a product to be loaded in the warehouse to enter the buffer zone of the first station to wait for assembly.

t ₂ is t ₂ (r ₂ ), which is the "start assembly" transition. Its trigger means that the corresponding assembly station starts to carry out the specified assembly (including preparation) of the corresponding product.

t ₃ is t ₃ (r ₃ ), which is the "complete assembly" transition. Its trigger means that the corresponding assembly station completes the specified assembly of the corresponding product.

t ₄ is t ₄ (r ₄ ), which is the "failure occurs" transition. Its triggering indicates that the corresponding station in the assembly state or idle state has failed.

t ₅ is t ₅ (r ₅ ), which is the "failure over" transition. Its triggering means that the corresponding assembly station or idle station ends the fault state.

In order to make ESHLEP-N better reflect the characteristics of assembly completed by workers, the following is a necessary description of the above ESHLEP-N diagram model:

(1) p ₃ is the "queuing" warehouse. In order to realize the cross-station assembly of products by workers and not make the number of crossed stations exceed a certain range, we set the maximum number of queues allowed by each station in the database, that is Virtual buffer for each station. If the number of workers at a certain station moving forward or backward exceeds this limit, it means that the assembly line is blocked at this moment.

(2) p ₂ is the storehouse of "stock to be loaded". In a mixed-batch assembly line, the on-line of the goods to be loaded is controlled by the off-line of the finished products. It is reflected in the program that after each finished product leaves the last station of the assembly line, it is required to add a product to be loaded in the first station queue in the "queuing" warehouse, which triggers the _t1 transition. Therefore, after all the items to be installed in the plan are online, in order to ensure that all online products can complete the rest of the assembly, virtual items to be installed can be added to the "warehouse of items to be installed" to ensure the smooth progress of the simulation .

Since the ESHLEP-N diagram is user-oriented and mainly used to analyze the performance of the mixed-batch assembly line, only the colored tokens are shown in the common place in Fig. 9. This is because representing the states of the ESHLEP-N graph model by colored tokens can reduce the number of states. For example, the colored token 5w of place p ₁ in Fig. 9 indicates that there are 5 assembly stations in an idle state. However, these five assembly stations can be any one of the m (=33) assembly stations, that is, the corresponding $C_m^5=237336$ A combination of workstations. If each assembly station is represented by a token, then these 5 colored tokens correspond to 237336 kinds of token combinations (that is, the number of 5 combinations taken from 33 different tokens). Although not shown in Figure 9, the tokens in the common repository do exist, only implicitly. When a colored token moves, the user should imagine a token moving with it. In this way, the distribution of corresponding tokens can be roughly determined based on the distribution of colored tokens in common exchanges. The issues related to colored tokens are mainly discussed below.

According to the definition of ESHLEP-N in Definition 1, if w represents an assembly station, b represents a product (to-be-assembled product, ready-assembled product or finished product), and q _i (i=1, 2, ..., m) represents a waiting The product assembled at the i-th station, <·> represents the composite color, and the color sets of all possible colored tokens in the common warehouse in Figure 9 can be expressed as follows:

C(A _p (p ₁ ))={w}, which means that there are workstations in an idle state.

C(A _p (p ₂ ))={b}. Indicates that there is an item to be loaded in the item to be loaded library.

C(A _p (p ₃ ))={q ₁ , q ₂ ,...,q _m }, which means that there are products waiting for assembly at the i-th (i=1,2,...,m) station.

C(A _p (p ₄ ))={<w, b>}, indicating that there are products being assembled.

C(A _p (p ₅ ))={w,<w,b>}, where w indicates that there is a fault in an idle station. <w, b> indicates that a station in assembly state has failed.

c(A _p (p ₆ ))={b}, which means that there are assembled finished products in the finished product warehouse.

Tokens in a decision point are special in that they can be reused but cannot be moved to other places, that is, the triggering of a transition related to a decision point will cause the token to move out of the decision point and move into the decision point again .

The transition trigger of ESHLEP-N is different from ordinary Petri nets. It does not remove tokens from all input places and add them to all output places, but according to the rules in the decision point, some or all of the input Move mountain tokens and corresponding colored tokens in the warehouse, adding them to some and all output warehouses. For example, one possible colored token move when transition _t2 fires is:

Remove a colored token w, q _j , (j=1, 2, ..., m) from input places p ₁ , p ₃ respectively, combine them into a composite colored token <w, b>, add it to Output place p ₄ .

Once the movement relationship between all transition triggers and their corresponding colored tokens in Figure 9 is determined, the dynamic process of the model can be determined accordingly.

All possible occurrences of all transitions in Figure 9 are as follows:

C(t ₁ )={q ₁ ), C(t ₂ )={<w,b>},

C(t ₃ )={w,b,q ₂ ,q ₃ ,...,q _m }, C(t ₄ )={w,<w,b>}

C(t ₅ )={w,<w,b>}

The following is a dynamic description with reference to the ESHLEP-N graph model in Fig. 9 . set up:

(q ₁ ←b) represents a linear mapping, that is, mapping from b to q ₁ , which represents the queue of items to be loaded to station 1.

p _r 1, p _r 2 are projections, that is, the mapping of the first color or the second color in the composite color <·>.

ID is an identity map.

X(t ₂ ) represents the movement of colored tokens caused by the triggering of transition t ₂ , and satisfies

X(t ₂ )∈C(t ₂ ) _MS

In this way, the dynamic description of the ESHLEP-N model is as follows:

1) Initial state

The initial colored logo in the general storehouse in Figure 9 can be expressed as follows:

CM ₀ (p ₁ )=5w, indicating that there are 5 assembly stations free.

CM ₀ (p ₂ )=10b, which means that there are 10 items to be loaded in the item library.

CM ₀ (p ₃ )＝q ₁ +q ₅ +2q ₁₀ +2q ₂₅ , which means that No. 1 and No. 5 stations each have one product, No. 10 and No. 25 stations each have two products waiting to be assembled, and the other stations have no Product awaits assembly.

CM ₀ (p ₄ )=26<w, b>, indicating that 26 stations are assembling products.

CM ₀ (P ₅ )=w+<w, b>, which means that each of the idle and assembly stations fails.

CM ₀ (p ₆ )=20b, which means that there are 20 assembled finished products in the finished product warehouse.

If expressed as a vector then

CM ₀ =(5w, 10b, q ₁ +q ₅ +2q ₁₀ +2q ₂₅ , 26<w,b>,w+<w,b>, 20b)

2) Let one of the idle stations in CM ₀ (p ₁ )=5w be number 1. In this way, according to the rules in the decision point r ₂ , t ₂ can be triggered, that is, one colored token is removed from p ₁ and p ₃ , and combined into a composite colored token <w, b> moved into p ₄ ( Assume no fault occurs at this time).

Let I _- (p ₁ , t ₂ )=p _r 1 again;

$\mathrm{<span\; class="notranslate">\; I</span>}<span\; class="notranslate">\; \_</span><span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span><span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="1"\; label="q"\; filenames="A20031010600600282.png"\; state="\{\{state\}\}">q</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}\stackrel{\mathrm{<span\; class="notranslate">\; L</span>}}{<span\; class="notranslate">\; \&LeftArrow;</span>}\mathrm{<span\; class="notranslate">\; b</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; P</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ;</span>$

I ₊ (p ₄ , t ₂ ) = ID;

X(t ₂ )=<w,b>

so:

CM ₁ (p ₁ )=CM ₀ (p ₁ )-I ₋ (p ₁ , t ₂ )X(t ₂ )=5w-(P _r 1 )<w,b>=5w-w=4w

$\mathrm{<span\; class="notranslate">\; C</span>}{\mathrm{<span\; class="notranslate">\; m</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; C</span>}{\mathrm{<span\; class="notranslate">\; m</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; I</span>}<span\; class="notranslate">\; \_</span><span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; )</span>$

$<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="1"\; label="q"\; filenames="A20031010600600282.png"\; state="\{\{state\}\}">q</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; 5</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 2</span>}{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; 10</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 2</span>}{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; 25</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="1"\; label="q"\; filenames="A20031010600600282.png"\; state="\{\{state\}\}">q</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}\stackrel{\mathrm{<span\; class="notranslate">\; L</span>}}{<span\; class="notranslate">\; \&LeftArrow;</span>}\mathrm{<span\; class="notranslate">\; b</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; r</span>}}\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; <</span>\mathrm{<span\; class="notranslate">\; w</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; b</span>}<span\; class="notranslate">\; ></span>$

$<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="1"\; label="q"\; filenames="A20031010600600282.png"\; state="\{\{state\}\}">q</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; 5</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 2</span>}{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; 10</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 2</span>}{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; 25</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="1"\; label="q"\; filenames="A20031010600600282.png"\; state="\{\{state\}\}">q</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; 5</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 2</span>}{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; 10</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 2</span>}{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; 25</span>}}$

CM ₁ (p ₄ )=CM ₀ (p ₄ )+I ₊ (p ₄ ,t ₂ )<w,b>=26<w,b>+<w,b>

= 27<w, b>

That is, CM ₁ =(4w, 10b, q ₅ +2q ₁₀ +2q ₂₅ , 27<w, b>, w+<w, b>, 20b)

3) Set station 33 to complete the assembly task, then transition t ₃ is triggered according to the rule in decision point r ₃ . To this end, a compound colored token <w, b> is moved out of p ₄ and decomposed into colored tokens w and b into p ₁ and p ₆ respectively. At this point, the colored logo becomes:

CM ₂ =(5w, 10b, q ₅ +2q ₁₀ +2q ₂₅ , 26<w,b>,w+<w,b>, 21b).

4) The same is true for other transitions, as long as the tokens and colored tokens in its input/output stores match the rules in the corresponding decision points, it will be triggered. Therefore, although the mixed-batch assembly line is complicated, its dynamic process can be clearly described by ESHLEP-N diagram.

4.3 Object-Oriented Implementation of ESHLEP-N Model for Mixed Batch Assembly Line

The term object-oriented (Object-Oriented) comes from the Simula language introduced in the 1960s. The basic idea of object-oriented technology is to construct objects and combine data structures and behaviors into a single entity through modeling methods. It organizes models around objective and realistic things, extracts the common methods and behaviors of certain objects and models, and encapsulates them to form classes. The objects in the class have the same attributes and behavior patterns, and then the objects are generated by the instantiation of the class. This set of objects also has general relationships, general behavior and general semantics. Of course, objects of different classes may also have the same attribute values and relationships.

The object-oriented method emphasizes that object properties can only be changed by the behavior of the object itself, and that objects interact through message passing. The object class can be refined through the inheritance mechanism, and the concept of polymorphism of the object can be induced by resetting the behavior of the object. . Encapsulation, inheritance, and polymorphism are important features of object-oriented.

The present invention adopts Visual C ⁺⁺ 5.0 of Microsoft Corporation as a development tool to realize the ESHELP-N model of the mixed-batch assembly line. Since Visual C ⁺⁺ 5.0 was born, it has been the most important application development system under the Windows environment. It provides a convenient classwizard to enable developers to easily handle their own designed classes, and provides packaged MFC to enable developers to easily implement various operations. In the present invention, its classwizard is also mainly used to design classes for realizing simulation, and MFC is used to realize extraction of basic simulation data in the database, construction of transition list and other operations. The object-oriented implementation of the ESHELP-N model is discussed below.

4.3.1 Place and Transition Representation

In the implementation process of ESHLEP-N, we use the basic class to realize the token in the general storehouse, and use the attributes in it to indicate which storehouse the specific token is in. For this reason, in Microsoft Visual C ⁺⁺ 5.0, Use Microsoft MFC to design the following classes:

           
    class CWorkstation: public CObject

    {

    public:

        stationstate priorstate; ∥ record the state before the failure when a failure occurs

        double surplus_needtime; ∥ is used to record the meeting of the corresponding assembly station during the process of assembling the corresponding product

                                     ∥ Remaining assembly time of the product at the time of failure

        long buffer; ∥The size of the buffer of the corresponding assembly station, that is, the number of storage locations
        <!-- SIPO <DP n="18"> -->
        <dp n="d18"/>
        Cprodnode waitingprod; ∥The products queued for assembly in the corresponding station buffer, p3 warehouse

        double needtime; ∥ the assembly time required by the product on the co-location

        stationstate state; ∥ station state

        double sum_emptytime, sum_processtime, sum_readytime;

                                   ∥Accumulated idle time, accumulated station processing (assembly) time, accumulated preparation time

        int current_prodno, current-prodtype; ∥ the number and type of the product being assembled at the corresponding station

        double begintime, planfinishtime;

                                   ∥ The starting time of assembly and the planned completion time of the product at the station

        int GetProdNumber(); ∥Get the serial number of the product being assembled by the corresponding station

        double getplanfinishtime(); ∥Get the planned completion time of the product at the station

        int getcurrentprodtype(); ∥Get the type of product being assembled at the corresponding station

        CWorkstation();

        virtual~CWorkstation();

        void init();

    };

        

The properties encapsulated in this class record the state of the corresponding station during the entire assembly line, and the methods in this class implement the operation of the station's properties. The attribute state belongs to typedef enum {empty=1, wrong, working, waiting, ready, sleep} stationstate, and its values empty, ready and sleep (indicating that the corresponding station has not started working) indicate that the corresponding station is in the warehouse p ₁ , working indicates that the corresponding station is in place p ₄ , and wrong indicates that the corresponding station is in place p ₅ .

For the "warehousing goods warehouse" place p ₂ in ESHLEP-N, we have designed the goods-to-be-loaded warehouse class in the program:

           
    class Cbodysimu ∥ The class that establishes the initial linked list of items to be loaded

    {

    public:

        Cbodysimu();

        virtual~Cbodysimu();

    public:

        int prodnum; ∥ product number to be installed

        int prodtype; ∥ type of product to be installed

        Cbodysimu *next; ∥ pointer to the next object to be loaded

    };

        

And use the following class to realize that the tokens (to-be-loaded items) in _p2 are sorted in the scheduling order:

           
    class Cprodnode ∥ The linked list of the initial items to be loaded, which is also used as a buffer in the corresponding station

                               A linked list of products queued for assembly in ∥

    {

    public:
        <!-- SIPO <DP n="19"> -->
        <dp n="d19"/>
        Cprodnode();

        virtual~Cprodnode();

    public:

        void delhead();

        Cbodysimu *GetPointNow();

        Cbodysimu *head, *now, *end;

        int count;

        void add(int prodnum, int prodtype); ∥ add new node

        void deleteall(); ∥ delete all linked lists

    };

        

When ESHLEP-N is started, the above-mentioned data structure can be used to realize the initialization of the storehouse p ₂ of the "warehouse for loading". Similarly, for the "queuing" place p ₃ on each station, the above data structure can also be used to realize.

For the "finished product warehouse" place p ₆ in ESHLEP-N, a variable overprods is used in the simulation to record the finished products that have been assembled on the assembly line, and the value of overprods represents the number of tokens in p ₆ .

Since there is a one-to-many mapping relationship between colored tokens and tokens, colored tokens can be regarded as the "view" of tokens, so in the implementation of the ESHLEP-N model, no special data structure is designed to Saving colored tokens is just to determine the number, display and distribution of colored tokens according to the one-to-many mapping relationship between colored tokens and tokens when performance statistics and ESHLEP-N graphical models are displayed.

As for, the transition class can be defined as follows:

           
    class CTransition: transition class in public CObject ∥ ESHLEP-N

    {

    public:

        CTransition();

        CTransition(int transition, double begin, int sta)

        {

            transitiontype = transition;

            begintime=begin;

            station=sta;

        } ∥ transition constructor

    public:

        int transitiontype; ∥ transition type, 1: t1, 2: t2, 3: t3, 4: t4, 5: t5

        double begintime; ∥ the time when the transition is triggered

        int station; ∥ transition triggered station 0-m

    };

        

The transition attribute transitiontype is defined in the CTransition class, whose values are 1, 2, 3, 4, and 5 respectively represent transitions t ₁ , t ₂ , t ₃ , t ₄ , and t ₅ in ESHLEP-N. transitiontype=1 indicates that there is an item to be loaded or a virtual item to be loaded in the item to be loaded warehouse and enters the buffer zone of the first station to wait for assembly.

The transition attribute begin and attribute sta are defined in the CTransition class, which respectively represent the time when the transition occurs and the station where the transition occurs.

In the implementation of the program, use the CtypedPtrArray<CObArray, CTransition ^* >transitions encapsulated by MFC to realize the linked list structure (queue) of transition. The CTypedPtrArray encapsulated in MFC provides Add(), Remove(), InsertInto() and other methods, which can insert CTransition ^* into pointer array transitions, and are easy to maintain. Therefore, during the execution of the program, it is only necessary to take out the transition that occurs first in chronological order, execute related functions, and then delete it in the pointer array.

In addition, in object-oriented simulation, the problem of simulation time must also be solved. In discrete-event simulation, simulation time is a logical clock that is different from the real time scale, and it is related to the activities of all entities and all schedules. The scale of simulation time is chosen arbitrarily and is independent of real time. Each event is associated with the logical clock through a scheduled event time, which corresponds to the real time of the physical system when the corresponding physical event occurs. In the design of the program, we defined the property simulationclock in the CsimulationDoc: public CDocument class of the main program, which is used to record the simulation time.

4.3.2 Transition trigger rules

There are 12 transition trigger rules in 5 categories, and each type of rule corresponds to a transition trigger. The details are as follows, where R plus a number indicates the rule number, and the first number after R indicates the type of transition.

R101; if (1) the assembly line is not blocked, (2) the last station on the assembly line has a product to complete assembly, (3) there is a token b in the warehouse p ₂ ; then transition t ₁ is triggered, that is, from p ₂ Remove a token b and add a token q ₁ to p ₃ .

R201: If (1) the assembly line is not blocked, (2) there is a token w in p ₁ indicating that station i is free, and (3) there is a token q _i in p ₃ (representing the product in process waiting for assembly at station i ), then transition t ₂ is triggered, that is, a token w is removed from p ₁ , a token q _i is removed from p ₃ , combined into a compound token <w, b> and added to p ₄ .

R202: If (1) the assembly line is blocked, (2) there is a token w in p ₁ indicating that the station i is free, (3) there is a token q _i in p ₃ , (4) the station i is blocked now; then Transition t ₂ is triggered, that is, a token w is removed from p ₁ , a token q _i is removed from p ₃ , combined into a compound token <w, b> and added to p ₄ . If the total number of in-process items in the buffer zone of station i and the buffer zone of station i+1 does not exceed the rated quantity, clear the blocking status of the assembly line and station i.

R301: If (1) the assembly line is not blocked, (2) there is a composite token <w, b> in _p4 indicating that station i has just finished assembling a loading item b, (3) station i is not on the assembly line The last station; then the transition t ₃ is triggered, that is, a compound token <w, b> is removed from p ₄ , decomposed into a token w and a token q _i+1 and added to p ₁ and p ₃ respectively .

R302: If (1) the assembly line is not blocked, (2) there is a compound token <w, b> in _p4 indicating that station i has just assembled a product b in progress, (3) station i is on the assembly line The last station; then transition _t3 is triggered, that is, a compound token <w, b> is removed from _p4 , decomposed into a token w and a token b, and added to _p1 and _p6 respectively.

R303: If the number of token q in p ₃ exceeds the limit (that is, the total number of loading items in the buffer zone of station i and the buffer zone of station i+1 exceeds the rated quantity, the buffer zone of station i is full ); then the entire assembly line enters a blocking state.

R304: If (1) the assembly line is blocked, (2) one of _p4 indicates that station i has just finished assembling a compound token <w, b> in loading b, (3) station i is not the last on the assembly line One station, (4) station i is the current blocking station; then transition _t3 is triggered, that is, a composite token <w, b> is removed from _p4 and decomposed into a token w and a token q _i+1 are added to p ₁ and p ₃ respectively.

R305: If (1) the assembly line is blocked, (2) one of _p4 indicates that station i has just finished assembling a compound token <w, b> in loading b, (3) station i is the last on the assembly line One station, (4) station i is the current blocking station; then transition _t3 is triggered, that is, a composite token <w, b> is removed from _p4 and decomposed into a token w and a token b Add to p ₁ and p ₆ respectively.

R401: If there is a fault in the idle station represented by a token w in _p1 ; then transition _t4 is triggered, that is, a token w is removed from _p1 and added to _p5 .

R402: If there is a compound token <w, b> in p ₄ and the assembly station i represented by it fails; then transition _t4 is triggered, that is, a compound token <w, b> is removed from p ₄ Add to p ₅ .

R501: If the fault state of station i represented by a token w in p ₅ is eliminated; then transition t ₅ is triggered, that is, a token w is removed from p ₅ and added to p ₁ .

R502: If there is a compound token <w, b> in p ₅ and the fault status of station i is eliminated; then transition t ₅ is triggered, that is, a compound token <w, b> is removed from p ₅ and added to p ₄ .

4.3.3 Change processing flow

In the simulation implementation based on the ESHLEP-N model, we first take the first transition event from the transition queue to process. The step is to judge whether the assembly line is blocked. If it is blocked, enter the blocking processing program. If it is not blocked, read Get the type of transition and the station triggered by the transition, and enter the corresponding transition processing program. The triggering of transitions should follow the above-mentioned transition triggering rules, and the following uses a flow chart to describe its implementation process.

(1) Main process of system transition processing

Assuming that there are 33 assembly stations in a mixed batch assembly line, and a batch of production plans requires assembly of 20 products, then the initial colored logo of the ESHLEP-N model can be expressed as:

CM ₀ (p ₁ )=33w, indicating that all assembly stations are free.

CM ₀ (p ₂ )=20b, indicating that there are 20 items to be loaded in the item library.

CM ₀ (p ₃ )=φ, indicating that there is no product waiting for assembly at all stations.

CM ₀ (p ₄ )=φ, indicating that no station is assembling products.

CM ₀ (p ₅ )=φ, indicating that no station fails.

CM ₀ (p ₆ )=φ, indicating that there is no assembled finished product in the finished product warehouse.

According to the initial colored marks above, the main process of system transition processing (that is, the main program block diagram of the simulation software) is shown in Figure 10.

(2) Processing flow of transition _t1

The function of transition _t1 is to make the goods to be loaded in the warehouse of "warehouse to be loaded" enter the assembly line. The station where this change occurs must be the smallest station on the assembly line, that is, the on-line station. When processing transition _t1 , it is first judged whether there are tokens in the warehouse of the goods to be loaded; if yes, add the goods to be loaded in the queuing warehouse of the smallest station; Add a virtual item of type -1 to the "queuing" storehouse. Its processing flow is shown in Figure 11.

(3) Processing flow of transition _t2

Transition t ₂ is the transition of "start assembly", that is, take a product from the queuing warehouse of the station where the transition occurs, if it is not a virtual product to be installed, set the state of the station to working and generate the transition t ₃ of the station Put it into the transition queue, and then complete tasks such as blocking judgment. The processing flow is shown in Figure 12. It is worth mentioning that when transition _t3 occurs in this processing flow, it is necessary to consider whether the product needs assembly preparation at this station. If preparation is required, the preparation time of the product must be added to its assembly time as the transition The trigger time of _t3 , otherwise, the assembly time of the product is taken as the trigger time of transition _t3 . The assembly line is flexible due to the manual handling of the assembly work, allowing a certain number of storage locations for the product in progress (products in the assembly process) to be set in the virtual buffer zone of each station, that is, allowing the workers to properly handle the assembly when the task is completed. Move the assembly position forward, and properly move the assembly position backward when the task is too late to complete. However, due to the constraints of the position of the assembly parts, the forward and backward movement of the worker cannot exceed the specified limit. This can be achieved by specifying the buffer zone of each station. And the total number of goods in progress in the buffer zone of the next station shall not exceed the rated quantity. Therefore, according to the station parameter settings in the database, the rated quantity of the buffer zone of each station is determined at the beginning of the simulation. quantity, the buffer zone defining this station is full and the assembly line is blocked.

(4) Processing flow of transition _t3

Transition t ₃ is the transition of "complete assembly", that is, the transition of the completion of the assembly task of the corresponding product at a certain station, which mainly deals with the status of this station and the next station, and its processing flow is shown in Figure 13. In the figure, the ready state of the station indicates that the corresponding station is ready for assembly (including preparation).

(5) Processing flow of transition _t4

Transition t ₄ is a "fault occurs" transition, and its processing flow is relatively simple, as shown in Figure 14. In this processing flow, it is first necessary to determine whether the station is working when the fault occurs, that is, whether there is a product in progress on the station, and if so, the transition t ₃ of the station needs to be deleted in the transition queue. Then save the state information of the station before the fault occurs and set the state of the station to wrong.

(6) Processing flow of transition _t5

Transition _t5 is a transition of "fault end", and its processing flow is shown in Figure 15. In this processing flow, it is first necessary to determine whether there is a product in progress at this station, and if not, simply set the status of this station to empty. Otherwise, it is necessary to further judge whether this station is assembling products before the fault occurs, and if so, it is necessary to restore the transition _t3 of this station that was deleted in the processing flow of the previously triggered transition _t4 and set the original trigger time of _t3 Add the duration of this fault as the new trigger time of t ₃ , if not, generate the transition t ₂ of this station.

(7) Blocking processing flow

The above transition t _1-5 processing flow occurs under normal conditions of the assembly line. In the case of blocking, the general processing principle is roughly the same as in the normal case, with a slight difference, as shown in Figure 16: When the transition _t2 is triggered in the blocked state, it is first necessary to judge whether the station triggered by the transition is blocked state, if it is, clear the assembly line and the blocking flag of the station, and process the transition as normal; otherwise, do not process the transition. Similarly, when processing transition _t3 , it is also necessary to first judge whether the station triggered by the transition is the current blocked station, and if so, process the transition as normal; otherwise, do not process the transition. So by processing these transitions that are triggered at the blocking station, you can eliminate the blocking of the assembly line. After the blockage is eliminated, all transitions in the transition queue whose transition trigger time is less than the current simulation time (the current simulation time is the transition trigger time for eliminating assembly line blockage) are processed. This is equivalent to when the assembly line is blocked, the "start assembly" and "finish assembly" events and the "to-be-loaded assembly line" events on other stations cannot occur. These events can only occur after the assembly line blockage is eliminated.

4.4 Realization of production scheduling simulation of mixed batch assembly line

The realization of production scheduling simulation of mixed batch assembly line is based on the realization of Extended Stochastic Advanced Decision Petri Net (ESHLEP-N) model. Previously, we have established the ESHLEP-N model of the mixed-batch assembly line, and introduced its object-oriented implementation, including the Microsoft MFC-based class (class) representation of places, tokens and transitions, transition queues, and transition triggers Rules and transition processing flow. On this basis, we use Microsoft Visual C ⁺⁺ 5.0 to write the production scheduling simulation software of mixed batch assembly line.

The simulation process is as follows: First, initialize the " To-be-installed warehouse" warehouse, that is, to determine the type, quantity and on-line assembly sequence of the to-be-installed goods, and then according to the first-come-first-served rule and the above-mentioned transition trigger rules, sequentially place the waiting The loaded product is sent to the assembly line for assembly; the product to be loaded is assembled at the on-line station and becomes the in-process product, and is assembled at each station in turn along the assembly line; after the in-process product is assembled at each station, it enters the next The "queuing" warehouse of the station; the "queuing" warehouse of each station has a certain capacity. When the quantity of goods in progress in the "queuing" warehouse of a certain station exceeds this capacity, the assembly line enters a blocked state; in After being assembled by the last station (off-line station), the loaded product becomes a finished product and enters the "finished product warehouse" warehouse; during the whole simulation process, the station is allowed to fail; when all the cars are off-line, the simulation ends. In order to shorten the simulation time, a variable time flow is used to control the simulation process and there is no dynamic display of text and graphics during the simulation process, and only the performance index of a given schedule is calculated through fast simulation.

Because many parameters are needed in the simulation, for the generality of the software, the parameters are placed in the database, and these parameters are read when the simulation is started. In this way, after the situation of the assembly line changes, only the parameters need to be modified according to the database interface provided, and the scheduling simulation software can adapt to the new situation without modifying the scheduling simulation software. Since Microsoft Visual C ⁺⁺ 5.0 is used as the development tool of the scheduling simulation software, the MFC class library provided by Microsoft can be used to read the data in the database conveniently. At the same time, we also provide a database modification interface in VC, mainly using Activex controls DBGrid and RemoteDataControl to realize data reading and modification.

In summary, ESHLEP-N has the advantages of intuitive image, simple structure, few nodes, good description, strong decision-making ability, double token and double identification, etc., which is very suitable for modeling and scheduling simulation of mixed batch assembly line. The scheduling simulation software has two main purposes: first, as a fast scheduling simulator (that is, dynamic display without text and graphics), to calculate the performance index of a given scheduling; second, to obtain the optimal production plan and scheduling Finally, set the scheduling simulation software to animation display (or ESHLEP-N graphic display) mode to observe the optimal scheduling process of the mixed-batch assembly line and obtain the optimal scheduling performance index.

5. Integrated optimization software for production planning, scheduling and simulation of mixed batch assembly line

According to above-mentioned algorithm 1-5 and program flowchart thereof, and the ESHLEP-N model of mixed batch assembly line and its object-oriented realization method, the present inventor has adopted Microsoft Visual C ⁺⁺ 5.0 programming to realize solving above-mentioned mixed batch assembly line production Embedded tabu search simulation method, alternate tabu search simulation method, and serial tabu search simulation method for integrated optimization of planning and scheduling, developed integrated optimization software for production planning, scheduling and simulation of mixed-batch assembly line, its software structure As shown in Figure 17. The software consists of 8 modules including order smoothing, rough production planning, embedded tabu search, alternate tabu search, serial tabu search, animation scheduling simulation, parameter management and optimization result query. The tabu search and serial tabu search modules call the fast scheduling simulation module together. In the figure, the order smoothing module is used to smooth the customer's demand; the rough production planning module uses the branch and bound method to solve the mixed integer linear programming model of formula (4)-(8) to obtain the preparation cost and idle time of each assembly station A rough production plan that takes as little time as possible and meets product demand as much as possible; the main difference between the animation scheduling simulation module and the fast scheduling simulation module is whether there is animation display during the simulation process; the parameter management module manages the product cost coefficient in the mixed integer linear programming model , the assembly time, preparation time and preparation cost of the product at each station, the idleness and failure of the station, and the algorithm parameters; the optimization result query module is used to query the results of the integrated optimization of production planning and scheduling.

Claims (4)

1. An integrated optimization control method for a mixed batch assembly line, characterized in that the method comprises the following steps: (1) Smooth customer product demand; (2) According to the smoothed product demand, the branch and bound algorithm is used to solve the mixed integer programming model of the mixed-batch assembly line, so as to obtain the rough plan that minimizes the preparation cost and idle time of each assembly station and satisfies the product demand as much as possible. Production Plan; (3) On the basis of the integrated optimization model of production planning and scheduling of the mixed batch assembly line, aiming at three different levels of product types and quantities, such as small, medium and large, respectively use the embedded tabu search simulation method and the alternate tabu search The simulation method and the serial tabu search simulation method are used to obtain the best production plan of the mixed-batch assembly line with the rough production plan as the initial solution, that is, the product type and quantity, and the scheduling, that is, the assembly sequence; (4) Observe the optimal scheduling process of the mixed-batch assembly line through animation scheduling simulation; (5) Judging whether the product requirements of customers are met; (6) If after the animation scheduling simulation, it is considered that the product requirements are not met, the best plan and scheduling can be modified appropriately and then simulated; (7) If it is considered to meet the product requirements after animation scheduling simulation, it can be used as a formal plan and scheduling to be issued for execution; (8) According to the formal plan and scheduling, arrange the production and control the on-line of the products to be installed, and control the operation of the mixed-batch assembly line according to the moving speed of the assembly line determined during the animation scheduling simulation. 2. The integrated optimization control method of the mixed batch assembly line according to claim 1, characterized in that the main steps of the embedded tabu search simulation method are: (1) looking for a feasible plan and scheduling with the rough production plan as the initial production plan, (2) Then use tabu search to find the best plan at the plan layer, (3) use another tabu search to find the schedule with the best performance index after fast simulation calculation for each adjacent plan generated by the plan layer, until using Production planning and scheduling are optimized at the same time. 3. The integrated optimization control method of the mixed batch assembly line according to claim 1, characterized in that the main steps of the alternate tabu search simulation method are: (1) looking for a feasible plan and scheduling with the rough production plan as the initial production plan; (2) Given the schedule, use tabu search to find the plan with the best performance index after fast simulation calculation; (3) Conversely given the plan, use another tabu search to find the schedule with the best performance index after fast simulation calculation ; (4) Alternately use (2) and (3) two steps until finding the best plan and scheduling. 4. The integrated optimization control method of the mixed batch assembly line according to claim 1, characterized in that the main steps of the serial tabu search simulation method are: (1) use the rough production plan as the initial production plan and use the rule scheduling simulation method to find A feasible plan and scheduling; (2) Starting from the feasible plan, use tabu search to find the plan with the best performance index based on rule scheduling and fast simulation calculation; (3) For the best plan, use another tabu search to find the Fast simulation computes the schedule with the best performance metrics.

Images