# An Automatic Heuristic Design Approach for Seru Scheduling Problem with Resource Conflicts

Authors: Rongxin Zhan; Jinhui Zhang; Zihua Cui; Jin Peng; Dongni Li
Journal: Discrete Dynamics in Nature and Society
 (2021)

---

## Abstract

In current environments, production systems need the ability of quick response to face the volatile markets. Seru production systems, as a new mode of the production system, have the advantages of quick response, high flexibility, and high efficiency. Seru scheduling, which refers to constructing serus with an exact sequence in limited workspace, is an important decision problem in the operational management of seru production systems and can reflect the reconfiguration nature of seru production systems. This study investigates a seru scheduling problem with resource conflicts, whose objective is to minimize the makespan. An automatic heuristic design approach that combines a genetic programming algorithm and structure similarity-based operators is proposed. Comparative experiments are conducted with human-made rules, basic genetic programming, genetic programming-based algorithm, and with some state-of-the-art scheduling algorithms. The results show the effectiveness and efficiency of the proposed algorithm.


---

## Body

## 1. Introduction

Volatile market environments have the characteristics of short product life cycles, uncertain production types, and fluctuating production volumes [1, 2]. It is hard for traditional production systems, such as flow shop, Toyota production system, job shop, and cellular manufacturing system, to adapt to such environments. Seru production system (SPS), which is the latest innovation in production management in the Japanese manufacturing industry, is a new type of production system with quick responsiveness and high flexibility [3]. Since the 1980s, many Asian leading electronic enterprises such as Canon, Samsung, Sony, Panasonic, LG, Fujitsu, and NEC have adopted SPSs to enhance their coping ability to volatile markets [4, 5]. Roth et al. [2] reviewed the last 25 years of the growth and evolution of operations and supply chain management and noted that serus are more flexible than Toyota production systems and represent the next generation of lean. Browning and De Treville [6] also pointed out that seru can be an alternative to the TPS when meeting rapid product proliferation and highly volatile consumer demand.Many benefits, such as reducing lead time, setup time, working in process inventories, finished product inventories, cost, required workforce, and shop floor space, are gained by adopting SPSs [4, 7]. Many case studies show the significant advantages of SPSs in volatile market environments [3, 8, 9]. For example, in Nagahama Canon, six assembly lines are converted to serus. Profit had increased by 200% even though the sales had decreased from 1,300 hundred million to 1,020 hundred million Yen. The workforce and throughput time had been reduced by 10% and 33%, respectively [3, 4]. Each seru is a small, complete, and human-centered assembly unit. It consists of some cheap equipment and one or more cross-trained workers. An SPS includes at least one seru. Serus in SPSs can be frequently organized, dismantled, and rebuilt in a short time [1, 3, 4, 10, 11].The configuration problem of an SPS can be divided into two categories, i.e., seru formation [12] and seru scheduling [13]. Seru formation means grouping workers into serus and determining their tasks according to the arrived orders [12]. Seru scheduling refers to constructing serus with an exact sequence in limited workspace [13].Many studies focused on seru formation [12, 14–17]. For example, Yu et al. proposed an algorithm based on the nondominated sorting genetic algorithm 2 (NSGA-II) to solve the problem of line-to-seru conversion problem whose objectives are minimizing total throughput time and total labor hours [12]. Yu et al. investigated a seru formation problem toward reducing workers and developed exact and metaheuristic algorithms for the small- to medium-scale instances [16]. Yu et al. considered a line-hybrid seru formation problem by combining the two evaluated performances, i.e., makespan and total labor hours. Exact and heuristic algorithms are proposed to solve the different scale instances [17].For seru scheduling, there are few studies [13, 18]. Yu et al. selected ten usually used scheduling rules to investigate the performance of different rules on the line-seru conversion problem. Two improved exact algorithms based on reducing time complexity and space complexity are proposed [13]. Sun et al. focused on a seru scheduling problem with minimizing the total tardiness and analysed the solution space. They proposed a cooperative coevolution algorithm for large-scale problems and an exact algorithm for small-scale problems [18].Most of the above studies have the following assumptions: (1) once serus are constructed, they never change; and (2) workers are fully cross-trained. However, to cope with volatile markets, SPSs should be more flexible and quick responsive than traditional production systems. Just-in-time operation system (JIT-OS) [4], whose goal is configuring correct serus, in the right place, at the appropriate time, and in the exact amount, is proposed as the management and control principle of SPSs. Following this principle, serus should be built up over time rather than fixed. Besides, in real production environments, as an important characteristic and central resource, human workers cannot be neglected and it is hard to achieve that all workers are fully cross-trained. Therefore, if some serus require the same worker, these serus cannot be built simultaneously.Based on the above consideration, the seru scheduling problem can be seen as a complex variant of the parallel machine scheduling (PMS) problem [5, 19]. Some studies took PMS with resource constraints into consideration [20–22]. Though resource constraints are considered in the above studies, they assumed that the resources are extra resources, which are needed by machines or workers to be able to function. The lack of special resources leads to a lot of waiting time. The above waiting time cannot be reduced by changing the production planning. In our model, the waiting time is caused by human workers needed by different serus and can be reduced by optimizing the scheduling.Seru scheduling with resource (human workers) conflicts (SSRC) is considered in this study. First, this is an important decision problem in operation management in SPSs, which can reveal the nature of reconfiguration ability and quick response ability of SPSs. Second, from a model perspective, it is a new and realistic variant of the PMS problem.The contributions of this study are as follows. First, to our knowledge, this is the first work addressing the seru scheduling problem with the consideration of human resource conflicts. Second, genetic programming with structure similarity-based operators (GP-SS), which considers special attributes of the seru scheduling problem, is proposed to automatically generate effective rules to effectively and efficiently solve the SSRC. Third, comparative experiments conducted with human-made rules, basic genetic programming (GP), GP-based algorithm, and state-of-the-art algorithms verify the effectiveness of GP-SS.The rest of this study is organized as follows. Section2 describes addressed SSRC problem. The proposed GP-SS is presented in Section 3. Comparative results are shown in Section 4. Section 5 concludes the study in the end.


## 2. Seru Scheduling Problem with Resource Conflicts

