# Research on Construction and Application for the Model of Multistage Job Shop Scheduling Problem

Authors: Jianzhong Xu; Song Zhang; Yuzhen Hu
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Based on the practical application of an enterprise, we address the multistage job shop scheduling problem with several parallel machines in the first stage (production), a few parallel machines in the second stage (processing and assembly), and one machine in the following stages (including joint debugging, testing, inspection, and packaging). First, we establish the optimization objective model for the first two stages. Then, based on the design of the sequencing algorithm in the first two stages, a correction algorithm is designed between the first stage and the second stage to solve this problem systematically. Finally, we propose two benchmark approaches to verify the performance of our proposed algorithm. Verification of numerical experiments shows that the model and algorithm constructed in this paper effectively improve the production efficiency of the enterprise.


---

## Body

## 1. Introduction

Multistage scheduling problems are common in the actual production scheduling of enterprises. Since the beginning of the 21st century, with the rapid development of the social economy, the diversified and personalized needs of customers have been increasing daily. The relationship between market supply and demand is gradually changing from a seller’s market to a buyer’s market, and competition among enterprises is intensifying, forcing enterprises to change their production mode towards diversification, multiple varieties, and small batches. Therefore, how to respond quickly, optimize production, and meet customers’ needs efficiently and punctually has become the core factor of competition among enterprises. In this context, most enterprises modularize their production according to process characteristics to form a number of production and assembly workshops with specific functions. At this time, the multistage scheduling problem arises in production scheduling. However, most existing research remains theoretical, with few studies on practical application, so there is an urgent need to establish a set of system methods that can be applied to the multistage production enterprise production scheduling mode.In this study, we focus on the multistage job shop scheduling problem. The constraints (such as processing time and processing sequence) in the process of multistage job shop scheduling are considered to construct a mathematical model for different stages of production scheduling, and both a multistage separated production scheduling algorithm and an improved multistage relevance production scheduling algorithm are designed to solve the proposed problem. Finally, the improved multistage relevance production scheduling algorithm is verified through a computational experiment based on real-world data. Two contributions are made in this paper: (1) in the process of calculating the solution, the theory of scheduling and a heuristic algorithm are combined to obtain a satisfactory multistage production scheduling solution; (2) compared with previous articles, this paper pays more attention to the practical application of mathematical problems in enterprises. It not only improves the production efficiency of multistage manufacturing enterprises but also provides a scientific reference for the production decision-making of enterprises. Furthermore, the approach can create more profits for enterprises.The remainder of this paper is organized as follows. Section2 reviews the relevant literature on production scheduling. Section 3 builds a model for the multistage job shop scheduling problem. Section 4 designs the corresponding algorithm for the multistage job shop scheduling mode. Section 5 reports the numerical experiments of the model of multistage job shop scheduling, and conclusions are drawn in Section 6. The findings can be used as a reference for production enterprises’ decision-making and have good application value.


## 2. Literature Review

Production scheduling, which can be defined as to “allocate limited resources to several tasks in time to meet or optimize one or more objectives” [1], is a key task for manufacturing enterprises in implementing production plans. Moreover, production scheduling is an important field in operational research. Since Johnson [2] proposed an effective optimization algorithm for solving N/2/F/Cmax and some special n/3/F/Cmax problems, many scholars have engaged in production scheduling research. Graves [3] systematically summarized the types of production scheduling based on previous research. According to the processing complexity, he divided production scheduling into four types: one processor, parallel processors, flow shop, and job shop. This classification method has been adopted and quoted by later scholars.Many scholars engaged in one-processor scheduling and parallel-processor scheduling research in the early stage [4–8], and many scholars are continuing research in this field [9–15]. Luo et al. [16] studied the single-machine scheduling problem with job-dependent machine deterioration. Chen and Yuan [17] studied the classic single-machine scheduling problem with deadlines based on minimizing the total tardiness and proved that the problem is NP-hard. Luo and Liu [18] focused on the single-machine scheduling problem with workload dependent on maintenance time and extended the previous theoretical results. Atakan et al. [19] studied the single-machine scheduling problem with uncertain parameters. Zhang et al. [20] proposed an unrelated parallel machine scheduling problem based on the consideration of processing speed and processing time, and they verified the effectiveness of their proposed heuristic evolutionary algorithm. Vallada et al. [21] studied the problem of unrelated parallel machines with one additional resource using a scatter search algorithm. Alidaee et al. [22] used dynamic programming to study a parallel machine scheduling model in which the job processing rates are interdependent and jobs have no priority. Vincent et al. [23] studied the capacity-constrained batch problem with multiple projects, set time and unrelated parallel machines, and compared the results with those of Toledo and Armentano [24] to demonstrate the competitiveness of the existing research results.Meanwhile, scholars represented by Johnson [2] are also studying the multistage production scheduling problem. The development of production modularization and integration in manufacturing enterprises has led to complex relations among production processes, which often affect the progress of the whole production system. Indeed, the multistage flow shop scheduling and multistage job shop scheduling are more in line with the actual needs of enterprises. Multistage flow shop scheduling is applicable to steel manufacturing [25, 26], printed circuit boards [27], automobile manufacturing [28], and other enterprises whose products must be produced and processed according to a certain technological process. Multistage job shop scheduling is more common in manufacturing enterprises because of its uncertain processing process [29–32]. However, due to the lack of practical application background, most scholars are engaged in research from the perspective of improving the speed [33, 34] and solution quality [35, 36] of multistage production scheduling algorithms. Samarghandi [37] studied the problem of minimizing the maximum completion time of flow shop scheduling under the constraints of a minimum and maximum time delay. By constructing a mixed-integer linear programming model and a constraint programming model, the author proposed a tabu search algorithm and verified the effectiveness of the proposed tabu search algorithm with an example. Gong et al. [38] proposed a hybrid evolutionary algorithm based on the flexibility of workers that considered factors such as energy consumption. Experiments on benchmark examples demonstrated that the proposed algorithm was significantly better than two other well-known algorithms in terms of solution quality and computational efficiency. Caldeira and Gnanavelbabu [39] used an improved Java algorithm to solve a flexible job shop scheduling problem and compared the solution quality with other famous metaheuristic algorithms to verify the superiority of their algorithm. Dabah et al. [40] paralleled the tabu search algorithm to solve the blocking job shop scheduling problem and used data in the existing literature to verify that the designed algorithm can improve upon the best results achieved by a large number of benchmark methods in the literature. Zhang et al. [41] proposed an improved hybrid particle swarm optimization algorithm to study the multiobjective flexible job shop scheduling problem. The benchmark experiment showed that the algorithm has the advantages of high quality and fast convergence.A literature review finds many research results related to the production scheduling problem. However, the production scheduling problem is characterized by not only many production constraints but also a large number of production sequencing combinations, so a general production scheduling theory is difficult to develop. Existing scholars focus on improving the solution quality of the algorithms and give less attention to the application of the production scheduling model to solve the actual problems of enterprises. Therefore, the application of multistage production scheduling to better serve real manufacturing enterprises must be studied.


## 3. Problem Description and Model Formulation

### 3.1. Problem Description

Quality, cost, and delivery time are the three core issues in the production and operation management of enterprises. This paper focuses on the delivery time to solve a production scheduling problem in which the products go through multiple stages of production before final delivery. In this multistage production, the first two stages are usually the most complex because the product processing techniques of these two stages, which are the key factors affecting the production efficiency, are both independent and influence each other. The subsequent stages are all single-machine operations, so we simply need to sum the standard working hours of each stage. To summarize, we take the first two stages of the production scheduling process as the key content to be studied.


#### 3.1.1. Problem Description of the First-Stage Production Scheduling

The first stage usually involves producing intermediate products and providing raw materials for subsequent assembly. Letj workstations produce i parts in this stage. In this process, due to the limited number of processing workstations, there is no specific requirement for prioritizing which type of intermediate products to produce, which leads to many plans for production. However, the processing time for different types and models of intermediate products is different, and intermediate products can be processed at any workstation. At any time, an intermediate product can be processed at most at one workstation, and each workstation can process only one intermediate product at a time. The processing of intermediate products in any processing stage is not allowed to be interrupted. This scenario inevitably leads to different processing times for each workstation to complete the intermediate products. For a complete set of products, the production schedule of the first stage directly affects the assembly time of the second stage, so the production of the first stage must be scheduled carefully.


#### 3.1.2. Problem Description of the Second-Stage Production Scheduling

The second stage is the process of product system integration, and the speed of its progress directly affects the delivery time of the final product. Therefore, the production of the second stage must also be scheduled. In this stage,l workstation processes workpieces (denoted as set K), and the set K is divided into two subsets (i.e., K = K1∪K2): set K1, in which workpieces can be processed directly without waiting time, and set K2, in which workpieces have a waiting time. The waiting time is the total time spent in the production and conversion section of intermediate products in the first stage, and when the intermediate products are transferred to the second stage, they should be transferred in the form of subsystems.


#### 3.1.3. Relevance between the First Stage and the Second Stage

The relevance of the first stage, the second stage, and the third stage can be seen in Figure1.Figure 1
Relevance diagram of the first three stages.The first stage and second stage have obvious relevance in the process of production scheduling.First, the intermediate product production in the first stage and the no waiting time workpiece from setK1 in the second stage can be conducted in parallel, and their completion time directly affects the start time of the third stage.Second, the completion time of the intermediate product processing in the first stage directly affects the start time of the workpiece assembly with waiting time in the second stage.Third, the workpiece with waiting time in the second stage must be assembled in the form of a subsystem.Finally, only after all the workpieces are assembled can they be transferred to the third stage.


### 3.2. Model Formulation

#### 3.2.1. Objective

