Keywords

1 Introduction

The rapid development of globalization and information technologies has made our world a Global Village, where the interest of countries is interconnected. The core of the connection highly relies on international trade. Thus, it brings more opportunities and also thrives competition among companies. The study of allocating the jobs to machines and determining the order of processing the allocated jobs on each machine to optimize criteria such as flowtime, tardiness or customer satisfaction will benefit the companies by increasing their efficiency, profit or reputation.

Flexible job shop scheduling (FJSS) is an extension to classical job shop scheduling (JSS). The FJSS task, as its name suggests, assumes a more flexible situation. It reflects a production environment where it is possible to run an operation on more than one machine. This special trait causes the problem to become more complicated than classical JSS because we not only have to decide where to allocate jobs, but also need to decide which job to be processed next simultaneously. FJSS is NP-hard [2].

In addition, dynamic changes are inevitable in the real-world applications. For example, it is obvious that job orders are unpredicted or cannot be accurately predicted for companies, especially taking uncertain factors such as price impact, asymmetric information, rush hours and indefinite events into consideration. That is to say, we could not know job information until the job arrives. Dynamic flexible job shop scheduling (DFJSS) was born for considering this situation.

All these characteristics make DFJSS much more challenging than standard JSS and FJSS. Thus, the exact optimization methods such as mathematical programming [15] are often inapplicable, especially to large scale instances. Under this circumstance, heuristic search methods such as tabu search [14], genetic algorithm [16], simulated annealing [18] become more and more popular. These methods can get better performance in achieving reasonable solutions in less time. However, the biggest drawback is their lack of capability to adapt to the dynamic environmental change.

In order to reduce computational complexity and cope with dynamic changes, dispatching rules (DRs) have been widely applied [6, 10, 13]. When a machine becomes idle and has waiting operations in its queue, DRs will be triggered to select the operation with highest priority to be processed next. In this way, computation is carried out only at each decision point and decisions can be made efficiently.

However, lots of DRs are designed manually [17] and manual design has its inherent weaknesses. For instance, it highly relies on domain knowledge and it is very demanding on labour and time. Fortunately, genetic programming (GP) has been proven to be an effective hyper-heuristic method, which can automatically design DRs for scheduling [1, 9, 10, 12] that are much better than the manually designed ones. However, the existing works mainly focus on evolving the sequencing rule (the rule to select which waiting operation will be processed next when a machine becomes idle) without considering the routing rule (the rule to select which machine will be chosen to allocate the ready operations).

For DFJSS, a crucial issue is how it can evolve both routing and sequencing rules simultaneously. The representation is the crux of the applicable algorithm. There are two main reasons. Firstly, an appropriate representation is definitely a rudimentary factor for an algorithm to build a solution. Secondly, the representation determines the size of the search space and there is a clear trade-off between the complexity of the representation and the ability of GP to explore the search space. These two facts foster the motivation to propose a more suitable representation for DFJSS. To the best of our knowledge, cooperative co-evolution (CC) was firstly embedded into GP to evolve routing and sequencing rules together [19]. The proposed CCGP in [19] is the current state-of-the-art algorithm of DFJSS. However, the CC approach cannot fully capture the interaction between the routing and sequencing rules. Research in this area is still in a very early stage and little work has been reported on this important aspect. Dealing with multiple interdependent decisions, especially in dynamic environment, is always difficult but also creates opportunities to find the real global optimal solution. This is particularly challenging when multiple decisions need to be made at the same time.

In this paper, GP with multi-tree representation is introduced to evolve routing and sequencing rules together and a novel tree swapping crossover operator is proposed to evolve more effective rules. We aim to find more effective routing and sequencing rules for DFJSS based on GP with a multi-tree representation. In particular, we have the following research objectives.

  • Introduce GP with multi-tree representation (MTGP) for evolving the routing and sequencing rules simultaneously.

  • Propose a novel tree swapping crossover operator for the MTGP algorithm according to the feature of the DFJSS problem. The MTGP with the newly proposed tree swapping crossover is denoted as sMTGP.

  • Compare the performance of MTGP, sMTGP and CCGP to verify the effectiveness of the multi-tree representation and the novel tree swapping crossover operator.

  • Analyse the rules evolved by MTGP, sMTGP and CCGP.

2 Background