In this study, the SSRC problem is proposed as to how to arrange the sequence of constructing serus with resource conflicts under limited spaces. In particular, a SPS is considered in a manufacturing firm. This firm has some locations to configure serus, and each location can accommodate one seru at a time. When several orders come, serus should be configured to finish these orders. Resource conflicts may exist within some serus, so they cannot be built simultaneously. The sequence of constructing serus should be determined to minimize the makespan of these orders. The proposed problem can be described as follows.


### 2.1. Assumptions

The SSRC addressed in this study is based on the following assumptions.(1)
The information (arrival times and seru(s) that configured for each order) of orders over a period of time is known when a time period starts. The arrival time of orders may be different.(2)
For every single order, at least one seru should be configured and the information (numbers, life cycles, and conflicts with other serus) of seru(s) for each order is predetermined.(3)
Serus that needs the same worker(s) cannot be built simultaneously.(4)
The build time and dismantle time of serus are neglected.(5)
The number of spaces in a seru production system is limited, and one space accommodates only one seru at a time.


### 2.2. Notations

The notations adopted to describe the addressed problem are presented below.


#### 2.2.1. Indices

The following indices were used in this study:o=1,2,O: index of ordersi=1,2,I: index of serusl=1,2,L: index of the spaces to accommodate serust=1,2,T: time


#### 2.2.2. Parameters

The following parameters were used in this study:ato: arrival time of order, oSo: set of serus that configured for order, and oti: life cycle of seru i from being constructed to dismantledvii′=1,serusiandi¢have the resource conflict,0,otherwise


#### 2.2.3. Decision Variables

The following decision variables were used in this study:sti: start time of seru i.xil=1,seruiis built in spacel,0,otherwise


### 2.3. Formulation of Seru Scheduling with Resource Conflicts

Seru scheduling with resource conflicts can be formulated using equations (1)–(4).


#### 2.3.1. Objective Function

The objective function(1)minCmaxis subject to(2)∑lLxil=1,∀i,(3)∑iItixil≤Cmax,∀l,(4)sti≥sti′+ti′orsti′≥sti+ti,ifvii′=1.Equation (1) states that the objective of the addressed problem is to minimize the makespan of orders in the same time period. Cmax=maxsti+ti,∀i, which is the amount of time to process all coming orders. Constraint (2) ensures that each seru is exactly built in one space. Constraint (3) ensures that the makespan is at least as large as the total life cycles of serus built in each space. Constraint (4) means that serus i and i’ cannot be built simultaneously.


### 2.4. Model Complexity

In this section, the NP-hardness of SSRC is proved as follows.Theorem 1.
SSRC is NP-hard.Proof.
The PMS problem is a classic NP-hard problem. We reduce any instance of the PMS problem to an instance of SSRC. The PMS problem can be described as follows.
Given a set of jobs,Jobs=1,H, each h∈Jobs is characterized by a release time fh and a processing time vh. These jobs are scheduled on M machines, and preemption is not allowed. The target is to minimize the makespan.
Letsti=fh ands ti=vh, where i=h, I=H, L=M. Obviously, a seru is the same as a job in PMS and a location is the same as a machine in PMS. When the solution of the PMS instance is found, the corresponding instance of SSRC can be solved. Thus, the addressed SSRC problem in this study is NP-hard.


## 2.1. Assumptions

The SSRC addressed in this study is based on the following assumptions.(1)
The information (arrival times and seru(s) that configured for each order) of orders over a period of time is known when a time period starts. The arrival time of orders may be different.(2)
For every single order, at least one seru should be configured and the information (numbers, life cycles, and conflicts with other serus) of seru(s) for each order is predetermined.(3)
Serus that needs the same worker(s) cannot be built simultaneously.(4)
The build time and dismantle time of serus are neglected.(5)
The number of spaces in a seru production system is limited, and one space accommodates only one seru at a time.


## 2.2. Notations

The notations adopted to describe the addressed problem are presented below.


### 2.2.1. Indices

The following indices were used in this study:o=1,2,O: index of ordersi=1,2,I: index of serusl=1,2,L: index of the spaces to accommodate serust=1,2,T: time


### 2.2.2. Parameters

The following parameters were used in this study:ato: arrival time of order, oSo: set of serus that configured for order, and oti: life cycle of seru i from being constructed to dismantledvii′=1,serusiandi¢have the resource conflict,0,otherwise


### 2.2.3. Decision Variables

The following decision variables were used in this study:sti: start time of seru i.xil=1,seruiis built in spacel,0,otherwise


## 2.2.1. Indices

The following indices were used in this study:o=1,2,O: index of ordersi=1,2,I: index of serusl=1,2,L: index of the spaces to accommodate serust=1,2,T: time


## 2.2.2. Parameters

The following parameters were used in this study:ato: arrival time of order, oSo: set of serus that configured for order, and oti: life cycle of seru i from being constructed to dismantledvii′=1,serusiandi¢have the resource conflict,0,otherwise


## 2.2.3. Decision Variables

The following decision variables were used in this study:sti: start time of seru i.xil=1,seruiis built in spacel,0,otherwise


## 2.3. Formulation of Seru Scheduling with Resource Conflicts

Seru scheduling with resource conflicts can be formulated using equations (1)–(4).


### 2.3.1. Objective Function

The objective function(1)minCmaxis subject to(2)∑lLxil=1,∀i,(3)∑iItixil≤Cmax,∀l,(4)sti≥sti′+ti′orsti′≥sti+ti,ifvii′=1.Equation (1) states that the objective of the addressed problem is to minimize the makespan of orders in the same time period. Cmax=maxsti+ti,∀i, which is the amount of time to process all coming orders. Constraint (2) ensures that each seru is exactly built in one space. Constraint (3) ensures that the makespan is at least as large as the total life cycles of serus built in each space. Constraint (4) means that serus i and i’ cannot be built simultaneously.


## 2.3.1. Objective Function

The objective function(1)minCmaxis subject to(2)∑lLxil=1,∀i,(3)∑iItixil≤Cmax,∀l,(4)sti≥sti′+ti′orsti′≥sti+ti,ifvii′=1.Equation (1) states that the objective of the addressed problem is to minimize the makespan of orders in the same time period. Cmax=maxsti+ti,∀i, which is the amount of time to process all coming orders. Constraint (2) ensures that each seru is exactly built in one space. Constraint (3) ensures that the makespan is at least as large as the total life cycles of serus built in each space. Constraint (4) means that serus i and i’ cannot be built simultaneously.


## 2.4. Model Complexity