During the modeling process, this paper makes some reasonable simplifications, including that the availability of raw materials does not affect the processing process, workstation equipment failure has little impact on processing and can be ignored, the processing time of all intermediate products is known in standard working hours, and there is no disturbance of the processing time caused by the production personnel’s emotions. For the convenience of subsequent modeling, we call the processing and assembly of the second-stage workpiece the assembly task.According to the situation of the first two stages, the optimization objective is to minimize the latest completion time of the assembly task for all assembly stations in the second stage to ensure that all tasks are completed as evenly as possible before the third stage.


#### 3.2.2. Models

(1)
Parameter definitions are as follows:I: intermediate product setJ: intermediate product processing workstation setK′: subsystem setIk: intermediate product set contained in the k-th subsystem, k ∈ K′ti: processing time of intermediate product i on the processing workstation, i ∈ IL: assembly workstation setK1: assembly task set without waiting timeK2: assembly task set with waiting timeK: assembly task set, K = K1∪K2Pkl: assembly time of assembly task k on assembly workstation l, k ∈ K, l ∈ LCk: the end of processing time when assembly task k finishes processing in the first stage of intermediate products, k ∈ K(2)
Decision variables definition is as follows:(1)Xij=1,intermediate productiis processed on processingworkstationj,i∈I,j∈J,0,otherwise.Sij: start processing time of intermediate product i on processing workstation j, i ∈ I, j ∈ J.Cij: end processing time of intermediate product i on processing workstation j, i ∈ I, j ∈ J.(2)Xkl=1,assemble taskkis assembled on assembly workstationl,k∈K,l∈L,0,otherwise.Skl: start assembly time of assembly task k on assembly workstation l, k ∈ K, l ∈ L.Ckl: end assembly time of assembly task k on assembly workstation l, k ∈ K, l ∈ L.(3)
Objective function is as follows:(3)minmaxk,lSkl+Pkl.(4)
Constraints are as follows:(4)∑j∈JXij=1,i∈I,(5)Cij=Sij+ti,i∈I,j∈J,(6)CijXij≤Si′jXi′jorCi′jXi′j≤SijXij,i,i′∈I,j∈J,(7)Sij≥0,i∈I,j∈J,(8)Xij=0or1,i∈I,j∈J,(9)∑l∈LSklXkl>Ck,k∈K,(10)∑l∈LXkl=1,k∈K,(11)CklXkl≤Sk′lXk′lorCk′lXk′l≤SklXkl,k,k′∈K,l∈L,(12)Ckl=Skl+Pkl,k∈K,l∈L,(13)Skl>0,k∈K,l∈L,(14)Xkl=0,or1k∈K,l∈L.Objective function (3) is used to minimize the latest end time of each workstation.Constraint (4) indicates that an intermediate product can be processed by only one processing workstation. Constraint (5) represents the end processing time of intermediate product i on the processing workstation. Constraint (6) indicates that a single processing workstation cannot process two intermediate products simultaneously. Constraint (7) represents that decision variable Sij is a nonnegative continuous number. Constraint (8) indicates that decision variable Xij is an integer of 0 or 1. Constraint (9) indicates that the start time of the assembly task is later than the end time of the previous operation. There are two meanings: one is to take Ck = 0 for an assembly task that does not need to wait; the other is to take Ck > 0 for an assembly task that needs to wait. Constraint (10) indicates that an assembly task can be assembled by only one assembly workstation. Constraint (11) indicates that a single assembly workstation cannot assemble two assembly tasks simultaneously. Constraint (12) shows that the end assembly time of assembly task k on assembly workstation l is the sum of its start assembly time on assembly workstation l and its assembly time on assembly workstation l. Constraint (13) represents that decision variable Skl is a nonnegative continuous number. Constraint (14) indicates that decision variable Xkl is an integer of 0 or 1.The above models are difficult to solve with commercial software, and enterprises prefer to obtain a satisfactory solution instead of deliberately pursuing the optimal solution when addressing actual production scheduling problems. Thus, a heuristic algorithm is good for multistage production scheduling problems. Multistage production scheduling is usually solved stage by stage, in line with the actual production situation of enterprises. Therefore, a multistage heuristic algorithm is designed in this paper.


## 3.1. Problem Description

Quality, cost, and delivery time are the three core issues in the production and operation management of enterprises. This paper focuses on the delivery time to solve a production scheduling problem in which the products go through multiple stages of production before final delivery. In this multistage production, the first two stages are usually the most complex because the product processing techniques of these two stages, which are the key factors affecting the production efficiency, are both independent and influence each other. The subsequent stages are all single-machine operations, so we simply need to sum the standard working hours of each stage. To summarize, we take the first two stages of the production scheduling process as the key content to be studied.


### 3.1.1. Problem Description of the First-Stage Production Scheduling

The first stage usually involves producing intermediate products and providing raw materials for subsequent assembly. Letj workstations produce i parts in this stage. In this process, due to the limited number of processing workstations, there is no specific requirement for prioritizing which type of intermediate products to produce, which leads to many plans for production. However, the processing time for different types and models of intermediate products is different, and intermediate products can be processed at any workstation. At any time, an intermediate product can be processed at most at one workstation, and each workstation can process only one intermediate product at a time. The processing of intermediate products in any processing stage is not allowed to be interrupted. This scenario inevitably leads to different processing times for each workstation to complete the intermediate products. For a complete set of products, the production schedule of the first stage directly affects the assembly time of the second stage, so the production of the first stage must be scheduled carefully.


### 3.1.2. Problem Description of the Second-Stage Production Scheduling

The second stage is the process of product system integration, and the speed of its progress directly affects the delivery time of the final product. Therefore, the production of the second stage must also be scheduled. In this stage,l workstation processes workpieces (denoted as set K), and the set K is divided into two subsets (i.e., K = K1∪K2): set K1, in which workpieces can be processed directly without waiting time, and set K2, in which workpieces have a waiting time. The waiting time is the total time spent in the production and conversion section of intermediate products in the first stage, and when the intermediate products are transferred to the second stage, they should be transferred in the form of subsystems.


### 3.1.3. Relevance between the First Stage and the Second Stage

The relevance of the first stage, the second stage, and the third stage can be seen in Figure1.Figure 1
Relevance diagram of the first three stages.The first stage and second stage have obvious relevance in the process of production scheduling.First, the intermediate product production in the first stage and the no waiting time workpiece from setK1 in the second stage can be conducted in parallel, and their completion time directly affects the start time of the third stage.Second, the completion time of the intermediate product processing in the first stage directly affects the start time of the workpiece assembly with waiting time in the second stage.Third, the workpiece with waiting time in the second stage must be assembled in the form of a subsystem.Finally, only after all the workpieces are assembled can they be transferred to the third stage.


## 3.1.1. Problem Description of the First-Stage Production Scheduling

The first stage usually involves producing intermediate products and providing raw materials for subsequent assembly. Letj workstations produce i parts in this stage. In this process, due to the limited number of processing workstations, there is no specific requirement for prioritizing which type of intermediate products to produce, which leads to many plans for production. However, the processing time for different types and models of intermediate products is different, and intermediate products can be processed at any workstation. At any time, an intermediate product can be processed at most at one workstation, and each workstation can process only one intermediate product at a time. The processing of intermediate products in any processing stage is not allowed to be interrupted. This scenario inevitably leads to different processing times for each workstation to complete the intermediate products. For a complete set of products, the production schedule of the first stage directly affects the assembly time of the second stage, so the production of the first stage must be scheduled carefully.


## 3.1.2. Problem Description of the Second-Stage Production Scheduling

The second stage is the process of product system integration, and the speed of its progress directly affects the delivery time of the final product. Therefore, the production of the second stage must also be scheduled. In this stage,l workstation processes workpieces (denoted as set K), and the set K is divided into two subsets (i.e., K = K1∪K2): set K1, in which workpieces can be processed directly without waiting time, and set K2, in which workpieces have a waiting time. The waiting time is the total time spent in the production and conversion section of intermediate products in the first stage, and when the intermediate products are transferred to the second stage, they should be transferred in the form of subsystems.


## 3.1.3. Relevance between the First Stage and the Second Stage

The relevance of the first stage, the second stage, and the third stage can be seen in Figure1.Figure 1
Relevance diagram of the first three stages.The first stage and second stage have obvious relevance in the process of production scheduling.First, the intermediate product production in the first stage and the no waiting time workpiece from setK1 in the second stage can be conducted in parallel, and their completion time directly affects the start time of the third stage.Second, the completion time of the intermediate product processing in the first stage directly affects the start time of the workpiece assembly with waiting time in the second stage.Third, the workpiece with waiting time in the second stage must be assembled in the form of a subsystem.Finally, only after all the workpieces are assembled can they be transferred to the third stage.


## 3.2. Model Formulation

### 3.2.1. Objective

During the modeling process, this paper makes some reasonable simplifications, including that the availability of raw materials does not affect the processing process, workstation equipment failure has little impact on processing and can be ignored, the processing time of all intermediate products is known in standard working hours, and there is no disturbance of the processing time caused by the production personnel’s emotions. For the convenience of subsequent modeling, we call the processing and assembly of the second-stage workpiece the assembly task.According to the situation of the first two stages, the optimization objective is to minimize the latest completion time of the assembly task for all assembly stations in the second stage to ensure that all tasks are completed as evenly as possible before the third stage.


### 3.2.2. Models

