1 Introduction

Because of the complexity and NP-hardness of many real engineering scheduling problems and their key roles in manufacturing systems, it is very important to develop efficient and effective advanced manufacturing and scheduling technologies and approaches. Flow shop scheduling is a class of widely studied scheduling problems with a strong engineering background, which illustrates at least some of the demands required by a wide range of real-world problems and has earned a reputation for being difficult to solve [1, 2]. The permutation flow shop problem with n jobs and m machines, as studied by many researchers, is commonly defined as follows. Each of n jobs is to be sequentially processed on machine 1, ..., m. The processing time p i,j of job i on machine j is given. At any time, each machine can process at most one job and each job can be processed on at most one machine. The sequence in which the jobs are to be processed is the same for each machine. The objective widely used is to find a permutation of jobs to minimise the maximum completion time, i.e. makespan C max [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]. Due to its significance both in theory and applications, it still represents an important issue for demonstrating the efficiency and effectiveness of newly proposed optimisation methods, although it has been widely studied so far.

Flow shop scheduling is a typical NP-hard combinatorial optimisation problem [1]. Exact techniques are only applicable to small-sized problems in practice. The solution quality of constructive methods such as CDS, NEH, etc. [2, 3] is not quite satisfactory although the process is very quick. Meta-heuristics such as simulated annealing (SA) [5, 6], genetic algorithm (GA) [7, 8], tabu search (TS) [9, 10, 11, 12] and evolutionary programming [13] can obtain fairly satisfactory solutions, but they are often very time consuming and parameter dependent, as well as the fact that the stopping criteria are either impracticable or hard to design. Recently, due to the growing paper number in hybrid systems, hybrid optimisation technology that combines the features of different methods in a complementary fashion has been a hot topic [14, 15, 16]. Ordinal optimisation (OO), proposed by Ho et al. [17, 18] has been successfully applied to many stochastic optimisation problems. It concentrates on finding a "good enough" solution with significantly reduced computation quantities instead of on finding the exact best solution. Borrowing the notion of "survival of the fittest", GA is an evolutionary computation algorithm with a learning capability that has been used in wide application in a variety of fields so far. In this paper, a class of order-based genetic algorithm is proposed for flow shop scheduling which borrows from the idea of OO to ensure the quality of the solution found with reduced computation efforts and which applies the evolutionary searching mechanism and learning capability of GA to effectively perform exploration and exploitation. With the guidance of OO, and by emphasising order-based search and elitist-based evolution, a good enough solution can be guaranteed with a high confidence level and reduced computation quantity.

The organisation of the article is as follows. In Sect. 2, the order-based genetic algorithm is proposed after a brief review of OO and GA. The implementation of the order-based genetic algorithm for flow shop scheduling is provided in Sect. 3, and its effectiveness is tested by simulation based on benchmarks in Sect. 4. The effects of some parameters on the optimisation performance are discussed in Sect. 5 and a conclusion follows in Sect. 6.

2 Order-based genetic algorithm

Recently hybrid optimisation systems have developed into promising tools by combining the features of different methods in a complementary fashion [14, 15, 16]. In this section, after briefly reviewing OO and GA, a class of order-based genetic algorithm is proposed.

2.1 Ordinal optimisation

The basic idea of OO is that "order is easier to determine than value" as well as "goal softening". Instead of trying to find the overall best solution, OO concentrates on finding a good solution in some top percentile of all solutions so that it can significantly reduce computation time and greatly improve convergence [17, 18].

Let S be the search space with |S| solutions and let the set G consist of the p e percent "best" solutions, i.e., p e =|G|/|S|. Usually |S| is extremely large, so it is very hard and time consuming to find the best global solution in S. If the goal is to obtain at least one solution in G with the desired probability p se , then p se =1−(1−p e )L and L=ln(1−p se )/ln(1−p e ), where L is the number required for random sampling. In Table 1, the required number L is summarised according to a different p se and p e . For example, the best of the 2301 randomly selected solutions is within the top 0.1% of the whole solution space with at least 90% probability. Obviously, if one uses some prior information for the problem or guidance to orient the search direction, much better results or probability can be achieved even with the same sampling number. This is the motivation behind replacing the blind search with the GA evolution process under the guidance of OO in this paper.

Table 1. Sampling number required for good enough solution via OO
Full size table

2.2 Genetic algorithm

