1 Introduction

In open-shop scheduling problem (OSSP), n jobs are processed by m machines. If all of the jobs are processed in a constant route by m machines (e.g., all jobs are processed by machine 1 at first, then by machine 2, and so on until they are processed by machine m), the problem will be a flow-shop type problem. If each job is processed in a specific route by m machines, the problem will be a job-shop type problem; and if the routes of job processing are not deterministic, the problem will be classified as open-shop type (Shamshirband et al. 2015a; Hosseinabadi et al. 2015; Shojafar et al. 2016).

In OSSP, m machines process a set of jobs. Each job includes n operations that must be processed in a deterministic processing time interval by a machine (Hosseinabadi et al. 2013). Operations can be processed through following any possible order. At a specified time, each machine is able to process only one operation of a job. Operations of each job can be processed only after a time called release time for each job. During the process of an operation, no interrupt or tardiness is allowed; and the jobs are independent. The goal of this problem is to find an optimal scheduling with makespan \(C_{\max }\) for the completion of n jobs. To achieve this result, the jobs processing sequence and the routes that jobs pass through must be considered (Tavakkolai et al. 2015; Farahabadi and Hosseinabadi 2013).

For simplicity, it is assumed that all jobs in most problems are accessible at zero time. According to the scheduling standard introduced by Graham et al. (1979), the problem can be defined in the form of \(O_{\max } ||C_{\max }\), where m is the number of machines. Pinedo (1995) proposed a prioritization rule in the form of the Longest Alternate Processing Time First (LAPT) for the \(O_{2} ||C_{\max }\) problem by which optimal scheduling was obtained in a polynomial time complexity. Gonzalez and Sahni (1976) proved \(O_{3} ||C_{\max }\) is an NP-hard problem, and, in 1993, Lawler et al. (1993) proved that \(O_{m} \left| 3 \right| C_{\max }\) is strongly an NP-hard problem, which means that the optimal solution for the problem is not obtained in a polynomial time complexity. Branch and bound algorithms were used to solve small problems, and heuristic algorithms, which could find approximately optimal solutions, are suitable for solving large problems (Vasant et al. 2016; Vasant 2014).

Broadly speaking, the optimization algorithms can be divided into two categories of exact and approximate methods (Talbi 2009).

In this paper, a new extended GA is proposed to solve the OSSP with the aim of minimizing the end time of all jobs. Also, various efficient crossover and mutation operators are studied in the proposed algorithm. Jobs and operations are as inputs, and the minimization of the finish time of all jobs is the output of the proposed algorithm.

The remaining of the paper is organized as follows: Sect. 2 reviews related works on the subject covered in this paper. Section 3 describes the statement of the problem. Section 4 discusses the proposed algorithm. Sections 5 and 6 present the mechanism of the EGA_OS and the computational results, respectively. Finally, the conclusion is presented in Sect. 7.

2 Related work

In this section, some recent works on OSSP are investigated. The parallel OSSP was studied by Chen et al. (2013) with the purpose of minimizing makespan. But due to the NP-hard nature of the problem, it was proposed that approximate algorithms can be used for solving them. Goldansaz et al. (2013) dealt with the multi-processor OSSP with different limitations including independent setup time, process time, and sequence-dependent removal time. It applied the combination of the Imperialist Competitive Algorithm (ICA) and Genetic Algorithm (GA) in order to solve the problem with the objective of minimizing makespan. It has been proved that if restrictions for machine loads were considered, the three-machine proportionate open-shop problem could be solved in \(O\left( {n\log n} \right) \) time, and if these restrictions were not considered, approximate methods are a suitable alternative for solving them (Koulamas and Kyparisis 2015).