(1)
Parameter definitions are as follows:I: intermediate product setJ: intermediate product processing workstation setK′: subsystem setIk: intermediate product set contained in the k-th subsystem, k ∈ K′ti: processing time of intermediate product i on the processing workstation, i ∈ IL: assembly workstation setK1: assembly task set without waiting timeK2: assembly task set with waiting timeK: assembly task set, K = K1∪K2Pkl: assembly time of assembly task k on assembly workstation l, k ∈ K, l ∈ LCk: the end of processing time when assembly task k finishes processing in the first stage of intermediate products, k ∈ K(2)
Decision variables definition is as follows:(1)Xij=1,intermediate productiis processed on processingworkstationj,i∈I,j∈J,0,otherwise.Sij: start processing time of intermediate product i on processing workstation j, i ∈ I, j ∈ J.Cij: end processing time of intermediate product i on processing workstation j, i ∈ I, j ∈ J.(2)Xkl=1,assemble taskkis assembled on assembly workstationl,k∈K,l∈L,0,otherwise.Skl: start assembly time of assembly task k on assembly workstation l, k ∈ K, l ∈ L.Ckl: end assembly time of assembly task k on assembly workstation l, k ∈ K, l ∈ L.(3)
Objective function is as follows:(3)minmaxk,lSkl+Pkl.(4)
Constraints are as follows:(4)∑j∈JXij=1,i∈I,(5)Cij=Sij+ti,i∈I,j∈J,(6)CijXij≤Si′jXi′jorCi′jXi′j≤SijXij,i,i′∈I,j∈J,(7)Sij≥0,i∈I,j∈J,(8)Xij=0or1,i∈I,j∈J,(9)∑l∈LSklXkl>Ck,k∈K,(10)∑l∈LXkl=1,k∈K,(11)CklXkl≤Sk′lXk′lorCk′lXk′l≤SklXkl,k,k′∈K,l∈L,(12)Ckl=Skl+Pkl,k∈K,l∈L,(13)Skl>0,k∈K,l∈L,(14)Xkl=0,or1k∈K,l∈L.Objective function (3) is used to minimize the latest end time of each workstation.Constraint (4) indicates that an intermediate product can be processed by only one processing workstation. Constraint (5) represents the end processing time of intermediate product i on the processing workstation. Constraint (6) indicates that a single processing workstation cannot process two intermediate products simultaneously. Constraint (7) represents that decision variable Sij is a nonnegative continuous number. Constraint (8) indicates that decision variable Xij is an integer of 0 or 1. Constraint (9) indicates that the start time of the assembly task is later than the end time of the previous operation. There are two meanings: one is to take Ck = 0 for an assembly task that does not need to wait; the other is to take Ck > 0 for an assembly task that needs to wait. Constraint (10) indicates that an assembly task can be assembled by only one assembly workstation. Constraint (11) indicates that a single assembly workstation cannot assemble two assembly tasks simultaneously. Constraint (12) shows that the end assembly time of assembly task k on assembly workstation l is the sum of its start assembly time on assembly workstation l and its assembly time on assembly workstation l. Constraint (13) represents that decision variable Skl is a nonnegative continuous number. Constraint (14) indicates that decision variable Xkl is an integer of 0 or 1.The above models are difficult to solve with commercial software, and enterprises prefer to obtain a satisfactory solution instead of deliberately pursuing the optimal solution when addressing actual production scheduling problems. Thus, a heuristic algorithm is good for multistage production scheduling problems. Multistage production scheduling is usually solved stage by stage, in line with the actual production situation of enterprises. Therefore, a multistage heuristic algorithm is designed in this paper.


## 3.2.1. Objective

During the modeling process, this paper makes some reasonable simplifications, including that the availability of raw materials does not affect the processing process, workstation equipment failure has little impact on processing and can be ignored, the processing time of all intermediate products is known in standard working hours, and there is no disturbance of the processing time caused by the production personnel’s emotions. For the convenience of subsequent modeling, we call the processing and assembly of the second-stage workpiece the assembly task.According to the situation of the first two stages, the optimization objective is to minimize the latest completion time of the assembly task for all assembly stations in the second stage to ensure that all tasks are completed as evenly as possible before the third stage.


## 3.2.2. Models

(1)
Parameter definitions are as follows:I: intermediate product setJ: intermediate product processing workstation setK′: subsystem setIk: intermediate product set contained in the k-th subsystem, k ∈ K′ti: processing time of intermediate product i on the processing workstation, i ∈ IL: assembly workstation setK1: assembly task set without waiting timeK2: assembly task set with waiting timeK: assembly task set, K = K1∪K2Pkl: assembly time of assembly task k on assembly workstation l, k ∈ K, l ∈ LCk: the end of processing time when assembly task k finishes processing in the first stage of intermediate products, k ∈ K(2)
Decision variables definition is as follows:(1)Xij=1,intermediate productiis processed on processingworkstationj,i∈I,j∈J,0,otherwise.Sij: start processing time of intermediate product i on processing workstation j, i ∈ I, j ∈ J.Cij: end processing time of intermediate product i on processing workstation j, i ∈ I, j ∈ J.(2)Xkl=1,assemble taskkis assembled on assembly workstationl,k∈K,l∈L,0,otherwise.Skl: start assembly time of assembly task k on assembly workstation l, k ∈ K, l ∈ L.Ckl: end assembly time of assembly task k on assembly workstation l, k ∈ K, l ∈ L.(3)
Objective function is as follows:(3)minmaxk,lSkl+Pkl.(4)
Constraints are as follows:(4)∑j∈JXij=1,i∈I,(5)Cij=Sij+ti,i∈I,j∈J,(6)CijXij≤Si′jXi′jorCi′jXi′j≤SijXij,i,i′∈I,j∈J,(7)Sij≥0,i∈I,j∈J,(8)Xij=0or1,i∈I,j∈J,(9)∑l∈LSklXkl>Ck,k∈K,(10)∑l∈LXkl=1,k∈K,(11)CklXkl≤Sk′lXk′lorCk′lXk′l≤SklXkl,k,k′∈K,l∈L,(12)Ckl=Skl+Pkl,k∈K,l∈L,(13)Skl>0,k∈K,l∈L,(14)Xkl=0,or1k∈K,l∈L.Objective function (3) is used to minimize the latest end time of each workstation.Constraint (4) indicates that an intermediate product can be processed by only one processing workstation. Constraint (5) represents the end processing time of intermediate product i on the processing workstation. Constraint (6) indicates that a single processing workstation cannot process two intermediate products simultaneously. Constraint (7) represents that decision variable Sij is a nonnegative continuous number. Constraint (8) indicates that decision variable Xij is an integer of 0 or 1. Constraint (9) indicates that the start time of the assembly task is later than the end time of the previous operation. There are two meanings: one is to take Ck = 0 for an assembly task that does not need to wait; the other is to take Ck > 0 for an assembly task that needs to wait. Constraint (10) indicates that an assembly task can be assembled by only one assembly workstation. Constraint (11) indicates that a single assembly workstation cannot assemble two assembly tasks simultaneously. Constraint (12) shows that the end assembly time of assembly task k on assembly workstation l is the sum of its start assembly time on assembly workstation l and its assembly time on assembly workstation l. Constraint (13) represents that decision variable Skl is a nonnegative continuous number. Constraint (14) indicates that decision variable Xkl is an integer of 0 or 1.The above models are difficult to solve with commercial software, and enterprises prefer to obtain a satisfactory solution instead of deliberately pursuing the optimal solution when addressing actual production scheduling problems. Thus, a heuristic algorithm is good for multistage production scheduling problems. Multistage production scheduling is usually solved stage by stage, in line with the actual production situation of enterprises. Therefore, a multistage heuristic algorithm is designed in this paper.


## 4. Scheduling Procedure (Algorithm Design)

According to the actual situation of production, this paper focuses on the first two stages of production scheduling and designs a corresponding scheduling algorithm. Generally, the scheduling process will not start the next stage until the previous stage is completed. Based on this principle, we design two-stage algorithms in Sections4.1 and 4.2, denoted as S1 and S2. Moreover, according to the relevance description in Section 3.1.3, the algorithm can be further optimized, so we propose an improved algorithm (denoted as S1′) for the first stage; see Section 4.3 for details.


### 4.1. Design of the First-Stage Production Scheduling Algorithm

#### 4.1.1. General Idea of the Production Scheduling Algorithm for the First Stage

In the first stage, the processing sequence of intermediate products and the processing sequence of each subsystem should be determined. The general ideas for the first-stage scheduling algorithm (S1) are as follows.First, we need to identify and summarize the intermediate products to which each subsystem belongs.Second, because the processed intermediate products need to be transferred to the second stage in the form of a subsystem, one subsystem must be completed before processing another subsystem; that is, if the intermediate products of one subsystem are being processed, the intermediate products of another subsystem cannot be processed.Finally, during intermediate product processing, the complexity of each subsystem is directly proportional to its processing time, so we prioritize complex subsystems, which should be transferred to the next stage as soon as possible. We give priority to complex systems, that is, tasks with long processing times, because Tang and Zhao [42] proved that the optimal solution of the maximum processing time can be obtained by performing tasks in descending order of processing time in the same speed machine scheduling problem, which will not be demonstrated here.


#### 4.1.2. Steps of S1

Step 1: all intermediate products are classified according to their subsystemsStep 2: the processing times of all intermediate products in setIk are added to obtain Mk, namely, Mk=∑i∈IktiStep 3: all subsystems are sorted in descending order according toMk, namely, Mk≥Mk+1,∀k∈1,…,K−1Step 4: all intermediate products in setI1 are sorted in descending order of ti, namely, ti≥ti+1,∀i∈1,…,I1−1Step 5: letk = 1. The first J parts are taken and arranged on workstations in sequence; now, let i=J+1Step 6: if any workstation is processing, thei-th intermediate product in set Ik set is assigned to this workstationStep 7: ifi>Ik, then let k = k+1, and go to Step 8; otherwise, go to Step 6, and let i = i+1Step 8: ifk<K, then all intermediate products in set Ik are sorted in descending order of ti, namely, ti ≥ ti+1; let i = 1, and go to Step 6; otherwise, go to Step 9Step 9: endThe time complexity of algorithm S1 isO (mn3), where m represents the number of processing subsystems, that is, m=K′, and n represents the maximum number of intermediate products in all subsystems, that is, n=maxk∈KIk. In Step 2, the summation of the processing time for each subsystem occurs no more than n times, so it takes at most mn iterations to obtain the total processing time for m subsystems. In Step 6, Step 7, and Step 8, intermediate product assignment of each subsystem to a workstation occurs no more than mn times. In Step 8, the complexity of the bubble sorting algorithm for each subsystem is O (n2). Therefore, the total complexity of algorithm S1 is O (mn) + O (mn3) = O (mn3).