Based on the mechanics of artificial selection and genetics, GA combines the concept of survival of the fittest among solutions with a structured, yet randomised information exchange and offspring creation, which repeats evaluation, selection, crossover and mutation after initialisation until the stopping condition is satisfied. GA is naturally parallel and exhibits implicit parallelism [19, 20], which does not evaluate and improve a single solution but analyses and modifies a set of solutions simultaneously. Even with random initialisation, the selection operator can select some "good" solutions as seeds, the crossover operator can generate new solutions while retaining good features from the parents, and the mutation operator can enhance the diversity and provide a chance to escape from the local optima. So, GA is an iterative learning process with a certain learning ability and thus is considered part of computational intelligence for optimisation. Although a number of weaknesses still exist, such as premature convergence, parameter dependence and difficulty in determining stopping criterion, GA has been extensively studied and applied in a number of fields thus far, especially in production scheduling.

2.3 Order-based genetic algorithm

Borrowing the idea of OO to ensure the quality of the solution found with reduced computation efforts and applying the evolutionary searching mechanism and learning capability of GA to effectively perform exploration and exploitation, a class of order-based genetic algorithm (OGA) is proposed as follows.

Step 1:

Randomly sample L solutions to form initial population P 0, where L is determined by OO according to a predefined weak p s0 and p 0 . Let k=0, and let π* be the best state among the initial solutions.

Step 2:

Select the best top-l solutions from the current population P k , and perform the first mutation operator with probability p mut for all these solutions; evaluate the newly generated solution if mutation happens and update π* if necessary, else keep the old solution; then order the resulted l solutions.

Step 3:

If stopping criterion is satisfied, stop the algorithm and output the best solution found so far, i.e. π*; otherwise, continue the following steps.

Step 4:

Perform |P k+1|/2 times order-based selection and crossover operators using the l solutions obtained by the first mutation operator to generate |P k+1| new temporary solutions, where |P k+1| can be determined by OO according to predefined strong p se and p e .

Step 5:

Perform the second mutation operator with probability p′ mut for all the temporary solutions to generate |P k+1| solutions and evaluate all the obtained solutions, and perform elitism policy for π* simultaneously.

Step 6:

Select the best |P k+1| solutions from the |P k+1| solutions obtained by the second mutation and the l solutions obtained by the first mutation to form the next population P k+1, and let k=k+1, then go back to step 2.

With the idea of OO, the OGA is able to guarantee a top-p 0 solution with at least a p se confidence level at initialisation stage. Moreover, some useful information on solution space can be gained, which may provide help for the GA's evolutionary self-learning search. In the later procedure, the OGA performs selection, crossover and mutation operators to guide the evolution process, with special emphasis on order-based searching and elitist-based evolution. Thus, with the computational time determined by the OO and the learning search behaviour of the GA, the OGA can find a solution with at least a p se confidence level, which is of the much better quality than the top p e . In comparison to exact searching and to some meta-heuristics, the OGA is highly efficient; in comparison to blind search and some constructive heuristics, the OGA is of great effectiveness. For the sake of clarity, the procedure is briefly illustrated in Fig. 1.

Fig. 1
figure 1

Brief procedure of the OGA

Full size image

3 Implementation of the OGA for flow shop scheduling

A job-permutation based encoding scheme has been widely used in many papers for permutation flow shop scheduling, so such an encoding scheme was also adopted for this paper. Next, the implementation of the OGA for permutation flow shop scheduling will be discussed in detail.

3.1 Implementation of step 1

First, since there is no prior information and knowledge available about the problem studied, only a blind search can be performed in the solution space. To achieve a certain search quality and an upper bound on the optimal value, a weak confidence level p s0 and an initial requirement p 0 are predefined, e.g., p s0=90% and p 0=0.1%. Thus, it is concluded via OO that 2301 random samples are required.

Obviously, after the above blind search is completed, some knowledge about the search space can be gained that will be useful for the GA in learning the evolutionary search process. So, let π* be the best solution among all the random samples, which is regarded as the initial population. In addition, if some problem-dependent information or heuristic is available, it can also be used in the initialisation stage, e.g., the well-known NEH heuristic can be applied to generate one solution for flow shop scheduling.

3.2 Implementation of step 2

To emphasise the order-based search and elitist-based evolution, only the best top-l solutions among the current population P k are selected to perform later genetic operators. Obviously a good choice of l and |P k | is often problem specific, so the effects of such parameters on the search quality will be discussed in Sect. 5. To avoid premature convergence, the selected l solutions perform the first SWAP mutation operator [16] with probability p mut, i.e., two distinct elements are randomly selected and swapped. π* should also be updated if the newly generated solution is better than π*. Since p mut is set to be very small, the number of evaluation for the newly generated solutions created by the mutation in this step can be ignored.