In this section, the NP-hardness of SSRC is proved as follows.Theorem 1.
SSRC is NP-hard.Proof.
The PMS problem is a classic NP-hard problem. We reduce any instance of the PMS problem to an instance of SSRC. The PMS problem can be described as follows.
Given a set of jobs,Jobs=1,H, each h∈Jobs is characterized by a release time fh and a processing time vh. These jobs are scheduled on M machines, and preemption is not allowed. The target is to minimize the makespan.
Letsti=fh ands ti=vh, where i=h, I=H, L=M. Obviously, a seru is the same as a job in PMS and a location is the same as a machine in PMS. When the solution of the PMS instance is found, the corresponding instance of SSRC can be solved. Thus, the addressed SSRC problem in this study is NP-hard.


## 3. Methodology

In this section, GP-SS is proposed to solve the addressed SSRC problem. Studies on seru scheduling employed heuristic rules [13, 18] in which problem instances are small scale. In industrial environments, heuristic rules are often used due to simplicity and efficiency [23, 24]. Though efficient heuristic rules can bring many benefits for manufacturing, they also may lead to malfunctions because of the limitation of human experiences. Besides, the performance of heuristic rules heavily depends on the environments and objectives. For each single heuristic rule, no one can outperform others in all circumstances [23].Genetic programming (GP) is a kind of technology, which can strongly generate heuristic rules based on specific problem attributes. Because of its high efficiency and generalization ability, GP is used to evolve heuristics in many scheduling domains, such as single machine scheduling [25–27], job shop scheduling [28–32], flow shop scheduling [33], and airplane scheduling [34, 35]. In recent years, GP is also used to solve the PMS problem [36–38]. However, GP has several drawbacks. First, in the evolutionary process, the tree-structured individuals are changed frequently by operations of mutation and crossover, which may lead to large and complex individuals but with poor quality. Thus, GP may waste a lot of computing time in exploiting good solutions. Second, basic operators may not be powerful enough to help GP search for good enough solutions, which means that GP is easy to be trapped into local optima.Similarity-based crossover operator is a kind of improved special operator in GP, which performs well in real-valued function regression problem [39, 40]. Its design concept in the above studies is that exchange of subtrees is most likely to get benefits if the two subtrees are semantically similar, which means that they are not semantically identical, but also they are not too semantically dissimilar. Semantic similarity refers to the difference value of fitness between two subtrees obtained by sampling methods. It is verified to be a useful strategy to improve the performance of GP and to shorten the sizes of tree-structured individuals. However, in continuous optimization, such as real-valued function regression problem, it requires very little computing time cost to calculate fitness when compared to scheduling problems. Such a method cannot be directly used to discrete GP to obtain similar benefits. It always uses less time to compare the structure similarity between two subtrees when compared with calculating the fitness. Therefore, in this study, GP with structure similarity-based operators (GP-SS) is proposed to generate effective rules to solve SSRC.


### 3.1. Framework of GP-SS

The evolutionary process of GP-SS is shown in Figure1. At first, the initial population consisting of tree-structured individuals is randomly generated. Then, the fitness of individuals is calculated and the good ones are selected by using the roulette wheel method to generate the next generation. The structure similarity-based crossover and mutation operators are adopted to improve the optimization ability and convergence speed of GP-SS. Finally, the termination criterion is used to determine whether to terminate the algorithm.Figure 1
Framework of the GP-SS.


### 3.2. Fitness Calculation of GP-SS

In GP-SS, as in basic GP, tree-structured individuals are used. In each individual, its root nodes represent function operators and leaf nodes represent an element in the terminal set. The terminals that are derived from the SSRC problem are shown in Table1. The function set includes addition (ADD), subtraction (SUB), protected division (DIV), and multiplication (MUL). The function set and terminal set are used to rank serus. The individual SUB (AT, ET) is taken as an example. There are two serus, seru 1 and seru 2, that need to be scheduled. It is assumed that these two serus are both built for one order and that the “AT” attributes of these two serus (arrival time) are set to 100. The “ET” attributes of serus 1 and 2 (life cycle) are set to 50 and 30, respectively. The rule derived from the individual is AT-ET. Thus, the scores of serus 1 and 2 are (100-50) = 50 and (100-30) = 70, respectively. Because the score of seru 1 (50) is less than the score of seru 2 (70), the built sequence of serus 1 and 2 is as follows: seru 1 is prior to seru 2. Then, the fitness of this schedule can be calculated by using equation (1).Table 1
Terminals for the SSRC problem.
SymbolDescriptionATArrival time of an order that a seru is configured forETLife cycle of a seruCFLNumber of current free spacesWWeight of a seruOFA number of serus that are overlapped with a seruCTCurrent time#Random number between 0 and 1


### 3.3. Structure Similarity-Based Operators

In GP-SS, structure similarity-based operators are inspired by similarity-based crossover operator designed for real-valued function regression problem [39, 40]. In order to be suitable for solving discrete optimization problems, a similarity coefficient is proposed in this study, which replaces the similar distance in continuous optimization.Letsscst1,st2 be the structure similarity coefficient between subtree 1, st1, and subtree 2, st2. ast1u and ast2u are defined as the number of u−th attribute of N (according to Table 1, N=7 in this study) attributes in subtrees 1 and 2, respectively. Therefore, sscst1,st2 can be defined by Algorithm 1.Algorithm 1: Determination of the similarity between subtrees 1 and 2.
(1)
:ifst1 and st2 meet the following conditions:(2)
: condition 1: the layer difference between two trees is less thanγ(3)
: condition 2:α<∑nNast1u−ast2u/N<βthen(4)
:sscst1,st2=1(5)
:else(6)
:sscst1,st2=−1(7)
:end ifIn Algorithm1, α, β, and γ are parameters in GP-SS, known as the lower bound for attributes’ similarity sensitivity, the upper bound for attributes’ similarity sensitivity, and the upper bound for layer difference, respectively. sscst1,st2=1 means st1 is similar to st2.The layer difference between the two treesst1 and st2 is defined as follows:(5)ldst1,st2=lst1−lst2,where ldst1,st2 is the layer difference between st1 and st2. lst1 and lst2 are the layers of st1 and st2, respectively. The layer of a tree can be calculated by traversing the tree.For example, Figure2 shows two subtrees st1 and st2. st1 can be transformed into AT+ET−#/OF, and st2 can be transformed into W/CFL+AT by in order traversal of these two trees, respectively. The layers of these two subtrees are 4 and 3, so the layer difference between st1 and st2 is 1.Figure 2
Example of two subtrees. (a)st1. (b) st2.Based on the above definition of structure similarity coefficient, the structure similarity-based crossover and mutation can be defined by Algorithms2 and 3, respectively.Algorithm 2: Structure similarity-based crossover.
(1)
:whilecount<attemptLimitdo(2)
: Randomly choose the crossover points to generatest1 and st2(3)
:ifst1 is similar to st2: then(4)
:  crossover and add the children to the new population(5)
:  addst1 and st2 into a list listsimilarity(6)
:  return 0(7)
:else(8)
:count++(9)
:end if(10)
:end while(11)
: crossoverIn Algorithm2, attemptLimit is the upper limit of attempts to find similar subtrees and listsimilarity is a list can be used in structure similarity-based mutation (listsimilarity is set to be empty at each end of generation). In this process, if the pair of similar subtrees is not found, structure similarity-based crossover is degenerated to classic crossover.Algorithm 3: Structure similarity-based mutation.
(1)
:ifrandomSeed<randomPara and listsimilarity is not empty then(2)
: mutate to a randomly chosen subtree inlistsimilarity(3)
:else(4)
: mutation(5)
:end ifIn Algorithm3, randomPara is the upper limit parameter that controls the structure similarity-based mutation probability. In the process of structure similarity-based mutation, if randomSeed is out of predefined range or listsimilarity is empty, the structure similarity-based mutation is degenerated to classic mutation.