2.1 Dynamic Flexible Job Shop Scheduling

In the basic version of the job shop scheduling problem, \(n\) jobs need to be processed by \(m\) machines. Each job consists of a sequence of operations and a machine can process at most one operation at a time. For each operation, it can be processed at a specified machine. In essence, the JSS problem is based on the assumption that only one machine is able to run a particular operation.

FJSS breaks through the constraints of resources uniqueness: each operation can be processed by more than one machine and its processing time depends on the machine that processes it. Thus, FJSS can improve the production efficiency, shorten the ordering cycle and increase the rate of orders delivered on time.

In real life, industry is in a dynamic environment, for instance, in terms of a factory, the orders will arrive over time. Actually, there are some methods to predict the information of incoming jobs to reduce uncertainty, thus to improve the accuracy of decisions. However, the gap between prediction and reality is always inevitable and sometimes they have a very wide difference. It is indicated that when dealing with the real-world applications, dynamic changes should be taken into consideration.

2.2 Rules for Dynamic Flexible Job Shop Scheduling

This paper aims to evolve two kinds of rules for DFJSS, which are routing and sequencing rules, to make decisions at decision points. A routing rule is triggered when a new job arrives or when an operation is completed and its next operation becomes ready to be processed to allocate ready operation to a particular machine. When a machine is free and there are operations waiting, an operation in its queue will be chosen by a sequencing rule to be processed next.

Fig. 1.
figure 1

An example of decision process of DFJSS.

Full size image

Figure 1 shows an example of decision process of DFJSS. In the figure, the solid lines stand for what is happening and the dotted lines indicate what will happen. There are three machines in the job shop and each job can be processed by any machine. Each job consists of several operations in a certain order. In the current system state, the operations (\(O_{32}\), \(O_{52}\), \(O_{22}\), \(O_{71}\), \(O_{42}\), \(O_{62}\) and \(O_{11}\)) have been allocated to different machines by the routing rule. Then, each machine uses the sequencing rule to decide the next operation to be processed, e.g. \(machine\) 3 selects \(O_{62}\). When \(O_{62}\) processing is completed, its subsequent operation \(O_{63}\) becomes ready, and will be allocated by the routing rule.

3 Genetic Programming with Multi-tree Representation

The choice of which representation to use when dealing with a problem using GP is vital. Tree-based GP is a popular way in previous research and multi-tree representation [7] as a special structure has been applied to classifier design [3, 11] and feature manipulation [8].

In multi-tree representation, each individual is represented as a list trees. Taking advantage of this feature to solve the DFJSS problems, routing and sequencing rules can be denoted by different trees in one individual. According to this, multi-tree representation naturally lends itself to DFJSS. The pseudo-code of MTGP is given in Algorithm 1.

In this paper, we use the multi-tree representation that one individual contains two trees to match our problem. To be specific, the first tree is used to indicate the sequencing rule and the second tree denotes the routing rule. The fitness of one individual depends on the two trees working together. In the case of multi-tree representation, the evolutionary algorithm must come to a decision as to which trees the genetic operator will be applied.

In multi-tree representation, the classical genetic operators are defined to act upon only one tree in an individual at a time. Other trees are unchanged and copied directly from the parents to the offsprings. Genetic operators are limited to a single type of trees at a time in the expectation that this will reduce the extent to which they disrupt “building blocks” of useful code. However, when coping with DFJSS, such a crossover operator has the following issues.

figure a

Firstly, the crossover operation only happens between one type of trees of the parents, therefore, the offsprings generated might not be substantially different from their parents. Thus, the population will lose its diversity and the ability of exploration will decrease.

Secondly, the crossover operation cannot improve the diversity of the combinations of routing and sequencing rules. In DFJSS, a good rule cannot be “good” by itself, but should behave well when collaborating with the other rule. Thus, the diversity of combinations is an important factor for achieving good solutions.

Fig. 2.
figure 2

Tree swapping crossover operator for multi-tree representation.

Full size image