Low and Yeh (2009) first defined the OSSP problem as a binary programming model and then introduced a Hybrid Genetic Algorithm (HGA) considering various restrictions including independent setup and dependent removal time for solving the problem with the purpose of makespan reduction. Other researchers (Shamshirband et al. 2015a) studied a special type of the open-shop problem called no-wait open-shop with the purpose of reducing the makespan. They then used three mathematical models in the form of integer linear programming models and patterns for coding and decoding. Furthermore, these patterns were used to introduce a method based on GA and variable neighborhood search for optimally solving the problem. The Lagrange expansion was used to total quadratic completion time reduction in scheduling small open-shops (Zhang and Bai 2014).

An efficient HGA called Hybrid Non-dominated Sorting Genetic Algorithm (HNSGA) was developed to solve the multi-objective open-shop problem in Noori-Darvish and Tavakkoli-Moghaddam (2011). This method applied the Local Search Algorithm (LSA) in order to generate an initial population for solving medium- and large-sized problems. Results obtained after the implementation with respect to qualitative criteria, variety, and space were found to be superior to the Strength Pareto Evolutionary Algorithm (SPEA-II) method.

Several two-phase heuristic algorithms were applied for solving the OSSP with portable dedicated machines and without time limitations in Hosseinabadi et al. (2014), Hosseinabadi et al. (2012) and Rostami et al. (2015). Furthermore, another HGA with special operations (Ahmdizar and Hosseinabadi 2012) was proposed for solving the OSSP. The suggested operations could omit the sequence of performing the jobs by the machines, and the proposed mutation operation could prevent search process for redundant solutions. The proposed method was a combination of iterative randomized active scheduling concepts, a dispatching index, and a lower bound.

In Ciro et al. (2016), two multi-objective methods named Non-dominated Sorting Genetic Algorithm (NSGA-II) and NSGA-III were proposed and compared. Different constraints, such as tools allocation and multi-skills staff assignment, were considered in these methods. The objectives were to minimize total flow time of jobs in the production system, workload balancing in both manpower and machine points of view. They generated some small- and large-sized instances to show the general performance of these algorithms. Results showed that when the size of instances increases, the performance of NSGA-III was better than that of NSGA-II.

The asymptotic optimality of the General Dense Scheduling (GDS) algorithm was investigated for the static and dynamic versions of the Flexible Open-Shop (FOS) makespan problem in Baia et al. (2016). A GDS-based algorithm was utilized to improve the original GDS algorithm for large- and average-scale problems.

A mechanical workshop-based OSSP was discussed in Ciro et al. (2015). The problem was formulated as a fuzzy Mixed-Integer Linear Programming (MILP) model and solved using an Ant Colony Optimization (ACO).

A recent study in Azadeh et al. (2016) has developed a novel bi-objective MILP model for multi-objective OSSP. Independent setup time and sequence-dependent transportation time were the main constraints considered in the model. The aim of the proposed model was to minimize the total makespan of jobs as well as the workload of all machines.

Harmanani and Ghosn (2016) proposed a Simulated Annealing Algorithm (SA) for solving the non-preemptive open-shop scheduling problem in order to minimize the makespan by determining a schedule for operations on the machines. Makespan was defined as the time starts from the beginning of the first operation until the end of the last operation.

Other recent studies (Karagöz and Yıldız 2017; Hosseinabadi et al. 2016a, 2017b; Shamshirband et al. 2015b; Hosseinabadi et al. 2016b, 2017a) evaluated the performances of some recent optimization algorithms, such as Particle Swarm Algorithm (PSO), Cuckoo Search Algorithm (CSA), Gravitational Search Algorithm (GSA), Hybrid Gravitational Search-Nelder Mead Algorithm (HGSANM), League Championship Algorithm (LCA), Firefly Algorithm (FA), Bat Algorithm (BA), Interior Search Algorithm (ISA), ICA, Gravitational Emulation Local Search Algorithm (GELS), and SA in terms of finding the optimal thin-walled tube design and Vehicle Routing Problem (VRP).

Yildiz (2012) investigated some population-based optimization methods to solve multi-pass turning optimization problems. The outcome of the investigation was a proposed differential evolution algorithm based on a hybrid technique for solving manufacturing optimization problems.