### 3.4. Computational Complexity Analysis

In this section, the complexity analysis of proposed structure similarity-based operators is given. For any pair of subtrees, suppose that the numbers of their nodes arem and n, the time complexity of Algorithm 1, which traverses all nodes of two subtrees several times, is Om+n. Thus, the time complexity of proposed structure similarity-based operators is Om+n.


## 3.1. Framework of GP-SS

The evolutionary process of GP-SS is shown in Figure1. At first, the initial population consisting of tree-structured individuals is randomly generated. Then, the fitness of individuals is calculated and the good ones are selected by using the roulette wheel method to generate the next generation. The structure similarity-based crossover and mutation operators are adopted to improve the optimization ability and convergence speed of GP-SS. Finally, the termination criterion is used to determine whether to terminate the algorithm.Figure 1
Framework of the GP-SS.


## 3.2. Fitness Calculation of GP-SS

In GP-SS, as in basic GP, tree-structured individuals are used. In each individual, its root nodes represent function operators and leaf nodes represent an element in the terminal set. The terminals that are derived from the SSRC problem are shown in Table1. The function set includes addition (ADD), subtraction (SUB), protected division (DIV), and multiplication (MUL). The function set and terminal set are used to rank serus. The individual SUB (AT, ET) is taken as an example. There are two serus, seru 1 and seru 2, that need to be scheduled. It is assumed that these two serus are both built for one order and that the “AT” attributes of these two serus (arrival time) are set to 100. The “ET” attributes of serus 1 and 2 (life cycle) are set to 50 and 30, respectively. The rule derived from the individual is AT-ET. Thus, the scores of serus 1 and 2 are (100-50) = 50 and (100-30) = 70, respectively. Because the score of seru 1 (50) is less than the score of seru 2 (70), the built sequence of serus 1 and 2 is as follows: seru 1 is prior to seru 2. Then, the fitness of this schedule can be calculated by using equation (1).Table 1
Terminals for the SSRC problem.
SymbolDescriptionATArrival time of an order that a seru is configured forETLife cycle of a seruCFLNumber of current free spacesWWeight of a seruOFA number of serus that are overlapped with a seruCTCurrent time#Random number between 0 and 1


## 3.3. Structure Similarity-Based Operators

In GP-SS, structure similarity-based operators are inspired by similarity-based crossover operator designed for real-valued function regression problem [39, 40]. In order to be suitable for solving discrete optimization problems, a similarity coefficient is proposed in this study, which replaces the similar distance in continuous optimization.Letsscst1,st2 be the structure similarity coefficient between subtree 1, st1, and subtree 2, st2. ast1u and ast2u are defined as the number of u−th attribute of N (according to Table 1, N=7 in this study) attributes in subtrees 1 and 2, respectively. Therefore, sscst1,st2 can be defined by Algorithm 1.Algorithm 1: Determination of the similarity between subtrees 1 and 2.
(1)
:ifst1 and st2 meet the following conditions:(2)
: condition 1: the layer difference between two trees is less thanγ(3)
: condition 2:α<∑nNast1u−ast2u/N<βthen(4)
:sscst1,st2=1(5)
:else(6)
:sscst1,st2=−1(7)
:end ifIn Algorithm1, α, β, and γ are parameters in GP-SS, known as the lower bound for attributes’ similarity sensitivity, the upper bound for attributes’ similarity sensitivity, and the upper bound for layer difference, respectively. sscst1,st2=1 means st1 is similar to st2.The layer difference between the two treesst1 and st2 is defined as follows:(5)ldst1,st2=lst1−lst2,where ldst1,st2 is the layer difference between st1 and st2. lst1 and lst2 are the layers of st1 and st2, respectively. The layer of a tree can be calculated by traversing the tree.For example, Figure2 shows two subtrees st1 and st2. st1 can be transformed into AT+ET−#/OF, and st2 can be transformed into W/CFL+AT by in order traversal of these two trees, respectively. The layers of these two subtrees are 4 and 3, so the layer difference between st1 and st2 is 1.Figure 2
Example of two subtrees. (a)st1. (b) st2.Based on the above definition of structure similarity coefficient, the structure similarity-based crossover and mutation can be defined by Algorithms2 and 3, respectively.Algorithm 2: Structure similarity-based crossover.
(1)
:whilecount<attemptLimitdo(2)
: Randomly choose the crossover points to generatest1 and st2(3)
:ifst1 is similar to st2: then(4)
:  crossover and add the children to the new population(5)
:  addst1 and st2 into a list listsimilarity(6)
:  return 0(7)
:else(8)
:count++(9)
:end if(10)
:end while(11)
: crossoverIn Algorithm2, attemptLimit is the upper limit of attempts to find similar subtrees and listsimilarity is a list can be used in structure similarity-based mutation (listsimilarity is set to be empty at each end of generation). In this process, if the pair of similar subtrees is not found, structure similarity-based crossover is degenerated to classic crossover.Algorithm 3: Structure similarity-based mutation.
(1)
:ifrandomSeed<randomPara and listsimilarity is not empty then(2)
: mutate to a randomly chosen subtree inlistsimilarity(3)
:else(4)
: mutation(5)
:end ifIn Algorithm3, randomPara is the upper limit parameter that controls the structure similarity-based mutation probability. In the process of structure similarity-based mutation, if randomSeed is out of predefined range or listsimilarity is empty, the structure similarity-based mutation is degenerated to classic mutation.