In order to overcome these shortcomings and make the algorithm more in line with the properties of DFJSS, a new tree swapping crossover operator is proposed. Figure 2 shows the tree swapping crossover operator, which shares the same process with the classical crossover operator except that the unselected trees (the same type) are also swapped with each other. To be specific, two parents (\(parent_1\) and \(parent_2\)) are selected to generate offsprings and the second type (\(T_2\)) of trees is selected for crossover. The dotted circles mean that the subtrees are chosen and will be swapped. The standard crossover operator will stop here. But for the tree swapping crossover operator, the other type of trees is also swapped. Thus, two offsprings (\(Offspring_1\) and \(Offspring_2\)) are generated.

This will bring two benefits. The first is that useful blocks are not easily broken. The second is more possible pairs or combinations of routing and sequencing rules will be examined in sMTGP. That is to say, the population of sMTGP will become more diverse compared with MTGP. More importantly, this point matches well with the characteristics of the DFJSS problems.

4 Experiment Design

4.1 Parameter Settings

In our experiment, time-invariant terminals in [10], were adopted. The details are shown in Table 1. Six functions {\(+\), −, \(*\), \(/\), \(max\), \(min\)} are selected in the function set, in which “\(/\)” is the protected division that returns the largest double positive number if divided by 0. All of them take two operands.

Table 1. The terminal set.
Full size table

For fair comparison, the parameters in MTGP and sMTGP are the same as in [19]. The population size is 1024 and the maximize depth of programs is 8. The crossover, mutation and reproduction rates are 0.80, 0.15 and 0.05, respectively. The rates of terminal and non-terminal selection are 0.10 and 0.90. Tournament selection was set as parent selection method with a tournament size of 7.

The learning process continued until the generation met the maximum generation, which was set to 51. The 30 independent runs test results were reported as the system performance.

4.2 Simulation Configuration

For dynamic simulation, the configuration is given in Table 2, which has been commonly used in existing studies [5, 10]. In order to improve the generalization ability of the evolved rules, the seeds used to stochastically generate the jobs were rotated in the training process at each generation.

Table 2. Dynamic simulation configuration.
Full size table

4.3 Comparison Settings

In our research, three algorithms were involved. CCGP [19] is built on GP with cooperative co-evolution and MTGP is the proposed algorithm that introduces GP with multi-tree representation to evolve routing and sequencing rules together. sMTGP is the improved MTGP with the tree swapping crossover. Moreover, a typical performance indicator for JSS is the flowtime, i.e., the sum of the total waiting time and the total processing time for one job. In this paper, we used three different kinds of variations of flowtime to measure the performance of the proposed algorithms, namely Max-Flowtime, Mean-Flowtime and Mean-weighted-Flowtime. Different scenarios were used to measure their robustness.

For the DFJSS problem, in our case, it is impossible to get the best known (lower bound) objective value of the instances. So, benchmark routing rule (LWIQ, Least Work in Queue, select the machine with the least work in its queue) and sequencing rules (SPT, Shortest Processing Time, choose the job with shortest processing time, for mean-flowtime; FCFS, First Come First Serve, the job comes first will be processed firstly, for max-flowtime and mean-weighted-flowtime) [4], were applied to get a baseline objective value for each instance. The reason for choosing them is that they show better performance than others in previous work [6] and often be chosen as benchmark rules [19]. Here, the relative performance ratio was defined as the average normalized objective value obtained by evolved rules over the counterpart got by benchmark rules. Thus, in our case, the smaller the fitness, the better.

5 Results and Discussions

5.1 Optimization Performance

In our experiment, six scenarios were set to test the performance of MTGP, sMTGP and CCGP. The best pair of rules of the last generation was tested on test data set to measure its performance. The test data set consists of 50 dynamic simulations with different random seeds. In addition, Wilcoxon signed rank test at the \(5\%\) level was used for comparison between the three algorithms. First of all, MTGP and sMTGP were compared with CCGP respectively to measure the feasibility of multi-tree based GP. Then, sMTGP and MTGP were compared for analysing the effectiveness of proposed tree swapping crossover operator.

Fig. 3.
figure 3

The boxplot of average normalized objective value obtained by sMTGP, MTGP and CCGP on test data set.

Full size image

All the mean value obtained by MTGP and sMTGP are better than CCGP and all the standard deviation value are smaller than the counterparts. Wilcoxon signed rank test results show that sMTGP is significantly better than CCGP only in two scenarios (Max-Flowtime-0.85, Mean-Flowtime-0.85). It is interesting that MTGP got better mean value than CCGP, but none of the instances of MTGP is significantly better than CCGP.