### 4.2. Design of the Second-Stage Production Scheduling Algorithm

#### 4.2.1. General Idea of the Production Scheduling Algorithm for the Second Stage

Compared with that of the first-stage scheduling algorithm, the design of the second-stage scheduling algorithm is more complex because the types of tasks in the second stage are different: there are tasks both with and without waiting time. Thus, the assembly sequence must be determined for tasks both with and without waiting time. According to the set optimization objectives, the general ideas for the second stage scheduling algorithm are as follows.First, we need to identify and distinguish the types of tasks.Second, the tasks without waiting time are sorted in descending order of assembly time.Third, for tasks requiring waiting time, the waiting time is defined as the time consumed by the corresponding subsystem in the first stage. Therefore, the scheduling of tasks requiring waiting time is a dynamic process that should be combined with the scheduling situation of the first stage in Section4.1.1 and should be changed along with changes in the first stage of scheduling. Additionally, once a task is being assembled, it cannot be interrupted, and the assembly of another task can be started only if the previous task is completed.Finally, in the second stage, the goal is to balance the workload of each assembly workstation as much as possible. Only after each assembly workstation has completed the assembly task can the product be transferred to the next stage.


#### 4.2.2. Steps of S2

Step 1: all the assembly tasks in the second stage are classified according to their type to form the no waiting time task setK1 and the waiting time task set K2.Step 2: the tasks in task setK1 are sorted in descending order of assembly time Pk, namely, Pk≥Pk+1,∀k∈1,…,K1−1.Step 3: the firstminK1,L tasks are arranged on minK1,L workstations in turn; now, let k=minK1,L+1,∀k∈K1.Step 4: confirm whether there is an idle assembly workstation; if so, go to Step 5. Otherwise, continue to wait until an idle workstation appears; then, go to Step 5.Step 5: search task setK2 to confirm whether there are any tasks to be assembled. If there are tasks to be assembled, assembly task k′ with the longest assembly time is assigned to the idle assembly workstation; then, k′=k′+1. Otherwise, the k-th task in K1 is assigned to the idle assembly workstation.Step 6: ifk>K1, go to Step 7; otherwise, let k = k + 1, and go to Step 4.Step 7: confirm whether there is an idle assembly workstation; if so, go to Step 8. Otherwise, continue to wait until an idle workstation appears; then, go to Step 8.Step 8: search task setK2 to confirm whether there are any tasks to be assembled. If there are tasks to be assembled, assembly task k′ with the longest assembly time is assigned to the idle assembly workstation; then, k′=k′+1. Otherwise, continue to wait until a task to be assembled appears and assign it to the idle workstation.Step 9: ifk′>K2, go to Step 10; otherwise, go to Step 7.Step 10: end.The time complexity of algorithm S2 isOm′n′2, where m′ represents the number of assembly workstations, that is, m′=L, and n′ represents the maximum number of the two types of assembly tasks, that is, Ln′=maxK1,K2. Additionally, m steps are required to confirm the existence of an idle assembly workstation in Step 4. Step 5 needs K times to search set K. If there exist tasks to be assembled, the assignment of the task with the longest assembly time takes no more than K iterations; otherwise, it will take no more than K1 iterations to assign the task from set K1 in Step 5 and Step 6. Therefore, the complexity of Step 4, Step 5, and Step 6 is Om′n′2. Similarly, the complexity of Step 7, Step 8, and Step 9 is Om′K2. Therefore, the total complexity of algorithm S1 is Om′n′2+Om′K2=Om′n′2.


### 4.3. Improved Algorithm for the First Stage (S1′)

The scheduling algorithm design of the second stage will change dynamically with the scheduling of the first stage. Here, we give priority to tasks with longer assembly times, which need to be assembled first, while in the scheduling algorithm design of the first stage, we give priority to subsystems with a longer processing time, which need to be processed first. However, the assembly time and processing time are not the same concept; if the scheduling algorithm of the first stage is directly embedded in the scheduling algorithm of the second stage, it is no longer applicable. Therefore, the improved scheduling algorithm of the first stage (S1′) should be adjusted as follows.Step 1: subsystemsIk are sorted in descending order of assembly time Pk, namely, Pk≥Pk+1,∀k∈1,…,K−1Step 2: all intermediate products in setI1 set are sorted in descending order of ti, namely, ti≥ti+1,∀i∈1,…,I1−1Step 3: letk = 1; the first J components are arranged on J workstations in turn, and now let i=J+1Step 4: if any workstation finishes processing, thei-th intermediate product in set Ik is assigned to this workstationStep 5: ifi>Ik, then let k = k + 1, and go to Step 6; otherwise, go to Step 4 and let i = i + 1Step 6: ifk<K, then all intermediate products in set Ik are sorted in descending order of ti, namely, ti ≥ ti+1; let i = 1, and go to Step 4; otherwise, go to Step 7Step 7: endThe only difference between S1 and S1′ is the sorting criterion in Step 1; therefore, the complexity of S1′ is the same as that of S1.In summary, to solve the two-stage production scheduling problem, we propose two combined scheduling algorithms in this chapter: the S1-S2 algorithm and the S1′-S2 algorithm.


## 4.1. Design of the First-Stage Production Scheduling Algorithm

### 4.1.1. General Idea of the Production Scheduling Algorithm for the First Stage

In the first stage, the processing sequence of intermediate products and the processing sequence of each subsystem should be determined. The general ideas for the first-stage scheduling algorithm (S1) are as follows.First, we need to identify and summarize the intermediate products to which each subsystem belongs.Second, because the processed intermediate products need to be transferred to the second stage in the form of a subsystem, one subsystem must be completed before processing another subsystem; that is, if the intermediate products of one subsystem are being processed, the intermediate products of another subsystem cannot be processed.Finally, during intermediate product processing, the complexity of each subsystem is directly proportional to its processing time, so we prioritize complex subsystems, which should be transferred to the next stage as soon as possible. We give priority to complex systems, that is, tasks with long processing times, because Tang and Zhao [42] proved that the optimal solution of the maximum processing time can be obtained by performing tasks in descending order of processing time in the same speed machine scheduling problem, which will not be demonstrated here.


### 4.1.2. Steps of S1

Step 1: all intermediate products are classified according to their subsystemsStep 2: the processing times of all intermediate products in setIk are added to obtain Mk, namely, Mk=∑i∈IktiStep 3: all subsystems are sorted in descending order according toMk, namely, Mk≥Mk+1,∀k∈1,…,K−1Step 4: all intermediate products in setI1 are sorted in descending order of ti, namely, ti≥ti+1,∀i∈1,…,I1−1Step 5: letk = 1. The first J parts are taken and arranged on workstations in sequence; now, let i=J+1Step 6: if any workstation is processing, thei-th intermediate product in set Ik set is assigned to this workstationStep 7: ifi>Ik, then let k = k+1, and go to Step 8; otherwise, go to Step 6, and let i = i+1Step 8: ifk<K, then all intermediate products in set Ik are sorted in descending order of ti, namely, ti ≥ ti+1; let i = 1, and go to Step 6; otherwise, go to Step 9Step 9: endThe time complexity of algorithm S1 isO (mn3), where m represents the number of processing subsystems, that is, m=K′, and n represents the maximum number of intermediate products in all subsystems, that is, n=maxk∈KIk. In Step 2, the summation of the processing time for each subsystem occurs no more than n times, so it takes at most mn iterations to obtain the total processing time for m subsystems. In Step 6, Step 7, and Step 8, intermediate product assignment of each subsystem to a workstation occurs no more than mn times. In Step 8, the complexity of the bubble sorting algorithm for each subsystem is O (n2). Therefore, the total complexity of algorithm S1 is O (mn) + O (mn3) = O (mn3).


## 4.1.1. General Idea of the Production Scheduling Algorithm for the First Stage

In the first stage, the processing sequence of intermediate products and the processing sequence of each subsystem should be determined. The general ideas for the first-stage scheduling algorithm (S1) are as follows.First, we need to identify and summarize the intermediate products to which each subsystem belongs.Second, because the processed intermediate products need to be transferred to the second stage in the form of a subsystem, one subsystem must be completed before processing another subsystem; that is, if the intermediate products of one subsystem are being processed, the intermediate products of another subsystem cannot be processed.Finally, during intermediate product processing, the complexity of each subsystem is directly proportional to its processing time, so we prioritize complex subsystems, which should be transferred to the next stage as soon as possible. We give priority to complex systems, that is, tasks with long processing times, because Tang and Zhao [42] proved that the optimal solution of the maximum processing time can be obtained by performing tasks in descending order of processing time in the same speed machine scheduling problem, which will not be demonstrated here.


## 4.1.2. Steps of S1