## 3.4. Computational Complexity Analysis

In this section, the complexity analysis of proposed structure similarity-based operators is given. For any pair of subtrees, suppose that the numbers of their nodes arem and n, the time complexity of Algorithm 1, which traverses all nodes of two subtrees several times, is Om+n. Thus, the time complexity of proposed structure similarity-based operators is Om+n.


## 4. Computational Results and Comparison

To evaluate the performance of the proposed GP-SS algorithm, a series of comparisons are conducted in this section. The GP-SS and other comparison algorithms are shown in Table2. All experiments are performed on a PC with the i5-10600 processor (4.1 GHz) and 16 GB RAM.Table 2
Description of GP-SS and comparison algorithms.
AlgorithmDescriptionGP-SSThis algorithm performs GP with structure similarity-based operators to generate heuristic rulesHuman-made rulesRules are selected from previous studies and are specially designed for SSRCBasic GPThis algorithm performs GP to generate heuristic rulesGP-HHThis algorithm performs GP with a predesigned low-level heuristics set to generate heuristic rulesGRASP-VNSGreedy randomized adaptive search procedure with variable neighborhood searchIGAGenetic algorithm with improved crossover operators and elitism selection mechanismThe test problems are generated by setting three important dimensions, which are orders, serus types, and spaces. The number of orders is ranging from 5 to 60, the number of seru types is ranging from 5 to 48, and the number of spaces is ranging from 3 to 35. A notation “3-2-1” is used to represent a test problem with 3 orders, 2 types of serus, and 1 space. For each test problem, 20 independent replications are tested to get the results. Training set and test set are designed to try to overcome overfitting. In the training set, 4 test problems are designed to train the parameters of GP-SS and all comparison algorithms. In the test set, 12 test problems are chosen. All the comparison experiments are run on the test set.TheGapx, which is calculated in equation (6), is defined in this section to reflect the performance of GP-SS. This gap is the percentage deviation between the average objective function values obtained by the GP-SS algorithm and the x algorithm for 20 independent replications.(6)Gapx=100∗scorex−scoreGP−SSscoreGP−SS,where scorex and scoreGP−SS represent the objective function values obtained by the x algorithm and GP-SS, respectively.


### 4.1. Parameter Setting

According to the parameter experiments, the parameter values in Table3 for GP-SS are set as default in the following experiments. Parameters of all comparison algorithms are also trained on the training set.Table 3
Parameters for GP-SS.
ParameterValueα0.01β0.3γ3attemptLimit5randomPara0.4Population size48Number of generations100


### 4.2. Comparison Experiments

To evaluate the performance of GP-SS, 4 groups of experiments are conducted. First, in the previous seru formation and scheduling studies, due to simplicity and efficiency, human-made rules are the most used approach. Therefore, 7 rules are selected to be compared with rules that are generated by GP-SS. Second, to verify the effects of the proposed structure similarity-based operators, GP-SS is compared with basic GP. Third, an excellent variant of GP in the scheduling domain [41], genetic programming hyperheuristic (GP-HH), is chosen to be compared with GP-SS. Finally, two state-of-the-art algorithms designed for PMS, greedy randomized adaptive search procedure with variable neighborhood search (GRASP-VNS) [42] and improved genetic algorithm (IGA) [43], are also chosen to evaluate the performance of our proposed GP-SS.


#### 4.2.1. Comparison with Human-Made Rules

To compare with GP-SS, 5 human-made rules selected from previous studies and 2 special rules designed for SSRC are used. These rules are shown in Table4.Table 4
Seven rules to be compared with GP-SS.
RuleDescriptionFCFSFirst come first serviceLPTLongest life cycle seru firstSPTShortest life cycle seru firstECTEarliest completion time seru firstSHRandomly sequenced serusHCHighest conflict factor seru firstLCLowest conflict factor seru firstAs shown in Table5, for all test problems, GP-SS outperforms the human-made rules with the range from 5.82% to 133.31%. The reason that GP-SS is superior to human-made rules lies in that human-made rules are predesigned. They can be used in many scheduling domain but cannot be universally good. Rules from GP-SS are specifically evolved for SSRC and can naturally achieve better performance.Table 5
Comparison with human-made rules.
Test problemGapFCFS (%)GapLPT (%)GapSPT (%)GapECT (%)GapSH (%)GapHC (%)GapLC (%)5−5−326.9736.5415.5313.6414.2712.3932.7710−8−540.859.0216.0516.7825.315.8248.7515−12−828.3539.1012.6713.5231.556.2446.0020−15−1015.5647.0121.9418.4125.2910.3578.3825−18−1234.7642.2713.6320.5433.918.3869.7930−21−1524.6545.1111.7519.2829.3514.5585.4535−25−1843.4424.3916.8815.6717.0812.0944.0340−30−2020.5865.7221.2422.9135.6414.4773.0545−30−2343.8929.3317.2617.8634.1117.8384.5650−42−2742.0246.1017.6421.1434.399.2794.8555−45−3059.6132.5416.4929.2045.3713.16133.3160−48−3541.3969.1921.6526.9345.0214.5076.28Average gap35.1744.6916.8919.6630.9411.5972.27


#### 4.2.2. Effects of Structure Similarity-Based Operators