Another study presented in Yıldız et al. (2007) aimed to develop a more efficient shape optimization approach using GA and robustness issues to release the restrictions caused by a larger population of solutions in the pure Multi-Objective Genetic Algorithm (MOGA).

Recently, Tellache and Boudhar (2017) have introduced open shops considering some conflicting jobs that cannot be processed simultaneously on different machines. They proposed heuristics and lower bounds for the general cases of the problem.

3 Problem description

OSSP is considered as a kind of general job scheduling problem and consists a set of n jobs \(\mathcal{J}=\left\{ {J_1 ,J_2 ,\ldots ,J_n} \right\} \) and must be processed on one of the m machines \(M=\left\{ {M_1 ,M_2 ,\ldots ,M_m} \right\} \). Each job \(J_i \in \mathcal{J}\) consists m operations \(o_{i,j}\) that is processed on the machine \(M_i\). At any moment, each machine can only process one operation related to the job. Two or more operations of a job cannot be processed on different machines at the same time. The problem is to find an optimal schedule for the operations on machines that minimizes makespan \((C_{\max })\); makespan is the calculated from the beginning time of the first operation until the last one (Bai and Tang 2013). A schedule of optimum finishing time is a schedule containing at least the finishing time among all schedules. If there is at least a triad \({<}{i,s\left( i \right) ,f\left( i \right) }{>}\) for each machine and each job, which must be scheduled, then the schedule is non-preemptive. S(i) denotes the \(i{\mathrm{th}}\) scheduling, and f(i) denotes the objective function value of \(i{\mathrm{th}}\) scheduling. A preemptive schedule is the one that has no constraint for the number of triads for jobs and machines. It has been demonstrated that non-preemptive open-shop scheduling problem is an NP-hard problem because it converts the problem into a scheduling problem (Gonzalez and Sahni 1976). It is proved that the following lower bound is correct for scheduling with optimum finishing time (Gonzalez and Sahni 1976).

$$\begin{aligned}&\mathcal{L}=\left\{ {\max _i \mathop \sum \limits _{j=1}^m p_{i,j} ,\max _j \mathop \sum \limits _{i=1}^n p_{i,j}} \right\} ,\quad \hbox {where } 1\le i\le n\nonumber \\&\quad \quad \hbox { and }1\le j\le m. \end{aligned}$$
(1)

The first part of Eq. (1) is related to the maximum completion time of all jobs that must be processed on machines. On the other hand, it indicates that the total processing time of jobs must at least be equal to their defined required time to process their operations. The second part shows the maximum completion time of jobs assigned to a given machine. Therefore, the processing time of each machine must at least be equal to the sum of all times required for operating its assigned jobs. The optimal makespan of an open-shop scheduling is never less than \(\mathcal{L}\), but it does not indicate that it should be necessarily equal to \(\mathcal{L}\) (Harmanani and Ghosn 2016).

This research evaluates the OSSP using the \(4\times 4\) Taillard Benchmark (Taillard 1993) as shown in Table 1. The benchmark instance consists of 4 jobs and 4 machines. Figure 1 shows a possible schedule with an optimal makespan of 193.

Table 1 A \(4\times 4\)Taillard Benchmark instance for the OSSP (Taillard 1993)
Full size table
Fig. 1
figure 1

Optimal schedule for Taillard Benchmark instance with the makespan of 193

Full size image

4 The proposed algorithm

There are many exact methods, heuristics and metaheuristics developed for all introduced optimization problems in order to solve them (Deb and Jain 2014; Khuri and Miryala 1999; Fang et al. 1994; Prins 2000; Colak and Agarwal 2005; Tellache and Boudhar 2017; Tirkolaee et al. 2018, 2017; Mirmohammadi et al. 2017; Babaee Tirkolaee et al. 2016; Alinaghian et al. 2014). In this paper, GA is implemented for developing a novel method in order to solve the OSSP. Also, the effects of the implemented crossover and mutation operations on the proposed approach are investigated to yield the high-quality solutions. Sections 4.1, 4.2, 4.3, 4.4, 4.5, 4.6 and 4.7 describe the parameters of the proposed algorithm (EGA_OS).