When further looking into the boxplot in Fig. 3, one can see that CCGP has many more outliers than MTGP and sMTGP. This is because CCGP cannot handle well the interactions between routing and sequencing rules directly, thus can be stuck into poor local optima more often. The reason why there is no statistical significance between MTGP and CCGP is that the two algorithms showed very similar performance except the outliers. Figure 3 clearly shows that multi-tree representation managed to dramatically reduce the probability of outliers.

Fig. 4.
figure 4

The convergence curves of the average best sequencing rule size (30 runs) obtained by sMTGP, MTGP and CCGP at each generation.

Full size image
Fig. 5.
figure 5

The convergence curves of the average best routing rule size (30 runs) obtained by sMTGP, MTGP and CCGP at each generation.

Full size image

According to these observations, the performance of GP with the multi-tree representation is more stable than GP with cooperative co-evolution. Also, Wilcoxon signed rank test results show that sMTGP is significantly better than MTGP in four scenarios, which are Max-Flowtime-0.85, Mean-Flowtime-0.85, Mean-weighted-Flowtime-0.85/0.95. It means that the proposed tree swapping crossover operator can effectively improve the performance of MTGP.

Figure 4 shows that the sizes of evolved best sequencing rules by sMTGP and MTGP are obviously and dramatically smaller than the best rules evolved by CCGP. Also, Fig. 5 shows that the best routing rule sizes got by sMTGP and MTGP are smaller than that of CCGP. However, there is not so much difference compared with the changes of sequencing rule sizes. These observations confirm the potential of using multi-tree based GP to achieve smaller size rules.

From Table 3, it is clear that sMTGP and MTGP can evolve rules with lower time complexity than CCGP in all scenarios. In addition, for sMTGP, less training time is needed as compared to MTGP in three situations (scenario 3, 4, 6). This is a promising finding that GP with multi-tree representation is computationally cheaper than GP via cooperative co-evolution for DFJSS.

Table 3. The average training time for each run of the three algorithms.
Full size table
Fig. 6.
figure 6

The convergence curves of average sequencing rule size (30 runs) obtained by CCGP, MTGP and sMTGP in population at each generation.

Full size image
Fig. 7.
figure 7

The convergence curves of average routing rule size (30 runs) obtained by CCGP, MTGP and sMTGP in population at each generation.

Full size image

Overall, MTGP and sMTGP (especially) undoubtedly show better ability to solve DFJSS problems. They can obtain better and smaller rules within a shorter training time.

5.2 Further Analysis

In the last section, the rule size relates to the best rule only. In order to explore whether the best rule is smaller by chance or the rules in the whole population generally become smaller, in this section, the average rule sizes in the whole population at each generation were investigated to get a clear vision of the changes of rule sizes. We took the scenario (Mean-Weighted-Flowtime-0.95) as an example to further investigate the changes of rule sizes.

As shown in Figs. 6 and 7, at the initial point, for all the three algorithms, the average sizes of both rules are about equal. However, the average sizes obtained by CCGP are larger than others over time. Maybe in multi-tree based GP, effective and smaller rules are more likely to be well preserved because there is at least one rule structure will not be changed by operator at each time during the evolution process. In addition, the average sizes obtained by MTGP and sMTGP show the same trend basically and routing rule sizes are bigger than sequencing rules. This is consistent with the observation in the last section.

6 Conclusions and Future Work

This paper tried to evolve routing and sequencing rules based on GP with multi-tree representation simultaneously, which is one of the very first piece of work in this field. From the experimental results, we got some interesting findings. Firstly, in addition to performance, both the routing and sequencing rules evolved by MTGP and sMTGP are much smaller than that of CCGP. MTGP and sMTGP also take less training time. This is an important merit because high training time is a big limitation of GP. Secondly, the proposed tree swapping crossover operator can enhance the ability of MTGP from the perspective of performance, rule size and training time in general. Thirdly, for average normalized objective values on test data set, there are more outliers obtained by CCGP. That is to say, the assumption in CCGP that routing and sequencing rules are independent and can be involved separately, might be not true. This suggests that when we evolve two rules at the same time, we would better to take the interaction into consideration. In the future, the reason why the average rule size in the whole population becomes smaller will be further explored in the future.