Step 1: all intermediate products are classified according to their subsystemsStep 2: the processing times of all intermediate products in setIk are added to obtain Mk, namely, Mk=∑i∈IktiStep 3: all subsystems are sorted in descending order according toMk, namely, Mk≥Mk+1,∀k∈1,…,K−1Step 4: all intermediate products in setI1 are sorted in descending order of ti, namely, ti≥ti+1,∀i∈1,…,I1−1Step 5: letk = 1. The first J parts are taken and arranged on workstations in sequence; now, let i=J+1Step 6: if any workstation is processing, thei-th intermediate product in set Ik set is assigned to this workstationStep 7: ifi>Ik, then let k = k+1, and go to Step 8; otherwise, go to Step 6, and let i = i+1Step 8: ifk<K, then all intermediate products in set Ik are sorted in descending order of ti, namely, ti ≥ ti+1; let i = 1, and go to Step 6; otherwise, go to Step 9Step 9: endThe time complexity of algorithm S1 isO (mn3), where m represents the number of processing subsystems, that is, m=K′, and n represents the maximum number of intermediate products in all subsystems, that is, n=maxk∈KIk. In Step 2, the summation of the processing time for each subsystem occurs no more than n times, so it takes at most mn iterations to obtain the total processing time for m subsystems. In Step 6, Step 7, and Step 8, intermediate product assignment of each subsystem to a workstation occurs no more than mn times. In Step 8, the complexity of the bubble sorting algorithm for each subsystem is O (n2). Therefore, the total complexity of algorithm S1 is O (mn) + O (mn3) = O (mn3).


## 4.2. Design of the Second-Stage Production Scheduling Algorithm

### 4.2.1. General Idea of the Production Scheduling Algorithm for the Second Stage

Compared with that of the first-stage scheduling algorithm, the design of the second-stage scheduling algorithm is more complex because the types of tasks in the second stage are different: there are tasks both with and without waiting time. Thus, the assembly sequence must be determined for tasks both with and without waiting time. According to the set optimization objectives, the general ideas for the second stage scheduling algorithm are as follows.First, we need to identify and distinguish the types of tasks.Second, the tasks without waiting time are sorted in descending order of assembly time.Third, for tasks requiring waiting time, the waiting time is defined as the time consumed by the corresponding subsystem in the first stage. Therefore, the scheduling of tasks requiring waiting time is a dynamic process that should be combined with the scheduling situation of the first stage in Section4.1.1 and should be changed along with changes in the first stage of scheduling. Additionally, once a task is being assembled, it cannot be interrupted, and the assembly of another task can be started only if the previous task is completed.Finally, in the second stage, the goal is to balance the workload of each assembly workstation as much as possible. Only after each assembly workstation has completed the assembly task can the product be transferred to the next stage.


### 4.2.2. Steps of S2

Step 1: all the assembly tasks in the second stage are classified according to their type to form the no waiting time task setK1 and the waiting time task set K2.Step 2: the tasks in task setK1 are sorted in descending order of assembly time Pk, namely, Pk≥Pk+1,∀k∈1,…,K1−1.Step 3: the firstminK1,L tasks are arranged on minK1,L workstations in turn; now, let k=minK1,L+1,∀k∈K1.Step 4: confirm whether there is an idle assembly workstation; if so, go to Step 5. Otherwise, continue to wait until an idle workstation appears; then, go to Step 5.Step 5: search task setK2 to confirm whether there are any tasks to be assembled. If there are tasks to be assembled, assembly task k′ with the longest assembly time is assigned to the idle assembly workstation; then, k′=k′+1. Otherwise, the k-th task in K1 is assigned to the idle assembly workstation.Step 6: ifk>K1, go to Step 7; otherwise, let k = k + 1, and go to Step 4.Step 7: confirm whether there is an idle assembly workstation; if so, go to Step 8. Otherwise, continue to wait until an idle workstation appears; then, go to Step 8.Step 8: search task setK2 to confirm whether there are any tasks to be assembled. If there are tasks to be assembled, assembly task k′ with the longest assembly time is assigned to the idle assembly workstation; then, k′=k′+1. Otherwise, continue to wait until a task to be assembled appears and assign it to the idle workstation.Step 9: ifk′>K2, go to Step 10; otherwise, go to Step 7.Step 10: end.The time complexity of algorithm S2 isOm′n′2, where m′ represents the number of assembly workstations, that is, m′=L, and n′ represents the maximum number of the two types of assembly tasks, that is, Ln′=maxK1,K2. Additionally, m steps are required to confirm the existence of an idle assembly workstation in Step 4. Step 5 needs K times to search set K. If there exist tasks to be assembled, the assignment of the task with the longest assembly time takes no more than K iterations; otherwise, it will take no more than K1 iterations to assign the task from set K1 in Step 5 and Step 6. Therefore, the complexity of Step 4, Step 5, and Step 6 is Om′n′2. Similarly, the complexity of Step 7, Step 8, and Step 9 is Om′K2. Therefore, the total complexity of algorithm S1 is Om′n′2+Om′K2=Om′n′2.


## 4.2.1. General Idea of the Production Scheduling Algorithm for the Second Stage

Compared with that of the first-stage scheduling algorithm, the design of the second-stage scheduling algorithm is more complex because the types of tasks in the second stage are different: there are tasks both with and without waiting time. Thus, the assembly sequence must be determined for tasks both with and without waiting time. According to the set optimization objectives, the general ideas for the second stage scheduling algorithm are as follows.First, we need to identify and distinguish the types of tasks.Second, the tasks without waiting time are sorted in descending order of assembly time.Third, for tasks requiring waiting time, the waiting time is defined as the time consumed by the corresponding subsystem in the first stage. Therefore, the scheduling of tasks requiring waiting time is a dynamic process that should be combined with the scheduling situation of the first stage in Section4.1.1 and should be changed along with changes in the first stage of scheduling. Additionally, once a task is being assembled, it cannot be interrupted, and the assembly of another task can be started only if the previous task is completed.Finally, in the second stage, the goal is to balance the workload of each assembly workstation as much as possible. Only after each assembly workstation has completed the assembly task can the product be transferred to the next stage.


## 4.2.2. Steps of S2

Step 1: all the assembly tasks in the second stage are classified according to their type to form the no waiting time task setK1 and the waiting time task set K2.Step 2: the tasks in task setK1 are sorted in descending order of assembly time Pk, namely, Pk≥Pk+1,∀k∈1,…,K1−1.Step 3: the firstminK1,L tasks are arranged on minK1,L workstations in turn; now, let k=minK1,L+1,∀k∈K1.Step 4: confirm whether there is an idle assembly workstation; if so, go to Step 5. Otherwise, continue to wait until an idle workstation appears; then, go to Step 5.Step 5: search task setK2 to confirm whether there are any tasks to be assembled. If there are tasks to be assembled, assembly task k′ with the longest assembly time is assigned to the idle assembly workstation; then, k′=k′+1. Otherwise, the k-th task in K1 is assigned to the idle assembly workstation.Step 6: ifk>K1, go to Step 7; otherwise, let k = k + 1, and go to Step 4.Step 7: confirm whether there is an idle assembly workstation; if so, go to Step 8. Otherwise, continue to wait until an idle workstation appears; then, go to Step 8.Step 8: search task setK2 to confirm whether there are any tasks to be assembled. If there are tasks to be assembled, assembly task k′ with the longest assembly time is assigned to the idle assembly workstation; then, k′=k′+1. Otherwise, continue to wait until a task to be assembled appears and assign it to the idle workstation.Step 9: ifk′>K2, go to Step 10; otherwise, go to Step 7.Step 10: end.The time complexity of algorithm S2 isOm′n′2, where m′ represents the number of assembly workstations, that is, m′=L, and n′ represents the maximum number of the two types of assembly tasks, that is, Ln′=maxK1,K2. Additionally, m steps are required to confirm the existence of an idle assembly workstation in Step 4. Step 5 needs K times to search set K. If there exist tasks to be assembled, the assignment of the task with the longest assembly time takes no more than K iterations; otherwise, it will take no more than K1 iterations to assign the task from set K1 in Step 5 and Step 6. Therefore, the complexity of Step 4, Step 5, and Step 6 is Om′n′2. Similarly, the complexity of Step 7, Step 8, and Step 9 is Om′K2. Therefore, the total complexity of algorithm S1 is Om′n′2+Om′K2=Om′n′2.


## 4.3. Improved Algorithm for the First Stage (S1′)

The scheduling algorithm design of the second stage will change dynamically with the scheduling of the first stage. Here, we give priority to tasks with longer assembly times, which need to be assembled first, while in the scheduling algorithm design of the first stage, we give priority to subsystems with a longer processing time, which need to be processed first. However, the assembly time and processing time are not the same concept; if the scheduling algorithm of the first stage is directly embedded in the scheduling algorithm of the second stage, it is no longer applicable. Therefore, the improved scheduling algorithm of the first stage (S1′) should be adjusted as follows.Step 1: subsystemsIk are sorted in descending order of assembly time Pk, namely, Pk≥Pk+1,∀k∈1,…,K−1Step 2: all intermediate products in setI1 set are sorted in descending order of ti, namely, ti≥ti+1,∀i∈1,…,I1−1Step 3: letk = 1; the first J components are arranged on J workstations in turn, and now let i=J+1Step 4: if any workstation finishes processing, thei-th intermediate product in set Ik is assigned to this workstationStep 5: ifi>Ik, then let k = k + 1, and go to Step 6; otherwise, go to Step 4 and let i = i + 1Step 6: ifk<K, then all intermediate products in set Ik are sorted in descending order of ti, namely, ti ≥ ti+1; let i = 1, and go to Step 4; otherwise, go to Step 7Step 7: endThe only difference between S1 and S1′ is the sorting criterion in Step 1; therefore, the complexity of S1′ is the same as that of S1.In summary, to solve the two-stage production scheduling problem, we propose two combined scheduling algorithms in this chapter: the S1-S2 algorithm and the S1′-S2 algorithm.


## 5. Numerical Experiments