4.1 Chromosome representation

The proposed EGA_OS applies a single-dimensional array with the same length as the total number of the operations to show each chromosome. Each gene of each chromosome contains a unique integer that indicates one operation in one job. Table 2 shows the procedure of numbering the example system in Table 1.

Table 2 The procedure of numbering the operations for the example system in Table 1
Full size table

An example chromosome for the example system in Table 1 is shown in Fig. 2.

Fig. 2
figure 2

Structure of a sample chromosome

Full size image

As shown in Fig. 2, the first gene is the number 5, which refers to the operation 1 in job number 2 that must be performed by machine 4. In this method of chromosome representation, each chromosome shows a schedule for performing all the operations in each job.

4.2 Fitness function

Makespan is used to determine chromosome fitness and is calculated based on Eq. (2):

$$\begin{aligned} {\hbox {Fitness}}={\hbox {Max}}_1 <I\le n\left\{ {T_i } \right\} \end{aligned}$$
(2)

where n is the number of jobs and \(T_{i}\) is the completion time for job i.

4.3 Parent selection

The EGA_OS used the tournament method to select the parents. In this method, a small subset of the chromosomes is randomly selected and two of the best chromosomes that have the highest fitness values are selected as the parents.

4.4 Crossover operation

Four different crossover operations are used in the EGA_OS to study the effects on the type of the selected crossover operation on solving the problem.

4.4.1 Homologous Crossover Genetic Operation (C.S)

Once the parents are selected, the Homologous Crossover Genetic Operation (C.S) first passed the homologous genes in the two parents on to the child, and then the remaining of the genes are stochastically selected from parent 1 or 2 and passed on to the child. In this kind of crossover in the early generations, different childrens with greater variety are produced because the chromosomes are different. Therefore, there would be greater diversity in the population. Figure 3 shows the operations performed by the C.S.

Fig. 3
figure 3

Homologous Crossover Genetic Operation

Full size image

4.4.2 Row Crossover Operation (C.R)

Once two parents are selected, the Row Crossover Operation (C.R) randomly selects one of the two parents first and passes its first gene on to the child. This gene is then omitted from the other parent. This process continues until the child received all its genes. In this crossover method, diverse chromosomes are generated. Figure 4 implies an example of the application of the C.R.

Fig. 4
figure 4

Row Crossover Operation

Full size image

4.4.3 One-point crossover operation (C.O)

The One-Point Crossover Operation (C.O) first selects one number stochastically from the interval 1 to n (length of the chromosome) and the genes in the interval from 0 to the randomly selected number are passed on to the child. Homologous genes in parent 2 are then omitted, and the remaining of the genes are embedded, respectively, in the empty cells of the child. Figure 5 illustrates the application of the C.O in the proposed algorithm.

Fig. 5
figure 5

One-point crossover operation

Full size image

4.4.4 The two-point crossover operation (C.D)

The Two-Point Crossover Operation (C.D) first selects two random numbers in the interval from 0 to n (length of the chromosome). The genes between these two stochastically selected numbers are passed on from parent 1 to the child, and the homologous genes in parent 2 are omitted. The remaining of the genes are embedded, respectively, from parent 2 in the empty cells of the child. Figure 6 implies an example of the application of the C.D.

Fig. 6
figure 6

Two-point crossover operation

Full size image
Fig. 7
figure 7

Displacement Mutation Operation

Full size image
Fig. 8
figure 8

Shift mutation operation

Full size image
Fig. 9
figure 9

The pseudo-code of the EGA_OS

Full size image

4.5 Mutation operation

In the EGA_OS, two different mutation operations were used to study the effects of the selected type of the mutation operation on solving the problem.

4.5.1 Displacement Mutation Operation (M.A)

After the selection of the parents, the Displacement Mutation Operation (M.A) randomly selects two genes and displaces them. Figure 7 indicates the application of the M.A.