To evaluate the performance of structure similarity-based operators, a comparison between GP-SS and basic GP is conducted. The results are shown in Table6.Table 6
Comparison with basic GP.
Test problemGapbasicGP (%)MinAvgTime5−5−35.5224.73−0.0310−8−54.4920.38−2.3115−12−86.8530.871.5320−15−107.4121.451.1825−18−1212.3635.31−1.5830−21−157.1526.692.7335−25−1813.2023.21−0.6440−30−207.9336.352.9345−30−238.4924.51−5.3150−42−2713.5428.89−3.0755−45−307.5226.841.5260−48−359.7322.731.61Average gap8.6826.83−0.12As shown in Table6, for best cases, GP-SS outperforms GP with an average gap of 8.68%. For the average cases, GP-SS outperforms GP with the gap ranging from 20.38% to 36.35%. For the computing time, GP-SS is similar to GP with an average gap of −0.12%. The above results verify that GP-SS is more effective than GP. The reason lies in that some subtrees or structures in individuals may have better effects than others. If these subtrees or structures can be found in the evolutionary process, it can help the algorithm enhance the optimization ability and convergence speed. The design concept of the proposed structure similarity-based operators is giving GP-SS a mechanism to search for a similar structure. Due to the design of two-attempt limit parameters, GP-SS also has the ability to jump from local optimal.To further analyze the quick convergence ability of GP-SS, an evolving process from a test problem in the test set is recorded in Figure3. The vertical and abscissa axes in Figure 3 represent fitness and the index of generation, respectively. It is easy to observe that GP-SS has a faster convergence speed and a better performance. This result can also help to verify the ability to search good regions of GP-SS.Figure 3
Evolving process of GP-SS and GP.


#### 4.2.3. Comparison with GP-Based Algorithm

GP-HH is a hyperheuristic algorithm that employs GP as the high-level strategy to manage several predefined low-level heuristics [41]. The comparison between GP-SS and GP-HH is conducted in this section. The results are shown in Table 7.Table 7
Comparison with GP-HH.
Test problemGapGP−HH (%)MinAvgTime5−5−32.9520.500.7310−8−54.6130.911.6115−12−82.8322.942.8720−15−103.259.561.1925−18−129.6719.033.8530−21−157.1118.654.5435−25−182.3424.372.1940−30−204.707.383.7845−30−235.0314.636.0950−42−2713.7323.705.8155−45−304.9716.617.9260−48−355.2231.6410.86Average gap5.5319.994.29As shown in Table7, for the best cases, the gap between GP-SS and GP-HH ranges from 2.34% to 13.73%, with an average gap of 5.53%. For the average cases, GP-SS outperforms GP-HH with an average gap of 19.99%. For the computing time, GP-SS outperforms GP-HH with an average gap of 4.29%. The results show that GP-SS is more effective and efficient than GP-HH. The reason lies in that low-level heuristics have a high impact on the performance of GP-HH. Without good enough heuristics that are specially designed for SSRC, GP-HH cannot perform much better than basic GP. Therefore, due to the good convergence ability, GP-SS is superior to GP-HH.


### 4.3. Comparison with Other PMS Scheduling Algorithms

GRASP-VNS [42] and IGA [43] are two recent state-of-the-art algorithms designed for the PMS problem. These two algorithms are compared with GP-SS, and the results are shown in Table 8.Table 8
Comparison with GRASP-VNS and IGA.
Test problemGapGRASP−VNS (%)GapIGA (%)MinAvgminAvg5−5−30.00−0.910.001.3010−8−50.000.050.006.2215−12−80.000.710.000.9320−15−100.003.251.427.3125−18−120.69−0.581.265.2230−21−151.843.930.387.0835−25−181.432.761.956.9740−30−202.615.592.468.4245−30−231.603.683.046.2150−42−273.137.205.685.8755−45−302.172.303.553.0760−48−352.731.993.435.94Average gap1.352.501.935.38As shown in Table8, for the best cases, GP-SS performs a little better than GRASP-VNS and IGA with an average gap of 1.35% and 1.93%, respectively. For the average cases, GP-SS outperforms GRASP-VNS and IGA with an average gap of 2.50% and 5.38%, respectively. These results show that, based on the training process on the specific problem and structure similarity-based operators, GP-SS can achieve a slight advantage over other PMS scheduling algorithms.Meanwhile, the computing time of GP-SS is the sum of the time of generating rules on a training set and applying rules on all test problems. The computing time of GRASP-VNS and IGA is the sum of the time of independently running the algorithm on all test problems. Therefore, the computing time that is compared in this section is set as the above settings. Because of the big difference in computing time among these three types of algorithms, the gap that shows the percentage deviation between GP-SS and each compared algorithm is given as follows.(7)Gaptimex=100∗timex−timeGP−SStimex,where timex and timeGP−SS represent the computing time obtained by the x algorithm and GP-SS, respectively.The results are shown in Table9. It is observed that GP-SS outperforms GRASP-VNS and IGA with the gap of 64.04% and 73.21%, respectively. This result verifies the efficiency of the proposed GP-SS. The reason lies in that GRASP-VNS and IGA need to search the solution space for each test problem. However, GP-SS just needs to search on the training set.Table 9
The computing time of each m.
ExperimentGaptime (%)GP-SS vs. GRASP-VNS64.04GP-SS vs. IGA73.21


## 4.1. Parameter Setting

According to the parameter experiments, the parameter values in Table3 for GP-SS are set as default in the following experiments. Parameters of all comparison algorithms are also trained on the training set.Table 3
Parameters for GP-SS.
ParameterValueα0.01β0.3γ3attemptLimit5randomPara0.4Population size48Number of generations100


## 4.2. Comparison Experiments

To evaluate the performance of GP-SS, 4 groups of experiments are conducted. First, in the previous seru formation and scheduling studies, due to simplicity and efficiency, human-made rules are the most used approach. Therefore, 7 rules are selected to be compared with rules that are generated by GP-SS. Second, to verify the effects of the proposed structure similarity-based operators, GP-SS is compared with basic GP. Third, an excellent variant of GP in the scheduling domain [41], genetic programming hyperheuristic (GP-HH), is chosen to be compared with GP-SS. Finally, two state-of-the-art algorithms designed for PMS, greedy randomized adaptive search procedure with variable neighborhood search (GRASP-VNS) [42] and improved genetic algorithm (IGA) [43], are also chosen to evaluate the performance of our proposed GP-SS.


### 4.2.1. Comparison with Human-Made Rules