Empirical enterprises produce three main types of products (typeA, type E, and type F), and all products have to go through multistage production successively. Figure 2 illustrates a schematic of the multistage job shop problem. In the first stage, an intermediate product circuit board is produced, and, in the second stage, cable processing, core component pretreatment, and subsystem assembly are conducted. Then, joint debugging, testing, acceptance checking, and packing are performed in the subsequent stage. The entire production process conforms to the mathematical model and algorithm design built in this paper.Figure 2
Schematic representation of the multistage job shop problem.In the enterprise, there are four parallel processing workstations in the first stage. The four processing workstations have no sequence when they perform processing tasks, and they are independent of each other. Once an intermediate product begins processing on one of the workstations, it will not be terminated and transferred to another workstation. Furthermore, in the second stage, there are five assembly workstations. The five assembly workstations have no sequence when they perform assembly tasks, and the workstations are independent of each other. Once an assembly task is begun on a workstation, it will not be terminated and transferred to another workstation.


### 5.1. Process Data

An F-type product with complex technology is selected for empirical research. For reasons of confidentiality, the actual names of the subsystems, intermediate products, and assembly tasks are replaced in the following process data.


#### 5.1.1. Process Data in the First Stage

The processing time and subsystem details of the first-stage intermediate products are shown in Table1.Table 1
Process data in the first stage.
Subsystem nameIntermediate product nameiProcessing timetiSubsystem 1Intermediate product 150Intermediate product 220Intermediate product 34Intermediate product 424Intermediate product 54Intermediate product 612Intermediate product 718Intermediate product 828Intermediate product 935Intermediate product 1016Intermediate product 1142Intermediate product 1232Intermediate product 139Intermediate product 144.5Intermediate product 154Intermediate product 1632Intermediate product 174Subsystem 2Intermediate product 1818Intermediate product 193Intermediate product 2016Intermediate product 2116Intermediate product 221Intermediate product 231Subsystem 3Intermediate product 244Intermediate product 251Intermediate product 261Subsystem 4Intermediate product 2710Subsystem 5Intermediate product 2812Subsystem 6Intermediate product 298Intermediate product 308Intermediate product 314Intermediate product 326Intermediate product 336Intermediate product 3412Subsystem 7Intermediate product 350.5


#### 5.1.2. Process Data in the Second Stage

The assembly time and task type of the second-stage assembly tasks are shown in Table2.Table 2
Process data in the second stage.
Task typeTask nameAssembly timeTasks without waiting timeTask 122Task 227Task 32Tasks with waiting timeTask 419Task 525.5Task 68.5Task 772Task 813Task 917Task 1013.5


#### 5.1.3. Process Data in the Subsequent Stage

After completing the assembly tasks in the second stage, the products are integrated into a set of system products; then, joint debugging, working environment testing, acceptance checking, and packing are conducted in the subsequent stages. Table3 shows the process data for the subsequent stages.Table 3
Process data in the subsequent stage.
Joint debuggingWorking environment testAcceptance checkPacking45631


### 5.2. Comparison Analysis

To verify the effectiveness of the S1′-S2 algorithm, we propose two benchmark approaches: the S1-S2 algorithm and the actual operation approach of the enterprise.


#### 5.2.1. Comparative Analysis between the S1′-S2 Algorithm and S1-S2 Algorithm

The operation results of the S1′-S2 algorithm and the S1-S2 algorithm in the first and second stages, which can be seen in Tables4 and 5, can be obtained using the scheduling algorithm in Section 4. The comparison results are shown in Table 6.Table 4
Comparison table of algorithm operation results in the first stage.
Workstation no.S1′-S2 algorithmS1-S2 algorithmIntermediate product no.Processing timetijProcessing end timeCijIntermediate product no.Processing timetijProcessing end timeCijProcessing workstation 1Intermediate product 271010Intermediate product 15050Intermediate product 19313Intermediate product 22070Intermediate product 22114Intermediate product 13979Intermediate product 23115Intermediate product 3483Intermediate product 15065Intermediate product 1818101Intermediate product 22085Intermediate product 308109Intermediate product 13994Intermediate product 2710119Intermediate product 144.598.5Intermediate product 3412110.5Intermediate product 2812122.5Processing workstation 2Intermediate product 181818Intermediate product 114242Intermediate product 123250Intermediate product 42466Intermediate product 163282Intermediate product 61278Intermediate product 101698Intermediate product 144.582.5Intermediate product 154102Intermediate product 17486.5Intermediate product 308110Intermediate product 19389.5Intermediate product 350.5110.5Intermediate product 22190.5Intermediate product 244114.5Intermediate product 23191.5Intermediate product 3412103.5Intermediate product 336109.5Intermediate product 244113.5Processing workstation 3Intermediate product 201616Intermediate product 93535Intermediate product 114258Intermediate product 82863Intermediate product 42482Intermediate product 71881Intermediate product 61294Intermediate product 15485Intermediate product 3498Intermediate product 2116101Intermediate product 174102Intermediate product 326107Intermediate product 326108Intermediate product 314111Intermediate product 336114Intermediate product 251112Intermediate product 261115Intermediate product 261113Intermediate product 350.5113.5Processing workstation 4Intermediate product 211616Intermediate product 123232Intermediate product 93551Intermediate product 163264Intermediate product 82879Intermediate product 101680Intermediate product 71897Intermediate product 5484Intermediate product 54101Intermediate product 2016100Intermediate product 298109Intermediate product 298108Intermediate product 314113Intermediate product 2812120Intermediate product 251114Table 5
Comparison table of algorithm operation results in the second stage.
Workstation no.S1′-S2 algorithmS1-S2 algorithmTask no.Assembly timePkWaiting timeAssembly end timeCklTask no.Assembly timePkWaiting timeAssembly end timeCklAssembly workstation 1Task 227027Task 227027Task 917114131Task 1013.5113.5127Assembly workstation 2Task 122022Task 122022Task 1013.5110.5124Task 68.5113.5122Task 813120135Assembly workstation 3Task 3202Task 3202Task 419102121Task 917111128Assembly workstation 4Task 7721082Task 41986.5105.5Task 813122.5135.5Task 772119191Assembly workstation 5Task 525.51843.5Task 525.5101126.5Task 68.5115123.5Table 6
Comparison of the effectiveness of the algorithms.
S1-S2 algorithmS1′-S2 algorithmEffectiveness comparison (%)Total completion time of single set ofF-type products (hours)255199.521.76Annual output ofF-type product (set)10.8314.4224.90Annual profit value ofF-type product (10000 yuan)433.2576.824.90Table6 shows that 255 working hours are required to complete a single set of F-type products using the S1-S2 algorithm, while 199.5 working hours are required by the S1′-S2 algorithm: the completion time of the S1′-S2 algorithm is 21.76% higher than that of the S1-S2 algorithm.In terms of the annual output ofF-type products, the S1′-S2 algorithm produces 3.59 sets more than the S1-S2 algorithm, and the production efficiency is increased by 24.90%. The annual output of F-type products is obtained as the ratio of the actual working days of the enterprise in the whole year to the production cycle of a single set of F-type products. Two points need to be explained.First, the working system of the empirical enterprise is a one-day-off system; that is, there is only one day off (Sunday) every week. Based on 52 weeks in a year and deducting 11 days for China national legal holidays, we can obtain the total actual number of working days for the whole year of the empirical enterprise as follows: actual working days = 365 − 11 − 52 = 302 (days).Second, the working environment testing in the subsequent stages, which costs 56 hours, is completed continuously, so the working environment test actually takes 3 days.In terms of the annual profit value of F-type products, the S1′-S2 algorithm yields 1.436 million Yuan greater profit than the S1-S2 algorithm, and the profit margin is increased by 24.90%.The reason for the above differences is the different scheduling rules adopted in the production scheduling process. The S1-S2 algorithm isolates the two-stage production scheduling into two separate production stages, and its scheduling algorithm guarantees only the minimum of the latest completion time of each stage. The S1′-S2 algorithm regards the two-stage production scheduling as a whole and forms a link between the stages. Table4 shows that the latest completion time of the first stage of the S1′-S2 algorithm is 122 working hours and that of the S1-S2 algorithm is 120 working hours. However, in the second stage, the S1′-S2 algorithm gives priority to the assembly time and returns the information of the subsystems with long assembly times to the first stage of the production scheduling, which effectively balances the assembly capacity of each assembly workstation in the second stage. Thus, a more satisfactory solution can be obtained.


#### 5.2.2. Comparative Analysis between the S1′-S2 Algorithm and the Actual Operation of the Enterprise

To verify the effectiveness of the S1′-S2 algorithm, we obtain the output ofF-type products from 2015 to 2018. The comparison results between the actual operation of the enterprise and the S1′-S2 algorithm are provided in Table 7.Table 7
Production ofF-type products in 2015–2018.
Annual output ofF-type productS1′-S2 algorithmYear201520162017201814.42Production (set)5579In Table7, the output of F-type products is the highest in 2018, reaching 9 sets. The S1′-S2 algorithm can be used to obtain 14.42 sets of annual production, which is 1.6 times the actual production in 2018. Therefore, the production capacity of F-type products is improved considerably. In view of the above situation, we analyze the following two reasons for this improvement.First, in the actual production scheduling process, enterprises usually implement production scheduling according to the production schedule. The production scheduling personnel not only are familiar with the production process of the product but also monitor the first-line production workshop to follow the production progress and take timely and effective adjustment measures to ensure that the production scheduling meets the requirements of the production schedule as much as possible. However, in the process of adjusting production scheduling, due to the different experience of production scheduling personnel, different scheduling rules will be adopted, which results in the balance of orderly production of workstations being broken. In the end, good production capacity cannot be obtained.Second, the empirical enterprise implements the time work system. Under this condition, production workers inevitably experience inertia that affects their work enthusiasm and initiative and leads to relatively low production efficiency. The S1′-S2 algorithm that we highly recommend is designed from the theoretical perspective. It eliminates the influence of human factors in the production scheduling process to improve production capacity.In summary, the effectiveness of the S1′-S2 algorithm is substantially better than that of the S1-S2 algorithm and the actual operation of enterprises, which demonstrates that the empirical enterprise can effectively improve its production capacity and earn greater profits by introducing the S1′-S2 algorithm. The S1′-S2 algorithm has good reference significance for guiding the actual production scheduling of enterprises.