4.5.2 Shift mutation operation (M.S)

Table 3 The parameters of the EGA_OS
Full size table
Table 4 The designed test datasets
Full size table

After the parent chromosome is selected, two points are randomly selected in the interval from 1 to n (length of the chromosome) and the genes located between these two points are rotationally shifted to the left. Figure 8 shows an example of M.S.

4.6 Selection of chromosomes for the next generation

Chromosomes for the next generation are selected in the EGA_OS using a hybrid approach. The chromosomes are ordered based on their fitness at first, and repetitive chromosomes are then omitted. Only 10% of the chromosomes with higher fitness values are then selected for the next generation. The remaining of the chromosomes are selected at random because this method tried to maintain chromosome dispersion in each iteration.

4.7 Termination condition

Termination condition of GA depends on the type of the problem and the external knowledge about it. In the EGA_OS, the specified maximum number of generations is considered as the termination condition, i.e., if the desired number of generations is reached, the best chromosome is found and the algorithm is terminated.

Figure 9 shows the pseudo-code of the EGA_OS.

After the initial evaluation of the various mentioned crossover and mutation operations for the OSSP, we reach the conclusion that the mutation and crossover operations substantially influence the achievement of optimal solutions. The conclusion from the initial evaluation is that the One-point and Two-point crossover operations perform better than the other crossover operations. The greater utilization of the mentioned mutation operations enhances scanning capability of the GA in solving the OSSP. Therefore, the EGA_OS pseudo-code algorithm is a combination of the two crossover operations (the One-point and Two-point crossover operations), with the C.O having a 70% chance, and the C.D having a 30% chance, of being selected for creating children. Moreover, both displacement and shift mutation operations are selected to apply mutation, with an M.A and M.S having a 60 and 40% chances, respectively, of being selected for creating the children. In the initial evaluations, 60 and 70% probabilities are obtained.

4.8 Parameter setting

The parameters of the EGA_OS are determined as below:

Crossover probability is equal to 0.8, and mutation probability is equal to 0.2. The number of generations is 250, and the population size is considered to be 92 according to Deb and Jain (2014). Table 3 shows the parameters of the EGA_OS.

5 Evaluation of the proposed algorithm

This section discusses the evaluation of the EGA_OS using different crossover and mutation operations to see for which operations the EGA_OS provided optimal solutions. This process is described in detail below. The C#.Net programming language was used to implement the algorithms. The algorithms were executed on a computer equipped by Intel \(\circledR \) Pentium \(\circledR \) 4 CPU 3.00 GHz processor and 2.00GB of RAM. In order to investigate the efficiency of the EGA_OS and the effects of crossover and mutation operations on solving the OSSP, 9 datasets in three different groups were designed.

The designed datasets were named Test_N_M, where N is the number of jobs and M is the number of operations in each job of the designed datasets. Table 4 shows the designed datasets.

Table 5 shows the results of the execution of the EGA_OS on the test datasets in group 1, where LB shows the highest fitness value, UB is the lowest fitness value, CPUs is the time (in seconds) required for executing the algorithm, and MU and CR are the type of mutation and crossover operation, respectively, employed in the EGA_OS. As shown in Table 5, in group 1 dataset the use of the C.O yielded better solutions compared to the other crossover operations. The M.S Mutation Operation together with the C.D performed relatively better compared to the other operations.

Table 5 Results of executing the EGA_OS on group one test datasets
Full size table

Table 6 lists results of executing the EGA_OS on group 2 test datasets. Here too, the use of the C.O yielded better solutions, and the M.A performed relatively better compared to the M.S.

Table 6 Results of executing the EGA_OS on group 2 test datasets
Full size table

Table 7 illustrates the results of executing the EGA_OS on group 3 test datasets. As observed in Table 7, once again the use of the C.O and the M.A was more suitable and yielded better solutions, whereas the M.S mutation operation together with the C.O crossover operation performed poorly. Moreover, the C.D performed better than the C.R and the C.S.