To compare with GP-SS, 5 human-made rules selected from previous studies and 2 special rules designed for SSRC are used. These rules are shown in Table4.Table 4
Seven rules to be compared with GP-SS.
RuleDescriptionFCFSFirst come first serviceLPTLongest life cycle seru firstSPTShortest life cycle seru firstECTEarliest completion time seru firstSHRandomly sequenced serusHCHighest conflict factor seru firstLCLowest conflict factor seru firstAs shown in Table5, for all test problems, GP-SS outperforms the human-made rules with the range from 5.82% to 133.31%. The reason that GP-SS is superior to human-made rules lies in that human-made rules are predesigned. They can be used in many scheduling domain but cannot be universally good. Rules from GP-SS are specifically evolved for SSRC and can naturally achieve better performance.Table 5
Comparison with human-made rules.
Test problemGapFCFS (%)GapLPT (%)GapSPT (%)GapECT (%)GapSH (%)GapHC (%)GapLC (%)5−5−326.9736.5415.5313.6414.2712.3932.7710−8−540.859.0216.0516.7825.315.8248.7515−12−828.3539.1012.6713.5231.556.2446.0020−15−1015.5647.0121.9418.4125.2910.3578.3825−18−1234.7642.2713.6320.5433.918.3869.7930−21−1524.6545.1111.7519.2829.3514.5585.4535−25−1843.4424.3916.8815.6717.0812.0944.0340−30−2020.5865.7221.2422.9135.6414.4773.0545−30−2343.8929.3317.2617.8634.1117.8384.5650−42−2742.0246.1017.6421.1434.399.2794.8555−45−3059.6132.5416.4929.2045.3713.16133.3160−48−3541.3969.1921.6526.9345.0214.5076.28Average gap35.1744.6916.8919.6630.9411.5972.27


### 4.2.2. Effects of Structure Similarity-Based Operators

To evaluate the performance of structure similarity-based operators, a comparison between GP-SS and basic GP is conducted. The results are shown in Table6.Table 6
Comparison with basic GP.
Test problemGapbasicGP (%)MinAvgTime5−5−35.5224.73−0.0310−8−54.4920.38−2.3115−12−86.8530.871.5320−15−107.4121.451.1825−18−1212.3635.31−1.5830−21−157.1526.692.7335−25−1813.2023.21−0.6440−30−207.9336.352.9345−30−238.4924.51−5.3150−42−2713.5428.89−3.0755−45−307.5226.841.5260−48−359.7322.731.61Average gap8.6826.83−0.12As shown in Table6, for best cases, GP-SS outperforms GP with an average gap of 8.68%. For the average cases, GP-SS outperforms GP with the gap ranging from 20.38% to 36.35%. For the computing time, GP-SS is similar to GP with an average gap of −0.12%. The above results verify that GP-SS is more effective than GP. The reason lies in that some subtrees or structures in individuals may have better effects than others. If these subtrees or structures can be found in the evolutionary process, it can help the algorithm enhance the optimization ability and convergence speed. The design concept of the proposed structure similarity-based operators is giving GP-SS a mechanism to search for a similar structure. Due to the design of two-attempt limit parameters, GP-SS also has the ability to jump from local optimal.To further analyze the quick convergence ability of GP-SS, an evolving process from a test problem in the test set is recorded in Figure3. The vertical and abscissa axes in Figure 3 represent fitness and the index of generation, respectively. It is easy to observe that GP-SS has a faster convergence speed and a better performance. This result can also help to verify the ability to search good regions of GP-SS.Figure 3
Evolving process of GP-SS and GP.


### 4.2.3. Comparison with GP-Based Algorithm

GP-HH is a hyperheuristic algorithm that employs GP as the high-level strategy to manage several predefined low-level heuristics [41]. The comparison between GP-SS and GP-HH is conducted in this section. The results are shown in Table 7.Table 7
Comparison with GP-HH.
Test problemGapGP−HH (%)MinAvgTime5−5−32.9520.500.7310−8−54.6130.911.6115−12−82.8322.942.8720−15−103.259.561.1925−18−129.6719.033.8530−21−157.1118.654.5435−25−182.3424.372.1940−30−204.707.383.7845−30−235.0314.636.0950−42−2713.7323.705.8155−45−304.9716.617.9260−48−355.2231.6410.86Average gap5.5319.994.29As shown in Table7, for the best cases, the gap between GP-SS and GP-HH ranges from 2.34% to 13.73%, with an average gap of 5.53%. For the average cases, GP-SS outperforms GP-HH with an average gap of 19.99%. For the computing time, GP-SS outperforms GP-HH with an average gap of 4.29%. The results show that GP-SS is more effective and efficient than GP-HH. The reason lies in that low-level heuristics have a high impact on the performance of GP-HH. Without good enough heuristics that are specially designed for SSRC, GP-HH cannot perform much better than basic GP. Therefore, due to the good convergence ability, GP-SS is superior to GP-HH.


## 4.2.1. Comparison with Human-Made Rules

To compare with GP-SS, 5 human-made rules selected from previous studies and 2 special rules designed for SSRC are used. These rules are shown in Table4.Table 4
Seven rules to be compared with GP-SS.
RuleDescriptionFCFSFirst come first serviceLPTLongest life cycle seru firstSPTShortest life cycle seru firstECTEarliest completion time seru firstSHRandomly sequenced serusHCHighest conflict factor seru firstLCLowest conflict factor seru firstAs shown in Table5, for all test problems, GP-SS outperforms the human-made rules with the range from 5.82% to 133.31%. The reason that GP-SS is superior to human-made rules lies in that human-made rules are predesigned. They can be used in many scheduling domain but cannot be universally good. Rules from GP-SS are specifically evolved for SSRC and can naturally achieve better performance.Table 5
Comparison with human-made rules.
Test problemGapFCFS (%)GapLPT (%)GapSPT (%)GapECT (%)GapSH (%)GapHC (%)GapLC (%)5−5−326.9736.5415.5313.6414.2712.3932.7710−8−540.859.0216.0516.7825.315.8248.7515−12−828.3539.1012.6713.5231.556.2446.0020−15−1015.5647.0121.9418.4125.2910.3578.3825−18−1234.7642.2713.6320.5433.918.3869.7930−21−1524.6545.1111.7519.2829.3514.5585.4535−25−1843.4424.3916.8815.6717.0812.0944.0340−30−2020.5865.7221.2422.9135.6414.4773.0545−30−2343.8929.3317.2617.8634.1117.8384.5650−42−2742.0246.1017.6421.1434.399.2794.8555−45−3059.6132.5416.4929.2045.3713.16133.3160−48−3541.3969.1921.6526.9345.0214.5076.28Average gap35.1744.6916.8919.6630.9411.5972.27


## 4.2.2. Effects of Structure Similarity-Based Operators