## 5.1. Process Data

An F-type product with complex technology is selected for empirical research. For reasons of confidentiality, the actual names of the subsystems, intermediate products, and assembly tasks are replaced in the following process data.


### 5.1.1. Process Data in the First Stage

The processing time and subsystem details of the first-stage intermediate products are shown in Table1.Table 1
Process data in the first stage.
Subsystem nameIntermediate product nameiProcessing timetiSubsystem 1Intermediate product 150Intermediate product 220Intermediate product 34Intermediate product 424Intermediate product 54Intermediate product 612Intermediate product 718Intermediate product 828Intermediate product 935Intermediate product 1016Intermediate product 1142Intermediate product 1232Intermediate product 139Intermediate product 144.5Intermediate product 154Intermediate product 1632Intermediate product 174Subsystem 2Intermediate product 1818Intermediate product 193Intermediate product 2016Intermediate product 2116Intermediate product 221Intermediate product 231Subsystem 3Intermediate product 244Intermediate product 251Intermediate product 261Subsystem 4Intermediate product 2710Subsystem 5Intermediate product 2812Subsystem 6Intermediate product 298Intermediate product 308Intermediate product 314Intermediate product 326Intermediate product 336Intermediate product 3412Subsystem 7Intermediate product 350.5


### 5.1.2. Process Data in the Second Stage

The assembly time and task type of the second-stage assembly tasks are shown in Table2.Table 2
Process data in the second stage.
Task typeTask nameAssembly timeTasks without waiting timeTask 122Task 227Task 32Tasks with waiting timeTask 419Task 525.5Task 68.5Task 772Task 813Task 917Task 1013.5


### 5.1.3. Process Data in the Subsequent Stage

After completing the assembly tasks in the second stage, the products are integrated into a set of system products; then, joint debugging, working environment testing, acceptance checking, and packing are conducted in the subsequent stages. Table3 shows the process data for the subsequent stages.Table 3
Process data in the subsequent stage.
Joint debuggingWorking environment testAcceptance checkPacking45631


## 5.1.1. Process Data in the First Stage

The processing time and subsystem details of the first-stage intermediate products are shown in Table1.Table 1
Process data in the first stage.
Subsystem nameIntermediate product nameiProcessing timetiSubsystem 1Intermediate product 150Intermediate product 220Intermediate product 34Intermediate product 424Intermediate product 54Intermediate product 612Intermediate product 718Intermediate product 828Intermediate product 935Intermediate product 1016Intermediate product 1142Intermediate product 1232Intermediate product 139Intermediate product 144.5Intermediate product 154Intermediate product 1632Intermediate product 174Subsystem 2Intermediate product 1818Intermediate product 193Intermediate product 2016Intermediate product 2116Intermediate product 221Intermediate product 231Subsystem 3Intermediate product 244Intermediate product 251Intermediate product 261Subsystem 4Intermediate product 2710Subsystem 5Intermediate product 2812Subsystem 6Intermediate product 298Intermediate product 308Intermediate product 314Intermediate product 326Intermediate product 336Intermediate product 3412Subsystem 7Intermediate product 350.5


## 5.1.2. Process Data in the Second Stage

The assembly time and task type of the second-stage assembly tasks are shown in Table2.Table 2
Process data in the second stage.
Task typeTask nameAssembly timeTasks without waiting timeTask 122Task 227Task 32Tasks with waiting timeTask 419Task 525.5Task 68.5Task 772Task 813Task 917Task 1013.5


## 5.1.3. Process Data in the Subsequent Stage

After completing the assembly tasks in the second stage, the products are integrated into a set of system products; then, joint debugging, working environment testing, acceptance checking, and packing are conducted in the subsequent stages. Table3 shows the process data for the subsequent stages.Table 3
Process data in the subsequent stage.
Joint debuggingWorking environment testAcceptance checkPacking45631


## 5.2. Comparison Analysis

To verify the effectiveness of the S1′-S2 algorithm, we propose two benchmark approaches: the S1-S2 algorithm and the actual operation approach of the enterprise.


### 5.2.1. Comparative Analysis between the S1′-S2 Algorithm and S1-S2 Algorithm

The operation results of the S1′-S2 algorithm and the S1-S2 algorithm in the first and second stages, which can be seen in Tables4 and 5, can be obtained using the scheduling algorithm in Section 4. The comparison results are shown in Table 6.Table 4
Comparison table of algorithm operation results in the first stage.
Workstation no.S1′-S2 algorithmS1-S2 algorithmIntermediate product no.Processing timetijProcessing end timeCijIntermediate product no.Processing timetijProcessing end timeCijProcessing workstation 1Intermediate product 271010Intermediate product 15050Intermediate product 19313Intermediate product 22070Intermediate product 22114Intermediate product 13979Intermediate product 23115Intermediate product 3483Intermediate product 15065Intermediate product 1818101Intermediate product 22085Intermediate product 308109Intermediate product 13994Intermediate product 2710119Intermediate product 144.598.5Intermediate product 3412110.5Intermediate product 2812122.5Processing workstation 2Intermediate product 181818Intermediate product 114242Intermediate product 123250Intermediate product 42466Intermediate product 163282Intermediate product 61278Intermediate product 101698Intermediate product 144.582.5Intermediate product 154102Intermediate product 17486.5Intermediate product 308110Intermediate product 19389.5Intermediate product 350.5110.5Intermediate product 22190.5Intermediate product 244114.5Intermediate product 23191.5Intermediate product 3412103.5Intermediate product 336109.5Intermediate product 244113.5Processing workstation 3Intermediate product 201616Intermediate product 93535Intermediate product 114258Intermediate product 82863Intermediate product 42482Intermediate product 71881Intermediate product 61294Intermediate product 15485Intermediate product 3498Intermediate product 2116101Intermediate product 174102Intermediate product 326107Intermediate product 326108Intermediate product 314111Intermediate product 336114Intermediate product 251112Intermediate product 261115Intermediate product 261113Intermediate product 350.5113.5Processing workstation 4Intermediate product 211616Intermediate product 123232Intermediate product 93551Intermediate product 163264Intermediate product 82879Intermediate product 101680Intermediate product 71897Intermediate product 5484Intermediate product 54101Intermediate product 2016100Intermediate product 298109Intermediate product 298108Intermediate product 314113Intermediate product 2812120Intermediate product 251114Table 5
Comparison table of algorithm operation results in the second stage.
Workstation no.S1′-S2 algorithmS1-S2 algorithmTask no.Assembly timePkWaiting timeAssembly end timeCklTask no.Assembly timePkWaiting timeAssembly end timeCklAssembly workstation 1Task 227027Task 227027Task 917114131Task 1013.5113.5127Assembly workstation 2Task 122022Task 122022Task 1013.5110.5124Task 68.5113.5122Task 813120135Assembly workstation 3Task 3202Task 3202Task 419102121Task 917111128Assembly workstation 4Task 7721082Task 41986.5105.5Task 813122.5135.5Task 772119191Assembly workstation 5Task 525.51843.5Task 525.5101126.5Task 68.5115123.5Table 6
Comparison of the effectiveness of the algorithms.
S1-S2 algorithmS1′-S2 algorithmEffectiveness comparison (%)Total completion time of single set ofF-type products (hours)255199.521.76Annual output ofF-type product (set)10.8314.4224.90Annual profit value ofF-type product (10000 yuan)433.2576.824.90Table6 shows that 255 working hours are required to complete a single set of F-type products using the S1-S2 algorithm, while 199.5 working hours are required by the S1′-S2 algorithm: the completion time of the S1′-S2 algorithm is 21.76% higher than that of the S1-S2 algorithm.In terms of the annual output ofF-type products, the S1′-S2 algorithm produces 3.59 sets more than the S1-S2 algorithm, and the production efficiency is increased by 24.90%. The annual output of F-type products is obtained as the ratio of the actual working days of the enterprise in the whole year to the production cycle of a single set of F-type products. Two points need to be explained.First, the working system of the empirical enterprise is a one-day-off system; that is, there is only one day off (Sunday) every week. Based on 52 weeks in a year and deducting 11 days for China national legal holidays, we can obtain the total actual number of working days for the whole year of the empirical enterprise as follows: actual working days = 365 − 11 − 52 = 302 (days).Second, the working environment testing in the subsequent stages, which costs 56 hours, is completed continuously, so the working environment test actually takes 3 days.In terms of the annual profit value of F-type products, the S1′-S2 algorithm yields 1.436 million Yuan greater profit than the S1-S2 algorithm, and the profit margin is increased by 24.90%.The reason for the above differences is the different scheduling rules adopted in the production scheduling process. The S1-S2 algorithm isolates the two-stage production scheduling into two separate production stages, and its scheduling algorithm guarantees only the minimum of the latest completion time of each stage. The S1′-S2 algorithm regards the two-stage production scheduling as a whole and forms a link between the stages. Table4 shows that the latest completion time of the first stage of the S1′-S2 algorithm is 122 working hours and that of the S1-S2 algorithm is 120 working hours. However, in the second stage, the S1′-S2 algorithm gives priority to the assembly time and returns the information of the subsystems with long assembly times to the first stage of the production scheduling, which effectively balances the assembly capacity of each assembly workstation in the second stage. Thus, a more satisfactory solution can be obtained.


### 5.2.2. Comparative Analysis between the S1′-S2 Algorithm and the Actual Operation of the Enterprise