Table 7 Results of executing the EGA_OS on group 3 test datasets
Full size table

Figure 10 shows the fitness diagram of the EGA_OS for the Test_7_7 dataset based on different crossover and mutation operations (M.A).

Fig. 10
figure 10

Fitness diagram of the EGA_OS for the Test_7_7 dataset, based on various crossover and mutation operations (M.A)

Full size image

Figures 11 and 12 show the dispersion diagrams for the Test_8_8 dataset and Test_5_5, respectively. Population dispersion is always maintained in the EGA_OS. This is one of the reasons for using the hybrid approach that prevented premature convergence of the chromosomes. Moreover, comparison of the dispersion diagrams of the various crossover operations in Figs. 11 and 12 implies the C.R and C.S crossover operations searched greater space of the problem compared to the other crossover operations reason being they generated more diverse chromosomes compared to the other crossover operations but did not find better solutions than the C.O crossover operation. The C.O crossover operation generated more desirable chromosomes, and better solutions compared to the other crossover operations were obtained because it merged information that resulted from the two parents better.

Figure 13 shows fitness comparison on Test_15_15 using various crossover and mutation operations. As shown in Fig. 13 the M.A mutation operation was more efficient compared to the M.S mutation operation. Moreover, Fig. 13 indicates better solutions could be obtained by using the M.A mutation operation together with the C.O crossover operation. By applying the M.A mutation operation, the generated children are very similar to the parents. These children differed in only two genes, and this similarity to the parents gave better parents a greater opportunity to create children, which made it easier to obtain the solution in the problem space. However, if the M.S mutation operation was used, children very different from the parents could be created. This would cause greater diversity in chromosomes, but, compared to the M.A mutation operation, the solution would be found much more slowly.

Figure 14 shows the Gantt chart of an example of open-shop scheduling for the Test_6_6 dataset in which the C.O and the M.A were used for solving the problem. Figure 15 shows the Gant chart of an example of open-shop scheduling of the Test_7_7 dataset.

Fig. 11
figure 11

Dispersion diagram of the various crossover operations for the Test_8_8 dataset

Full size image
Fig. 12
figure 12

Dispersion diagram of the various crossover operations for the Test_5_5 dataset

Full size image
Fig. 13
figure 13

Fitness diagram of various crossover and mutation operations for the Test_15_15 dataset

Full size image

6 Computational results for the designed test problems

For this study, 20 test datasets were considered to investigate the efficiency of the EGA_OS and the effects of the selection of crossover and mutation operators on solving the OSSP. The test datasets are named as Test_N_M, where N was the number of jobs and M was the number of operations of each job in the dataset. The designed test datasets were divided into three groups. The first group represented small systems, the second group indicated medium systems, and the third group represented large systems.

Table 8 presents results of executing the EGA_OS on the test datasets of small, medium, and large systems and compares these results with those of the ACO and ICA Algorithm. In Table 8, LB represents the highest fitness value, UB the lowest fitness value, and CPUs the time (in seconds) required for executing the algorithm. As shown in Table 8, the EGA_OS could find more optimal solutions for all kinds of problems compared to the other two algorithms and could be executed in a shorter time.

Fig. 14
figure 14

Gantt chart of an example of open-shop scheduling for the Test_6_6 dataset

Full size image
Fig. 15
figure 15

Gantt chart of an example of open-shop scheduling for the Test_7_7 dataset

Full size image
Table 8 Results of executing the EGA_OS, ACO, and ICA algorithms on various test data
Full size table
Fig. 16
figure 16

Fitness diagram of the EGA_OS vs ICA and ACO for the Test_5_5 dataset

Full size image
Fig. 17
figure 17

Fitness diagram of the EGA_OS vs ICA and ACO for the Test_8_8 dataset

Full size image
Fig. 18
figure 18

Fitness diagram of the EGA_OS vs ICA and ACO for the Test_18_18 dataset