3.3 Implementation of step 3

To guarantee the final quality of the solution obtained by the OGA, a final desired confidence level p se and a final desired p e are predefined to determine the total evaluation number by OO. For example, if p se =99.99% and p e =0.01%, then 92099 total samples are required. Thus, if population size is set to 100 for each of the remaining generations, almost 900 more generations are needed for the GA, except for the initialisation stage. So the stopping criterion for the OGA is to set maximum generation to 900. Once the OGA stops, the best solution π* found so far becomes the output.

3.4 Implementation of step 4

The widely used proportional selection operator of GA is based on fitness value, so that one needs to determine a transfer from objective value to fitness value. Here, order-based or rank-based selection is strongly suggested to avoid transfer. That is, the l solutions obtained by the first mutation operator are ordered from the smallest objective value to the largest one, and let 2l−i/(2l−1) be the selected-probability of the ith solution. The crossover operator is only performed for these selected solutions.

The crossover operator used here is a partial mapping crossover (PMX), which may be the most popular one for operating the permutation [20]. In the PMX step, two crossover points are first chosen and the sub-sections of the parents between the two points are exchanged, then the chromosomes are filled up by partial map. For example, let 3 and 7 be two crossover points for parents (2 6 4 7 3 5 8 9 1) and (4 5 2 1 8 7 6 9 3). Then, the children will be (2 3 4| 1 8 7 6| 9 5) and (4 1 2| 7 3 5 8| 9 6). It has been demonstrated that PMX satisfies the fundamental properties enunciated by Holland, namely that it behaves in such a way that the best schemata reproduce themselves better than the others [21]. Moreover, in order to generate |P k+1| new temporary solutions for the next mutation operator, it needs to perform such order-based selection and crossover operators |P k+1|/2 times.

3.5 Implementation of step 5

The crossover operator can introduce new individuals by recombining the current population, while the mutation operator serves to maintain diversity in the population and prevent the population from stagnating at local minima. Besides the first mutation operator, the second SWAP mutation operator is applied with mutation probability p′ mut for every solution generated by crossover. Mutation also can enhance local search, but to avoid random search p′ mut is usually set rather small or with a certain adaptive policy. Then, all |P k+1| solutions resulting from the second mutation are evaluated. Meanwhile, the elitism policy is used in the OGA to avoid losing good solutions, i.e. the best solution found so far, π*, should be updated during the whole evolution process when better a solution has been found.

3.6 Implementation of step 6

In this step, the best top-|P k+1| solutions are selected from the |P k+1| solutions obtained by the second mutation and the l solutions obtained by the first mutation. These selected solutions are then used to form the next population, i.e., P k+1. Then, the OGA lets k=k+1 and goes back to step 2 to repeat the evolution process.

In the next section, some simulations based on benchmarks are carried out and the performance of the OGA is tested.

4 Numerical test and analysis

4.1 Benchmarks selected

Computational simulation is often carried out with benchmarks. In this paper, 29 problems that were contributed to the OR-Library by Mattfeld and Vaessens are selected. The first eight problems were called car1, car2,..., car8, respectively by Carlier [22]. The other 21 problems were called rec01, rec03,..., rec41, respectively by Reeves [7], who used them to compare the performances of SA, GA and neighbourhood search and found these problems to be particularly difficult. All these problems can be downloaded from http://mscmga.ms.ic.ac.uk. Thus far these problems have been used as benchmarks for study with different methods by many researchers [14].

4.2 Simulation results and analysis

Based on the implementation discussed in Sect. 3, 50 independent simulations are carried out for the OGA, classic GA [19] and blind search (BS), respectively with the same computational budget for the OGA, and the statistical results, as well as the results of NEH heuristic, are summarised in Table 2. The parameters of the OGA are set as p s0=90%, p 0=0.1%, p se =99.99%, p e =0.01%, p mut=p′ mut=0.1, l=60, P k =100(k≥1). In the classic GA, population size, maximum evolution generation and initialisation are the same as the OGA and PMX crossover, SWAP mutation with probability 0.1, proportional selection (f=M−C max, where f is fitness value, M is a positive number large enough) are used. The sample number of BS is approximately set to be 2301+900×100, i.e., 92301.

Table 2. The statistical results of testing algorithms
Full size table