To verify the effectiveness of the S1′-S2 algorithm, we obtain the output ofF-type products from 2015 to 2018. The comparison results between the actual operation of the enterprise and the S1′-S2 algorithm are provided in Table 7.Table 7
Production ofF-type products in 2015–2018.
Annual output ofF-type productS1′-S2 algorithmYear201520162017201814.42Production (set)5579In Table7, the output of F-type products is the highest in 2018, reaching 9 sets. The S1′-S2 algorithm can be used to obtain 14.42 sets of annual production, which is 1.6 times the actual production in 2018. Therefore, the production capacity of F-type products is improved considerably. In view of the above situation, we analyze the following two reasons for this improvement.First, in the actual production scheduling process, enterprises usually implement production scheduling according to the production schedule. The production scheduling personnel not only are familiar with the production process of the product but also monitor the first-line production workshop to follow the production progress and take timely and effective adjustment measures to ensure that the production scheduling meets the requirements of the production schedule as much as possible. However, in the process of adjusting production scheduling, due to the different experience of production scheduling personnel, different scheduling rules will be adopted, which results in the balance of orderly production of workstations being broken. In the end, good production capacity cannot be obtained.Second, the empirical enterprise implements the time work system. Under this condition, production workers inevitably experience inertia that affects their work enthusiasm and initiative and leads to relatively low production efficiency. The S1′-S2 algorithm that we highly recommend is designed from the theoretical perspective. It eliminates the influence of human factors in the production scheduling process to improve production capacity.In summary, the effectiveness of the S1′-S2 algorithm is substantially better than that of the S1-S2 algorithm and the actual operation of enterprises, which demonstrates that the empirical enterprise can effectively improve its production capacity and earn greater profits by introducing the S1′-S2 algorithm. The S1′-S2 algorithm has good reference significance for guiding the actual production scheduling of enterprises.


## 5.2.1. Comparative Analysis between the S1′-S2 Algorithm and S1-S2 Algorithm

The operation results of the S1′-S2 algorithm and the S1-S2 algorithm in the first and second stages, which can be seen in Tables4 and 5, can be obtained using the scheduling algorithm in Section 4. The comparison results are shown in Table 6.Table 4
Comparison table of algorithm operation results in the first stage.
Workstation no.S1′-S2 algorithmS1-S2 algorithmIntermediate product no.Processing timetijProcessing end timeCijIntermediate product no.Processing timetijProcessing end timeCijProcessing workstation 1Intermediate product 271010Intermediate product 15050Intermediate product 19313Intermediate product 22070Intermediate product 22114Intermediate product 13979Intermediate product 23115Intermediate product 3483Intermediate product 15065Intermediate product 1818101Intermediate product 22085Intermediate product 308109Intermediate product 13994Intermediate product 2710119Intermediate product 144.598.5Intermediate product 3412110.5Intermediate product 2812122.5Processing workstation 2Intermediate product 181818Intermediate product 114242Intermediate product 123250Intermediate product 42466Intermediate product 163282Intermediate product 61278Intermediate product 101698Intermediate product 144.582.5Intermediate product 154102Intermediate product 17486.5Intermediate product 308110Intermediate product 19389.5Intermediate product 350.5110.5Intermediate product 22190.5Intermediate product 244114.5Intermediate product 23191.5Intermediate product 3412103.5Intermediate product 336109.5Intermediate product 244113.5Processing workstation 3Intermediate product 201616Intermediate product 93535Intermediate product 114258Intermediate product 82863Intermediate product 42482Intermediate product 71881Intermediate product 61294Intermediate product 15485Intermediate product 3498Intermediate product 2116101Intermediate product 174102Intermediate product 326107Intermediate product 326108Intermediate product 314111Intermediate product 336114Intermediate product 251112Intermediate product 261115Intermediate product 261113Intermediate product 350.5113.5Processing workstation 4Intermediate product 211616Intermediate product 123232Intermediate product 93551Intermediate product 163264Intermediate product 82879Intermediate product 101680Intermediate product 71897Intermediate product 5484Intermediate product 54101Intermediate product 2016100Intermediate product 298109Intermediate product 298108Intermediate product 314113Intermediate product 2812120Intermediate product 251114Table 5
Comparison table of algorithm operation results in the second stage.
Workstation no.S1′-S2 algorithmS1-S2 algorithmTask no.Assembly timePkWaiting timeAssembly end timeCklTask no.Assembly timePkWaiting timeAssembly end timeCklAssembly workstation 1Task 227027Task 227027Task 917114131Task 1013.5113.5127Assembly workstation 2Task 122022Task 122022Task 1013.5110.5124Task 68.5113.5122Task 813120135Assembly workstation 3Task 3202Task 3202Task 419102121Task 917111128Assembly workstation 4Task 7721082Task 41986.5105.5Task 813122.5135.5Task 772119191Assembly workstation 5Task 525.51843.5Task 525.5101126.5Task 68.5115123.5Table 6
Comparison of the effectiveness of the algorithms.
S1-S2 algorithmS1′-S2 algorithmEffectiveness comparison (%)Total completion time of single set ofF-type products (hours)255199.521.76Annual output ofF-type product (set)10.8314.4224.90Annual profit value ofF-type product (10000 yuan)433.2576.824.90Table6 shows that 255 working hours are required to complete a single set of F-type products using the S1-S2 algorithm, while 199.5 working hours are required by the S1′-S2 algorithm: the completion time of the S1′-S2 algorithm is 21.76% higher than that of the S1-S2 algorithm.In terms of the annual output ofF-type products, the S1′-S2 algorithm produces 3.59 sets more than the S1-S2 algorithm, and the production efficiency is increased by 24.90%. The annual output of F-type products is obtained as the ratio of the actual working days of the enterprise in the whole year to the production cycle of a single set of F-type products. Two points need to be explained.First, the working system of the empirical enterprise is a one-day-off system; that is, there is only one day off (Sunday) every week. Based on 52 weeks in a year and deducting 11 days for China national legal holidays, we can obtain the total actual number of working days for the whole year of the empirical enterprise as follows: actual working days = 365 − 11 − 52 = 302 (days).Second, the working environment testing in the subsequent stages, which costs 56 hours, is completed continuously, so the working environment test actually takes 3 days.In terms of the annual profit value of F-type products, the S1′-S2 algorithm yields 1.436 million Yuan greater profit than the S1-S2 algorithm, and the profit margin is increased by 24.90%.The reason for the above differences is the different scheduling rules adopted in the production scheduling process. The S1-S2 algorithm isolates the two-stage production scheduling into two separate production stages, and its scheduling algorithm guarantees only the minimum of the latest completion time of each stage. The S1′-S2 algorithm regards the two-stage production scheduling as a whole and forms a link between the stages. Table4 shows that the latest completion time of the first stage of the S1′-S2 algorithm is 122 working hours and that of the S1-S2 algorithm is 120 working hours. However, in the second stage, the S1′-S2 algorithm gives priority to the assembly time and returns the information of the subsystems with long assembly times to the first stage of the production scheduling, which effectively balances the assembly capacity of each assembly workstation in the second stage. Thus, a more satisfactory solution can be obtained.


## 5.2.2. Comparative Analysis between the S1′-S2 Algorithm and the Actual Operation of the Enterprise

To verify the effectiveness of the S1′-S2 algorithm, we obtain the output ofF-type products from 2015 to 2018. The comparison results between the actual operation of the enterprise and the S1′-S2 algorithm are provided in Table 7.Table 7
Production ofF-type products in 2015–2018.
Annual output ofF-type productS1′-S2 algorithmYear201520162017201814.42Production (set)5579In Table7, the output of F-type products is the highest in 2018, reaching 9 sets. The S1′-S2 algorithm can be used to obtain 14.42 sets of annual production, which is 1.6 times the actual production in 2018. Therefore, the production capacity of F-type products is improved considerably. In view of the above situation, we analyze the following two reasons for this improvement.First, in the actual production scheduling process, enterprises usually implement production scheduling according to the production schedule. The production scheduling personnel not only are familiar with the production process of the product but also monitor the first-line production workshop to follow the production progress and take timely and effective adjustment measures to ensure that the production scheduling meets the requirements of the production schedule as much as possible. However, in the process of adjusting production scheduling, due to the different experience of production scheduling personnel, different scheduling rules will be adopted, which results in the balance of orderly production of workstations being broken. In the end, good production capacity cannot be obtained.Second, the empirical enterprise implements the time work system. Under this condition, production workers inevitably experience inertia that affects their work enthusiasm and initiative and leads to relatively low production efficiency. The S1′-S2 algorithm that we highly recommend is designed from the theoretical perspective. It eliminates the influence of human factors in the production scheduling process to improve production capacity.In summary, the effectiveness of the S1′-S2 algorithm is substantially better than that of the S1-S2 algorithm and the actual operation of enterprises, which demonstrates that the empirical enterprise can effectively improve its production capacity and earn greater profits by introducing the S1′-S2 algorithm. The S1′-S2 algorithm has good reference significance for guiding the actual production scheduling of enterprises.


## 6. Conclusions

This paper constructs a multistage production scheduling model and designs a multistage production scheduling algorithm based on sequencing theory by analyzing the relationships among production stages and optimizing each stage. Meanwhile, to verify the effectiveness of the construction model and design algorithm, we conduct numerical experiments that show that the model and algorithm constructed in this paper not only improve the production efficiency of an empirical enterprise but also provide technical support to improve production capacity.However, the paper considers only static scheduling and not dynamic scheduling. In the actual production scheduling process, it is impossible for the production personnel to work all the time. Moreover, production equipment cannot operate all the time without faults, and not all the raw materials can be delivered on time. Therefore, there are many uncertain factors in the production scheduling process. Thus, one direction of follow-up research will be to improve the adaptability of the production scheduling method.



---

*Source: 6357394-2020-07-06.xml*