Full size image
Fig. 19
figure 19

Fitness diagram of the EGA_OS vs ICA and ACO for the Test_30_20 dataset

Full size image
Fig. 20
figure 20

Fitness diagram of the EGA_OS vs ICA and ACO for the Tset_30_30 dataset

Full size image
Fig. 21
figure 21

Fitness diagram of the EGA_OS vs ICA and ACO for the Test_40_20 dataset

Full size image

Figures 16, 17, 18, 19, 20, and 21 compare the fitness of the EGA_OS and those of ACO and the ICA algorithms for some of the designed datasets. As evident from Figs. 16, 17, 18, 19, 20, and 21, EGA_OS could solve the problem considered for this study efficiently and compete with compared algorithms.

The main objective of this assessment was to investigate the convergence of the algorithm in achieving an optimal or a near-optimal solution. In approximation algorithms, population convergence had a direct impact on ending and finding the optimal solution. Generally, some approximation algorithms were converged in a lower number of repetitions and this convergence may occur in an inappropriate space of the problem, so that obtained solution was not optimal. In addition, in some algorithm which emphasizes on population diversity, population convergence occurs slowly and it takes longer time. Thus, an algorithm is useful if it could investigate more space of solutions in a shorter time and also convergence occurs in a short time. Hence, it can generate better solutions than other algorithms.

Generally, solutions’ diversity has a direct impact on finding the optimal solution. If an algorithm investigates more space of problem in a shorter time, and it gets more time to converge, the chance of achieving optimum solution increases.

7 Computational results for the benchmarks

This section provides some scenarios containing different jobs and machines for solving the problem considered for this study using the EGA_OS. The created scenarios were divided into three groups according to the number of jobs and scenario complexity. Table 9 shows these scenarios with their number of jobs and machines.

The EGA_OS was tested on Taillard Benchmarks (Taillard 1993). Tables 10 and 11 describe the obtained results of Taillard Benchmark using determined parameters. As it can be seen, the EGA_OS could obtain optimum solutions in most benchmark instances and compete with compared algorithms. The running time of all benchmark instances is less than five minutes.

Figure 22 shows the best solution for the instance problem of benchmark \(10\times 10^{-2}\) obtained by the EGA_OS.

Table 9 The classified instances
Full size table
Table 10 Computational results for the Benchmark of Taillard (Taillard 1993) \(4\times 4\), \(5\times 5\), \(7\times 7\), and \(10\times 10\)
Full size table
Table 11 Computational results for the Benchmark of Taillard (Taillard 1993) \(15\times 15\) and \(20\times 20\)
Full size table
Fig. 22
figure 22

Schedule for an instance of benchmark \(10\times 10^{-2}\) with a makespan of 588

Full size image

8 Conclusion

In this paper, the effects of selected crossover and mutation operators on the proposed algorithm (EGA_OS) for solving the Open-Shop Scheduling Problem are investigated and it has been proved that these operators have greatly influenced the efficiency of the Genetic Algorithm. Also, the proposed algorithm is compared with the other algorithms, and the results showed the EGA_OS could find more optimal solutions for all kinds of problems and could find them in shorter computational times compared to the other algorithms. In other words, applying the proposed Genetic Algorithm (EGA_OS) for solving the Open-Shop Scheduling Problem was largely dependent on selecting the type of crossover and mutation operators. Employment of suitable crossover and mutation operators in the EGA_OS led to a goal-oriented dispersion of the chromosomes in the problem space and to find better solutions. Results show that hybrid selection in the Genetic Algorithm worked well for solving the Open-Shop Scheduling Problem and that the use of the One-point Crossover Operator together with the Displacement Mutation Operator resulted in finding solutions better and faster. However, applying different operators resulted in increasing the time complexity of the proposed solution method compared to the state-of-the-art methods. As a future work, it is recommended to make some changes in the proposed method that can parallelly work for different types of mutation and crossover operators. Also, we can consider more real assumptions in the model such as jobs release date and synchronous processing cycles.