To evaluate the performance of structure similarity-based operators, a comparison between GP-SS and basic GP is conducted. The results are shown in Table6.Table 6
Comparison with basic GP.
Test problemGapbasicGP (%)MinAvgTime5−5−35.5224.73−0.0310−8−54.4920.38−2.3115−12−86.8530.871.5320−15−107.4121.451.1825−18−1212.3635.31−1.5830−21−157.1526.692.7335−25−1813.2023.21−0.6440−30−207.9336.352.9345−30−238.4924.51−5.3150−42−2713.5428.89−3.0755−45−307.5226.841.5260−48−359.7322.731.61Average gap8.6826.83−0.12As shown in Table6, for best cases, GP-SS outperforms GP with an average gap of 8.68%. For the average cases, GP-SS outperforms GP with the gap ranging from 20.38% to 36.35%. For the computing time, GP-SS is similar to GP with an average gap of −0.12%. The above results verify that GP-SS is more effective than GP. The reason lies in that some subtrees or structures in individuals may have better effects than others. If these subtrees or structures can be found in the evolutionary process, it can help the algorithm enhance the optimization ability and convergence speed. The design concept of the proposed structure similarity-based operators is giving GP-SS a mechanism to search for a similar structure. Due to the design of two-attempt limit parameters, GP-SS also has the ability to jump from local optimal.To further analyze the quick convergence ability of GP-SS, an evolving process from a test problem in the test set is recorded in Figure3. The vertical and abscissa axes in Figure 3 represent fitness and the index of generation, respectively. It is easy to observe that GP-SS has a faster convergence speed and a better performance. This result can also help to verify the ability to search good regions of GP-SS.Figure 3
Evolving process of GP-SS and GP.


## 4.2.3. Comparison with GP-Based Algorithm

GP-HH is a hyperheuristic algorithm that employs GP as the high-level strategy to manage several predefined low-level heuristics [41]. The comparison between GP-SS and GP-HH is conducted in this section. The results are shown in Table 7.Table 7
Comparison with GP-HH.
Test problemGapGP−HH (%)MinAvgTime5−5−32.9520.500.7310−8−54.6130.911.6115−12−82.8322.942.8720−15−103.259.561.1925−18−129.6719.033.8530−21−157.1118.654.5435−25−182.3424.372.1940−30−204.707.383.7845−30−235.0314.636.0950−42−2713.7323.705.8155−45−304.9716.617.9260−48−355.2231.6410.86Average gap5.5319.994.29As shown in Table7, for the best cases, the gap between GP-SS and GP-HH ranges from 2.34% to 13.73%, with an average gap of 5.53%. For the average cases, GP-SS outperforms GP-HH with an average gap of 19.99%. For the computing time, GP-SS outperforms GP-HH with an average gap of 4.29%. The results show that GP-SS is more effective and efficient than GP-HH. The reason lies in that low-level heuristics have a high impact on the performance of GP-HH. Without good enough heuristics that are specially designed for SSRC, GP-HH cannot perform much better than basic GP. Therefore, due to the good convergence ability, GP-SS is superior to GP-HH.


## 4.3. Comparison with Other PMS Scheduling Algorithms

GRASP-VNS [42] and IGA [43] are two recent state-of-the-art algorithms designed for the PMS problem. These two algorithms are compared with GP-SS, and the results are shown in Table 8.Table 8
Comparison with GRASP-VNS and IGA.
Test problemGapGRASP−VNS (%)GapIGA (%)MinAvgminAvg5−5−30.00−0.910.001.3010−8−50.000.050.006.2215−12−80.000.710.000.9320−15−100.003.251.427.3125−18−120.69−0.581.265.2230−21−151.843.930.387.0835−25−181.432.761.956.9740−30−202.615.592.468.4245−30−231.603.683.046.2150−42−273.137.205.685.8755−45−302.172.303.553.0760−48−352.731.993.435.94Average gap1.352.501.935.38As shown in Table8, for the best cases, GP-SS performs a little better than GRASP-VNS and IGA with an average gap of 1.35% and 1.93%, respectively. For the average cases, GP-SS outperforms GRASP-VNS and IGA with an average gap of 2.50% and 5.38%, respectively. These results show that, based on the training process on the specific problem and structure similarity-based operators, GP-SS can achieve a slight advantage over other PMS scheduling algorithms.Meanwhile, the computing time of GP-SS is the sum of the time of generating rules on a training set and applying rules on all test problems. The computing time of GRASP-VNS and IGA is the sum of the time of independently running the algorithm on all test problems. Therefore, the computing time that is compared in this section is set as the above settings. Because of the big difference in computing time among these three types of algorithms, the gap that shows the percentage deviation between GP-SS and each compared algorithm is given as follows.(7)Gaptimex=100∗timex−timeGP−SStimex,where timex and timeGP−SS represent the computing time obtained by the x algorithm and GP-SS, respectively.The results are shown in Table9. It is observed that GP-SS outperforms GRASP-VNS and IGA with the gap of 64.04% and 73.21%, respectively. This result verifies the efficiency of the proposed GP-SS. The reason lies in that GRASP-VNS and IGA need to search the solution space for each test problem. However, GP-SS just needs to search on the training set.Table 9
The computing time of each m.
ExperimentGaptime (%)GP-SS vs. GRASP-VNS64.04GP-SS vs. IGA73.21


## 5. Conclusions

In this study, the seru scheduling problem with resource conflicts that minimizes the makespan is considered. In the addressed problem, workers are not necessarily fully cross-trained. Therefore, different serus may need the same worker(s), and serus that need the same worker(s) cannot be built simultaneously. To the best of our knowledge, this is the first work addressing the seru scheduling problem with the consideration of resource conflicts. The NP-hardness of the addressed problem is also proved.A GP-SS is proposed in this study to automatically generate effective rules to solve the SSRC. In GP-SS, structure similarity-based operators are designed to help GP-SS focus on more promising regions in searching spaces with affordable and small computing time increases. By adopting structure similarity-based operators, GP-SS can achieve fast convergence and avoid generating complex and huge tree-structured rules.Comparative results with human-made rules, basic GP, GP-based algorithm, and other state-of-the-art algorithms verify the effectiveness of GP-SS. For future work, there are several directions to be considered. Interaction between seru formation and SSRC can be taken into consideration. A cooperative coevolution algorithm can be designed to solve this problem. Besides, in addition to the makespan, some other objectives, such as production costs, can be considered.



---

*Source: 8166343-2021-12-21.xml*