From Table 2, it can be obviously concluded that the OGA provides the best optimisation performance for flow shop scheduling among all the methods studied. The results obtained by the OGA are close to being the best results available. In particular, the average relative error of the OGA over the best known is no more than 3.5%. Compared with the NEH method, the OGA can obtain much better results. Compared with the classic GA and BS, not only can the OGA achieve much better results, but its performance is also very stable as its BRE is always very close to the corresponding WRE. Especially when solving larger scale problems, the average performance of the classic GA is only of the same quality level as the NEH method, and the BS is much worse than NEH, but the OGA can do much better than NEH, GA and BS. Thus, it can be concluded that the OGA is superior to NEH, GA and BS with respect to optimisation quality and stability. It also can be concluded that the OGA can achieve the same performance as the classic GA and BS with much reduced computational efforts because more computational effort is required for classic GA and BS to achieve the same solution quality of the OGA. The effectiveness of the OGA can be attributed to the order-based genetic operators, the parallel and self-learning evolution mechanism of GA, and the guidance of OO. In addition, the performance of the OGA is also comparable or even superior to that of taboo search, simulated annealing, genetic algorithm and evolutionary programming and so on as presented in a number of existing papers [5, 7, 9, 10, 13].

5 The effects of some parameters

5.1 Effect of selected size

From the procedure of the OGA presented in Sect. 2, parameter l (number of the selected solutions in every generation) is one of the most important parameters related to the performance of the OGA. The effect of parameter l on the average performance when optimising the problem Rec21 is illustrated in Fig. 2.

Fig. 2
figure 2

The effect of selected size l on the average performance when optimising problem Rec21

Full size image

From Fig. 2, it can be concluded that when the value of parameter l is small, the algorithm is easily trapped in local minimums which can lead to premature convergence because there are not enough solutions selected. When l gets larger, the average performance becomes better. But if l is too large, the algorithm allocates a large amount of the search resources to low-quality solutions which induces a decline in the quality of the algorithm. The determination of an optimal parameter l and the adaptive mechanism will the object of the authors' further study.

5.2 Effect of population size

There's a tradeoff in the OGA between population size and generation number under the same computing budget determined by OO, i.e., generation×|P k |. The effect of population size |P k | on the average performance under the same computing budget when solving the problem Rec21 is shown in Fig. 3.

Fig. 3
figure 3

The effect of population size |P k | on the average performance when optimising problem Rec21

Full size image

From Fig. 3 it can be concluded that when the value of parameter |P k | is small, the algorithm can not converge at satisfactory solutions in spite of using more generations of evolution because the advantages of the order-based search mechanism can not be fully applied. When |P k | grows larger, the result of the algorithm becomes better. But if |P k | is too large, there are so few generations that the algorithm can not evolve efficiently and the solution quality becomes much worse. Actually, the population size can be variable during the evolution process, which is also a focus of further research work by the authors.

5.3 Effect of initial sample number

Besides parameter l and |P k |, the initial sample number of the algorithm is another important parameter for the OGA. The effect of this parameter on the average performance under the same total computing budget when solving the Rec41 problem is shown in Figs. 4a and 4b. If the initial sample number is not large, it can be seen from Fig. 4a that the results of the algorithm fluctuate very slightly when this parameter is changed. However, if the initial sample number is large enough, it can be seen from Fig. 4b that the search quality becomes much worse when this parameter becomes larger because less computational efforts are allocated to the OGA's evolutionary search. Since this stage is only used to construct the initial population of the OGA, it is suggested that moderate numbers of diversely random solutions should be sampled to form a satisfied initial population and speedy heuristics should be applied in this stage if available.

Fig. 4 a
figure 4

The effect of initial sample number on the average performance when optimising problem Rec41 and the initial sample number is not large. b The effect of initial sample number on the average performance when optimising problem Rec41 and the initial sample number is large

Full size image

6 Conclusions

Borrowing the idea of ordinal optimisation to ensure the quality of the best solution found with reduced computation effort, and applying the evolutionary searching mechanism and learning capability of a genetic algorithm to efficiently perform exploration and exploitation, a class of order-based genetic algorithms was proposed for flow shop scheduling problems. Under the guidance of OO and with emphasis on order-based searching and elitist-based evolution, a good enough solution can be guaranteed with a high confidence level and reduced computation quantity, which was demonstrated by benchmark-based computational simulation. Furthermore, the effects of some parameters on the optimisation quality were discussed. Future work will focus on enhancing the guided search ability in conjunction with OO and theoretical study of the convergence behaviour of the OGA, as well as on developing an adaptive mechanism. In addition, due to the generality and easy implementation of the OGA, other applications will be attempted.