Flexible open-shop problem for minimizing weighted total completion time

Abstract

In this article, scheduling flexible open shops with identical machines in each station is studied. A new mathematical model is offered to describe the overall performance of the system. Since the problem enjoys an NP-hard complexity structure, we used two distinct metaheuristic methods to achieve acceptable solutions for minimizing weighted total completion time as the objective function. The first method is customary memetic algorithm (MA). The second one, MPA, is a modified version of memetic algorithm in which the new permutating operation is replaced with the mutation. Furthermore, some predefined feasible solutions were imposed in the initial population of both MA and MPA. According to the results, the latter action caused a remarkable improvement in the performance of algorithms.

Keywords

Flexible open shop mixed integer linear programming memetic algorithm permutating operation taguchi method

1 Introduction

Production scheduling is to determine the processing order of n jobs on m machines, according to some restrictions, to achieve some objective function(s). Normally, each job is combined of some operations, and each machine can process one or more special operations. If there are no constraints on the processing order of any jobs’ operations, we encounter the open shop problem [1 , 25]. By flexibility, we mean that there are some distinct stations in a shop, each station consisting of parallel machines and dedicated to a special operation [14 , 21]. In flexible open-shops, the notions of classical open-shops and parallel machine shops are combined in order to increase the total capacity and output of the shop, to balance the speed of processing in each station, and to decrease or even remove the effect of bottleneck stations [3, 16].

1.1 Problem statement

Flexible open shop is a special case of multiprocessor open shops [21]. In this paper we assume that there are m distinct stations and n outstanding jobs. The operations of job j require processing with no predetermined orders. Each station i (1 ≤ i ≤ m) contains r_i ≥ 1 identical machines that are all dedicated to a special operation. Hence, each station exactly corresponds to one operation. In otherwords, if job j needs operation i for completion, it should be processed without any interruptions on just one of the machines in station i, no difference on which one. So, it is possible to process at most r_i jobs simultaneously in station i. The processing time P_ji of job j on station i is predetermined and depends on the job. If job j does not need processing in station i, then P_ji = 0. It is not possible to process a job on two stations simultaneously. The problem aims to find the completion time V_ji of job j in station i, and also the machine s (1 ≤ s ≤ r_i) that the job should be processed on, to minimize the weighted total completion time (WTCT) of jobs. By using the triple α|β|γ, we can state the problem as FOm||∑w_jC_j, where FOm indicates the Flexible Open Shop problem with Identical Parallel Machines (FOSIPM) in m stations, and ∑w_jC_j is the weighted total completion time, in which w_j is the weight (relative importance coefficient) of job j, and C_j is the completion time of it [17]. The following example illustrates the situation:

Example 1.1. In a large auto repair shop, so many services are offered in different stations, such as repairment and services for motor, transmissions, body, electrical parts, brakes, exhaust system, etc. In the morning, the cars are admitted and given a number j (in order) as they arrive. To each number j a weight w_j is assigned (smaller j, bigger w_j). Assume that all technicians and mechanics in any station of the shop have the same level of expertise, and that the organizers can estimate the time spent in each station for each car. Also, suppose the services that take done on each car are independent and have no predefined orders. Our problem is to find the completion time of service for any car j in station i, and the technician s in station i who works on car j, to minimize ∑w_jC_j, the weighted total completion time for all admitted jobs, where C_j is the completion time of all necessary services for car j. Hence, in the context of flexible open shop problem, the job j means the set of all operations that should be performed on the j^th car, and a machine in the station i is just a technician in that station.□

1.2 Literature

The problem FOSIPM does not have so much background in the literature. To the best of the authors’ knowledge, Sevastianov and Woeginger in [22] are the first to study this problem. Without any mathematical formulation, they have proposed a polynomial-time approximation scheme to solve FOSIPM to minimize the makespan. Matta in [16] has published an article in which there are some real examples and two distinct mathematical models to describe the problem, and a genetic algorithm (GA) is developed to schedule the shop to minimize the makespan. In [3], Naderi et al. developed a new formulation and tried to tackle the problem through a memetic algorithm (MA) together with simulated annealing for the local search to minimize the total completion time. However, the mathematical models in two recent articles utilize the limiting hypothesis “every job should be processed in all stations”. Example 1.1 shows that this is not satisfied in some cases of FOSIPM.

There are few references for flexible open shop other than those mentioned above. Trail and Ventura in [4] have studied a combination of FOSIPM together with the well-known traveling salesman problem (TSP) in a bi-objective optimization framework, for minimizing both the makespan and overall costs of operations. A two-phase metaheuristic algorithm is provided by them as the solving method. Bai et al. in [5] have investigated the static and dynamic versions of the FOSIPM to minimize makespan. Without any mathematical formulations, the differential evolution algorithm (DE) is applied to moderate scale problems for obtaining acceptable approximate solutions. In [7], Hurtado Villamizar et al. have considered a Flexible Open-Flow Shop scheduling problem to minimize makespan. They have inspired the formulation of the problem from [16], and offered a solution method based on GA. Behnamian, Memar Dezfooli, and Asgari in [12] have examined a biobjective flexible open shop structure with independent setup times. A modified scatter search is developed to solve the problem, and the results are compared with NSGA-II.

The first step in tackling this sort of optimization problems is to provide an accurate mathematical model. Here, this is done in the form of a mixed integer linear programming (MILP) model. Because of NP-hardness of FOSIPM, two distinct metaheuristics for solving process are proposed: customary memetic algorithm (MA), and a new modified version of MA developed by substituting the so called ‘permutating operation’ instead of mutation, which we named as MPA. Furthermore, the reasons for selecting MA-based algorithms are explained. A well-known trick is applied to improve the performance of algorithms, that is; imposing some predefined solutions in the initial population of MA (and MPA). For tuning the parameters and measuring the performance of each algorithm, the Taguchi method is proposed for its accuracy and time-saving specifications. Statistical analyzes are used to show the efficiency of model, and also to compare the performance of algorithms.

By comparing this article with the existing background, the new findings can be enumurated as follows:

A novel MILP model is developed that has not been adderssed in the previous works. This model is tested by the commercial software CPLEX 11, and for some instances the outputs of it are compared with the outputs of a software developed by authors (in which all of the points of the feasible space are evaluated to find the optimal solution). Similarity of the results confirms correctness of the mathematical model.

The problem is solved by two algorithms: customary memetic algorithm (MA), and a novel modified version of MA, called as memetic algorithm with permutating operation (MPA).

By imposing some special predefined solutions in the initial population of both MA and MPA, a remarkable improvement in the output solutions was appeared. These versions are named as MAI and MPAI; respectively.

1.3 Article organization

After introduction, a new Mixed Integer Linear Programming (MILP) model for this problem is offered in section 2. Section 3 is devoted to introduce the metaheuristic algorithms that are applied to solve the model. In section 4, it is described that how some feasible points are defined and added to the initial population of both MA and MPA to improve their performance. In section 5, the results of executing algorithms are statistically studied to determine the best parameters for each algorithm and compare their performance. Finally, some conclusions and suggestions are offered in section 6.

2 Formulation of the problem

In this section an MILP model for formulating FOSIPM to minimize WTCT is offered. Although this model is inspired by the models in [3] and [16], significant improvements have been made in it. Some shortcomings are fixed, including the ability to describe the situations in which every job does ‘not’ necessarily need processing in all stations, unlike the models in the above mentioned articles. Here, we show the ith operation of job j by O_ji.

First of all, consider some additional assumptions:

1. All jobs are independent and available in the beginning,

2. All machines are available at the zero time, and can work continuously,

3. Each machine can only process one job in a specific time,

4. The processing procedure of each operation of a job on a machine must be done continuously and without any interrupts,

5. There is unlimited buffer between any two stations,

6. The transportation time between stations is zero,

7. The processing time P_ji of O_ji is a nonnegative integer number.

8. There are more than one jobs to be processed.

The most important step in defining a mathematical model is the definition of decision variables. In this problem, the processing time P_ji of operation O_ji is given for all j and i, and the variables should be defined such that the following are determined in any optimal solution:

1. The processing completion time of each job j in any station i (completion time of O_ji),

2. The specific machine in each station that the job should be processed on.

The parameters used in this model are as follows:

n: The number of jobs, m: The number of stations,

r_i: The number of (identical) machines in station i,

O_ji: The operation i of job j (that should be processed on just one of the identical machines in station i),

P_ji: The processing time of O_ji,

M: A large positive number,

B: The set {0, 1},

$ℤ^{+}$ : The set of nonnegative integer numbers,

E = {(j, i) : P_ji > 0, j ∈ {1, 2, . . . , n} , i ∈ {1, 2, . . . , m}}.

Also we have used the following indices:

j, h: Indices for jobs, j, h ∈ {1, 2, . . . , n},

i, k: Indices for stations, i, k ∈ {1, 2, . . . , m},

s: Index for machines in any station i, s ∈ {1, 2, . . . , r_i}.

The decision variables used in this model are the following:

$X_{jik} = {\begin{matrix} 1 & if O_{ji} is processed after O_{jk}, (j, i) \in E, \\ (j, k) \in E, k > i; \\ 0 & otherwise . \end{matrix}$

∈{1, 2, . . . , r_i} ;0 otherwise .

∈{1, 2, . . . , r_i} otherwise .

$Z_{jis} = {\begin{matrix} 1 & if O_{ji} is processed on s th machine \\ in station i, (j, i) \in E, 1 \leq s \leq r_{i}; \\ 0 & otherwise . \end{matrix}$

V_ji: The completion time of job j in station i, (j,i) ∈ E.

C_j: The completion time of job j, 1 ≤ j≤ n.

It should be noted that Y_jhis = 0 may happen in three cases:

1) O_hi is processed after O_ji on sth machine in station i, (hence; $Y_{jhis}^{'} = 1$ ),

2) None of O_ji and O_hi are processed on sth machine in station i,

3) One of O_ji or O_hi is processed on sth machine in station i, and the other is processed on another machine.

In a similar way, $Y_{jhis}^{'} = 0$ can occur in 3 different situations.

The mathematical model is as follows:

$min \sum_{j = 1}^{n} w_{j} C_{j}$ (2.1) $s . t . \sum_{s = 1}^{r_{i}} Z_{jis} = 1, (j, i) \in E;$ (2.2) $\begin{matrix} V_{ji} \geq P_{ji}, (j, i) \in E; \end{matrix}$ (2.3) $\begin{matrix} V_{ji} \geq V_{jk} + P_{ji} - M (1 - X_{jik}), \\ (j, i) \in E, (j, k) \in E, k > i; \end{matrix}$ (2.4) $\begin{matrix} V_{jk} \geq V_{ji} + P_{jk} - M X_{jik}, \\ (j, i) \in E, (j, k) \in E, k > i; \end{matrix}$ (2.5) $\begin{matrix} V_{ji} \geq V_{hi} + P_{ji} - M (1 - Y_{jhis}), \\ (j, i) \in E, (h, i) \in E, h > j, \\ 1 \leq s \leq r_{i}; \end{matrix}$ (2.6) $\begin{matrix} V_{hi} \geq V_{ji} + P_{hi} - M (1 - Y_{jhis}^{'}), \\ (j, i) \in E, (h, i) \in E, h > j, \\ 1 \leq s \leq r_{i}; \end{matrix}$ (2.7) $\begin{matrix} Y_{jhis} + Y_{jhis}^{'} \geq Z_{jis} + Z_{his} - 1, \\ (j, i) \in E, (h, i) \in E, h > j, \\ 1 \leq s \leq r_{i}; \end{matrix}$ (2.8) $\begin{matrix} 2 (Y_{jhis} + Y_{jhis}^{'}) \leq Z_{jis} + Z_{his}, \\ (j, i) \in E, (h, i) \in E, h > j, \\ 1 \leq s \leq r_{i}; \end{matrix}$ (2.9) $C_{j} \geq V_{ji}, (j, i) \in E;$ (2.10) $V_{ji} \in ℤ^{+}, C_{j} \in ℤ^{+}, (j, i) \in E;$ (2.11)

$\begin{matrix} X_{jik} \in B, (j, i) \in E, (j, k) \in E, \\ k > i; \end{matrix}$ (2.12) $\begin{matrix} Y_{jhis} \in B, (j, i) \in E, (h, i) \in E, \\ h > j, 1 \leq s \leq r_{i}; \end{matrix}$ (2.13) $\begin{matrix} Y_{jhis}^{'} \in B, (j, i) \in E, (h, i) \in E, \\ h > j, 1 \leq s \leq r_{i}; \end{matrix}$ (2.14) $Z_{jis} \in B, (j, i) \in E, 1 \leq s \leq r_{i} .$ (2.15)

Relation (2.1) is the objective function that should be minimized. Relation (2.2) ensures that the processing of a job in a station is done on just one of the machines of that station. Relation (2.3) states that the completion time of each operation is greater than or equal to its processing time. Relations (2.4) and (2.5) guarantee that the processing time intervals of one job on two different stations can not overlap. Constraints (2.6) and (2.7) examine the completion times and orders of processing for each pair of jobs that should be done on the same machine at a station. Constraints (2.8) and (2.9) make relations among the variables Y_jihs, $Y_{jihs}^{'}$ , Z_jis and Z_his. Especially, they emphasis that both Y_jihs and $Y_{jihs}^{'}$ can not be equal to 1 together. Relation (2.10) states that the completion time of each job is greater than or equal to its completion time on each station. Condition (2.11) ensures that V_ji and C_j are nonnegative integers. (2.12), (2.13), (2.14) and (2.15) show that the variables X_jik, Y_jihs, $Y_{jihs}^{'}$ and Z_jis are all binary ones.

2.1 Model verification

To check the correctness of MILP model, we used the commercial software CPLEX 11, and compared the results for some small-sized instances to the outputs of a small program designed in MATLAB 17. The latter program performed a total search on all feasible points of the given instance to find the best solution of that instance. We implemented all algorithms on a PC with 1.73 GHz Intel Core i7 CPU and 4 GB of internal memory (RAM).

The instances were produced with n = 10, 20 and 30 jobs, m = 5, 10 stations and 1 to 4 randomly selected machines in each station. Also, the processing times were chosen randomly in [0, 15]. For n = 30 and m = 10, CPLEX spent 972 seconds to obtain the optimal solution of the given data set.

In all cases, the CPLEX optimal solutions were precisely the same as the outputs we gained by our program, which verifies the correct performance of the MILP model. For n = 50 and m = 10, CPLEX was unable to produce an acceptable output (on our system). All these instances are also applied to our suggested metaheuristic algorithms MA and MPA, and the results are discussed and compared in subsection 5.1.

3 Solution methods

In this section, the selected algorithms for solving the problem FOm||∑w_jC_j are discussed. Also, we briefly explain our reasons for choosing the algorithms.

3.1 Computational complexity

Achugbue and Chin in [13] proved that the open shop problem O2||∑C_j is NP-hard. Based on the notion of polynomial reducibility [14], since O2||∑C_j as a special case of FOm||∑w_jC_j is NP-hard, FOm||∑w_jC_j is NP-hard too.

3.2 Metaheuristic Algorithms

There has not already found any polynomial time algorithms that can solve all instances of an NP-hard problem exactly. So, inexact methods are normally used to obtain approximate, yet acceptable, answers in a reasonable time. Metaheuristic algorithms are one of the most popular methods for solving NP-hard problems. They derive their inspiration from natural behaviour of creatures and different phenomena, and have been proven to be efficient for many types of optimization problems.

In [25] the literature of applying intelligent algorithms to solve the open shop problem is reviewed. As mentioned before, we have chosen memetic algorithm (MA) and some modified versions of it to solve FOSIPM. The main reasons for such a selection is explained in the subsection 3.4. Before then, the special method for displaying a feasible solution in our solving algorithms is described.

3.3 Permutation lists

In an optimization problem, a feasible solution is a vector x of variables that satisfies all constraints, and the feasible space is the set of all feasible solutions. In all metaheuristic algorithms, to represent feasible solutions we must transform them into a special structure. This transformation is called encoding. Choosing a suitable method for encoding is a function of the type of the problem, and plays an important role in effectiveness of that algorithm.

For solving scheduling problems, many algorithms use permutation lists as the basis for encoding process. In FOSIPM, if we have n jobs that should be processed in m stations, there will be m × n operations for processing. We define a permutation list to be an m × n ordered vector in which every entry includes exactly one of the O_jis. In some cases it is possible that a job j does not need some operation i for completion. It means that this job j should not be processed in corresponding station i and the number of all operations to be processed in all stations is less than m × n. However, for simplicity in implementing the solving algorithms, we will consider this kind of operations in the permutation list, although their processing time is set to zero.

Furthermore, to complete the encoding process, we need a rule to change each permutation list into a schedule. Here, we offer the rule that leads to a semi-active scheduling [17], in which every operation O_ji will be processed according to its order of appearance in permutation list, and this will be done just when the job j and at least one machine in the corresponding station i are accessiable. This procedure is illustrated more precisely in Figure 1, which shows the pseudocode for encoding a given permutation list and computing the WTCT of it. Remind that by $\underset{1 \leq i \leq n}{argmin} {x_{i}}$ , we mean the set of all indices j that $x_{j} = \min_{1 \leq i \leq n} {x_{i}}$ .

Fig. 1

Pseudocode for computing WTCT of permutation lists.

It should be noted that there are more encoding rules [17], however; the semi-active scheduling rule is chosen for its simplicity in applications, and containing all “suitable” feasible solutions, specially the best solution.

Example 3.1. Consider a flexible open shop problem with n = 4 jobs and m = 3 stations S₁, S₂ and S₃ with the following data: r₁ = 2, r₂ = 1, r₃ = 4, w₁ = w₂ = w₃ = w₄ = 1 .

The processing times of operations are: P₁₁ = 8, P₁₂ = 18, P₁₃ = 20, P₂₁ = 0, P₂₂ = 11, P₂₃ = 10, P₃₁ = 31, P₃₂ = 0, P₃₃ = 14, P₄₁ = 34, P₄₂ = 12, P₄₃ = 42 .

Let θ be the following permutation list: θ = (O₄₃, O₃₁, O₄₂, O₄₁, O₃₃, O₃₂, O₁₃, O₂₂, O₁₁,

O₂₃, O₁₂, O₂₁) .

The Gantt chart of the above permutation list is obtained from the pseudocode in Figure 1, and demonstrated in Figure 2. The numbers in the boxes below the chart show the completion time of each job. It is obvious that WTCT = 291. □

Fig. 2

Gantt chart for example 3.1.

If the positions of the first three processes in the above permutation list commute, we get the same Gantt chart. Therefore, six different permutation lists lead to similar Gantt charts. These repeated cases are confronted frequently and cause some malfunctioning of solving algorithms. However, the number of these permutation lists is by no means distinguishable, and is a function of the number and weight of jobs, number of stations and machines in each station, processing time of each job in each station, and even the rule of encoding. Anyway, there are some sufficient conditions under which similar Gantt charts are created. For example, consider the following cases:

Case 1. Let θ be a permutation list, and P_{j
₀
i
₀} is zero for some O_{j
₀
i
₀}. Any permutation list that is obtained by moving O_{j
₀
i
₀} among other elements of θ, results in a permutation list θ′ that produces the same Gantt chart as θ.

Case 2. In a permutation list θ, let the first k entries θ (1),θ (2),...,θ (k), where $k \leq \sum_{i = 1}^{m} r_{i}$ , contain O_jis with distinct indices j, and the number of incidences of each index i (1 ≤ i ≤ m), among these k entries is less than or equal to r_i. In this case, all these k operations begin from zero time. So, every commutation of these O_jis leads to the same Gantt chart.

Although the above mentioned undesirable situation may occur frequently, it can be solved to a large extent by using local search in MA.

3.4 Memetic Algorithm

Since the memetic algorithm (MA) is a combination of genetic algorithm (GA) with some kind of local search, in this section the most important aspects of GA and the suggested local search method applied to solve FOSIPM are described. First, we explain the reasons for choosing the memetic algorithm:

There is a strong philosophy of evolution and transmission in the stages of MA [8],

MA shows an extraordinary performance in combinatorial optimization, specially when the parameters are properly adjusted and there is a suitable balance between genetic search and local search [8 , 19],

The local search in MA (and MPA) causes considering more feasible points in each stage of algorithm, and this can decrease the probability of confronting points with similar Gantt charts. Also, the ability of imposing some predetermined feasible points in the initial population of MAI and MPAI helps to have more miscellaneous Gantt charts.

For more details the reader can refer to [2].

Generally, in GA (and MA) the feasible space of an optimization problem is searched intelligently to fulfill two objects: exploitation and exploration. Exploitation makes the algorithm analyse a part of the feasible space intensively to enhance the best current solution quickly, where exploration tends to extend the search to the solutions that are situated in other portions of the feasible space that may have already been unexplored. Hence, exploration prevents the solutions to tend to a local extreme instead of a global one.

Figure 3 shows a general scheme of MA, where exploitation is done by crossover and exploration by mutation operators. By population, we mean a subset of feasible space. In each execution of main step, after crossover, mutation and local search, it is likely that some new feasible solutions be added to the present population, and based upon their evaluation by “fitness function” (ordinary, the objective function of the optimization problem), they will have the chance to be in the next step’s population.

Fig. 3

Pseudocode of memetic algorithm.

The reader must point out that every feasible point in MA is called a chromosome, and in our solving method for FOSIPM problem a chromosome is indeed a permutation list. The method of choosing the initial population of feasible solutions (permutation lists) is explained in section 4 in details. In the following, we describe the details of suggested crossover, mutation and local search to make new chromosomes from the old ones in MA to solve FOSIPM.

3.4.1 Crossover operation

In FOSIPM, suppose that n jobs should be processed in m stations and θ₁ and θ₂ are two chromosomes (permutation lists) that are selected by an elite operator from some population in MA. We will name θ₁ and θ₂ as parents. Here we use some sort of two point crossover method, to produce two new chromosomes $θ_{1}^{'}$ and $θ_{2}^{'}$ known as offsprings from the parents. To this end

1. Two random integer numbers k₁ and k₂ are selected, where 1 ≤ k₁ ≤ k₂ ≤ m × n,

2. For k₁ ≤ k ≤ k₂, let $θ_{1}^{'} (k) = θ_{1} (k)$ and $θ_{2}^{'} (k) = θ_{2} (k)$ ,

3. Other entries of $θ_{1}^{'}$ are selected from θ₂ by preserving their orders, such that none of them is among the entries of θ₁ (k₁) to θ₁ (k₂). In a similar manner, other entries of $θ_{2}^{'}$ are selected from θ₁ by preserving orders.

Example 3.2. Let m = 3, n = 4, k₁ = 3 and k₂ = 8 are given, and also $θ_{1} = (O_{23}, O_{31}, \underline{O_{42}, O_{32}, O_{11}, O_{22}, O_{21}, O_{33}}, O_{43},$

O₁₃, O₄₁, O₁₂) ,

$θ_{2} = (O_{31}, O_{42}, \underline{O_{21}, O_{22}, O_{33}, O_{12}, O_{41}, O_{32}}, O_{43},$

O₁₁, O₂₃, O₁₃) .

Hence, we will get $θ_{1}^{'} = (O_{31}, O_{12}, \underline{O_{42}, O_{32}, O_{11}, O_{22}, O_{21}, O_{33}}, O_{41},$

O₄₃, O₂₃, O₁₃) ,

$θ_{2}^{'} = (O_{23}, O_{31}, \underline{O_{21}, O_{22}, O_{33}, O_{12}, O_{41}, O_{32}}, O_{42},$

O₁₁, O₄₃, O₁₃) . □

3.4.2 Mutation operation

Let θ be a given chromosome. For mutation, we select two random integers k₁ and k₂ (1 ≤ k₁, k₂ ≤ m × n), and then simply exchange the entries θ (k₁) and θ (k₂).

Example 3.3. Let, m = 3, n = 4, k₁ = 3, k₂ = 10, and θ be the chromosome $θ = (O_{23}, O_{31}, \underline{O_{42}}, O_{32}, O_{11}, O_{22}, O_{21}, O_{33}, O_{43},$ $\underline{O_{13}}, O_{41}, O_{12}) .$

After a successful mutation, θ will be changed to

$\underline{O_{42}}, O_{41}, O_{12}) . □$

3.4.3 Local search

As mentioned before, local search not only increases the performance of algorithms, but also is a way to overcome identical Gantt chart problems. We suggested the following method for local search:

(1) For every permutation list θ, select a random integer k ( $1 \leq k \leq \frac{m \times n}{2}$ ), that gives the number of new permutation lists in the neighborhood of θ to be examined.

(2) Each of the k new feasible solutions are obtained from θ in this way: an integer t (1 ≤ t ≤ m × n - 1) is randomly chosen, and then θ (t) and θ (t + 1) are exchanged to get a new permutation list. For example, if m = 3, n = 4, k = 2, t = {4, 11}, and $θ = (O_{23}, O_{31}, O_{42}, \underline{O_{32}}, O_{11}, O_{22}, O_{21}, O_{31}, O_{43},$

$O_{13}, \underline{O_{41}}, O_{12});$

then for t = 4, we get θ₁ = (O₂₃, O₃₁, O₄₂, O₁₁, O₃₂, O₂₂, O₂₁, O₃₁, O₄₃,

O₁₃, O₄₁, O₁₂) ;

and for t = 11 we get θ₂ = (O₂₃, O₃₁, O₄₂, O₃₂, O₁₁, O₂₂, O₂₁, O₃₁, O₄₃,

O₁₃, O₁₂, O₄₁) .

(3) Finally, the WTCTs of k new permutations together with θ are evaluated, and the best (minimum) of them will be replaced with θ.

It is clear that this procedure will lead to consider more various permutation lists, and the final selected chromosome has a Gantt chart whose fitness function value is not worse than the original one.

3.5 Memetic Algorithm with permutating operation (MPA)

In this section we introduce permutating operation, a novel operation which uses algebraic properties of permutation lists to produce new permutation lists. The main difference between MA and MPA is that mutation in MA is replaced with permutating operation in MPA for more exploration in the feasible space. It should be noted that unlike mutation, the permutating operation gets two random chromosomes, and finally produces two new ones. The following subsections describe this procedure.

3.5.1 Symmetric group on n letters

Recall from algebra that if f : A ⟶ B and g : B ⟶ C are two functions, then the composition of g and f, g ∘ f : A ⟶ C is a function, such that $\forall x \in A, g \circ f (x) = g (f (x)) .$ Now, consider the set S_n = {1, 2, . . . , n}. Every bijection (one to one and onto function) θ : S_n ⟶ S_n is called an n-letter permutation on S_n. It can be proved that if θ₁ and θ₂ are permutations on S_n, then both of θ₁ ∘ θ₂ and θ₂ ∘ θ₁ are also permutations on S_n [23].

To denote a permutation θ we use this notation $θ = (\begin{matrix} \begin{matrix} \begin{matrix} 1 & 2 \end{matrix} & 3 & ... & n \end{matrix} \\ \begin{matrix} \begin{matrix} i_{1} & i_{2} \end{matrix} & i_{3} & ... & i_{n} \end{matrix} \end{matrix}),$

where i₁, i₂, . . . , i_n are distinct elements of S_n. This shows that θ (1) = i₁, θ (2) = i₂, θ (3) = i₃, . . . , θ (n) = i_n .

Example 3.4. Consider the 4-letter permutations $\begin{array}{l} θ_{1} = (\begin{matrix} \begin{matrix} 1 & 2 & 3 & 4 \end{matrix} \\ \begin{matrix} 4 & 2 & 1 & 3 \end{matrix} \end{matrix}), θ_{2} = (\begin{matrix} \begin{matrix} 1 & 2 & 3 & 4 \end{matrix} \\ \begin{matrix} 3 & 1 & 4 & 2 \end{matrix} \end{matrix}), and \\ ι = (\begin{matrix} \begin{matrix} 1 & 2 & 3 & 4 \end{matrix} \\ \begin{matrix} 1 & 2 & 3 & 4 \end{matrix} \end{matrix}) \end{array}$

on S₄. Then, $θ_{1} \circ θ_{2} = (\begin{matrix} \begin{matrix} 1 & 2 & 3 & 4 \end{matrix} \\ \begin{matrix} 1 & 4 & 3 & 2 \end{matrix} \end{matrix}), θ_{2} \circ θ_{1} = (\begin{matrix} \begin{matrix} 1 & 2 & 3 & 4 \end{matrix} \\ \begin{matrix} 2 & 1 & 3 & 4 \end{matrix} \end{matrix}) .$

Obviously, “ι” is the identity permutation on S₄, that is θ₁ ∘ ι = ι ∘ θ₁ = θ₁ . □

3.5.2 Permutating operation

Now, we turn back to the permutation lists. Assume that there are n jobs that should be processed in m stations. First, we put an order on the operations O_ji, and correspond this order with natural order of numbers 1 ≤ 2 ≤ . . . ≤ mn - 1 ≤ mn. In this article, we select the lexicographic order O_ji ≥ O_j′i′ ⇔ (j > j′) or (j = j′ and i ≥ i′) ,

and then make correspondence between any permutation list, with a permutation on mn-letters. The next example clears this process.

Example 3.5. Let n = 4, m = 3, and let the permutation lists θ₁ and θ₂ be given by θ₁ = (O₂₃, O₃₁, O₄₂, O₃₂, O₁₁, O₂₂, O₂₁, O₃₃, O₄₃,

O₁₃, O₄₁, O₁₂) ,

θ₂ = (O₃₁, O₄₃, O₂₁, O₂₂, O₃₃, O₁₂, O₄₁, O₃₂, O₄₂,

O₁₁, O₂₃, O₁₃) .

Consider that lexicographic order establishes the following correspondences:

$\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ ↕ & ↕ & ↕ & ↕ & ↕ & ↕ & ↕ & ↕ & ↕ & ↕ & ↕ & ↕ \\ O_{11} & O_{12} & O_{13} & O_{21} & O_{22} & O_{23} & O_{31} & O_{32} & O_{33} & O_{41} & O_{42} & O_{43} \end{matrix}$

Therefore, we can correspond θ₁ and θ₂ with 12-letter permutations σ₁ and σ₂, respectively; as follows $σ_{1} = (\begin{array}{l} 1 2 3 4 5 6 7 8 9 10 11 12 \\ 6 7 11 8 1 5 4 9 12 3 10 2 \end{array}),$

$σ_{2} = (\begin{array}{l} 1 2 3 4 5 6 7 8 9 10 11 12 \\ 7 12 4 5 9 2 10 8 11 1 6 3 \end{array}) . □$

Now, if two chromosomes (permutation lists) θ₁ and θ₂ are selected for permutating operation in MPA, we first find the corresponding permutations on mn-letters σ₁ and σ₂, and then obtain σ₁ ∘ σ₂ and σ₂ ∘ σ₁. At last, we transform σ₁ ∘ σ₂ and σ₂ ∘ σ₁ to two new chromosomes $θ_{1}^{'}$ and $θ_{2}^{'}$ . The following example demonstrates the procedure.

Example 3.6. In the previous example, let θ₁ and θ₂ be two chromosomes, that must be combined to get new chromosomes $θ_{1}^{'}$ and $θ_{2}^{'}$ by permutating operation. Following that example, σ₁ ∘ σ₂ and σ₂ ∘ σ₁ are simply computed: $σ_{1} \circ σ_{2} = (\begin{array}{l} 1 2 3 4 5 6 7 8 9 10 11 12 \\ 4 2 8 1 12 7 3 9 10 6 5 11 \end{array}),$

$σ_{1} \circ σ_{2} = (\begin{array}{l} 1 2 3 4 5 6 7 8 9 10 11 12 \\ 2 10 6 8 7 9 5 11 3 4 1 12 \end{array}) .$

Hence, the chromosomes $θ_{1}^{'}$ and $θ_{2}^{'}$ that correspond to σ₁ ∘ σ₂ and σ₂ ∘ σ₁, are obtained as: $θ_{1}^{'} = (O_{21}, O_{12}, O_{32}, O_{11}, O_{43}, O_{31}, O_{13}, O_{33}, O_{41},$

O₂₃, O₂₂, O₄₂) ,

$θ_{2}^{'} = (O_{12}, O_{41}, O_{23}, O_{32}, O_{31}, O_{33}, O_{22}, O_{42}, O_{13},$

O₂₁, O₁₁, O₄₃) .□

4 Imposing the initial feasible points

The set of feasible solutions with which the solving algorithms start is called the initial population. The number of members of initial population is one of the algorithm parameters that should be determined, and usually stays constant during the execution. The initial population is usually selected randomly, however; in the algorithms MAI and MPAI we have imposed some predetermined feasible solutions in addition to random ones in the initial population. This is done for making more variety in solutions, faster convergence of solutions, and avoiding similar Gantt charts. Among these points, there may be feasible solutions which are likely to have favorite WTCTs.

The sample pseudocode in Figure 4 together with the first row of Table 1 shows the way that leads to obtain one of these imposed points. We can achieve more imposed feasible points by some changes in that pseudocode, specially by replacing the values of i₀ and j₀ in Figure 4 with suggested i₀ and j₀ in Table 1. In addition, by reversing the order of entries (operations) at such a permutation list, another feasible point can be obtained.

Fig. 4

Sample outline for imposing initial solutions.

Table 1

Some imposed initial points based on Procedure ‘Imposed Solutions’

1	$i_{0} = \underset{1 \leq i \leq m}{argmax} {\sum_{j = 1}^{n} P_{ji} / r_{i}}$	$j_{0} = \underset{1 \leq j \leq n}{argmax} {P_{{ji}_{0}}}$
2	$i_{0} = \underset{1 \leq i \leq m}{argmax} {\sum_{j = 1}^{n} P_{ji} / r_{i}}$	$j_{0} = \underset{1 \leq j \leq n}{argmin} {P_{{ji}_{0}}}$
3	$i_{0} = \underset{1 \leq i \leq m}{argmax} {r_{i}}$	$j_{0} = \underset{1 \leq j \leq n}{argmax} {P_{{ji}_{0}}}$
4	$i_{0} = \underset{1 \leq i \leq m}{argmax} {r_{i}}$	$j_{0} = \underset{1 \leq j \leq n}{argmin} {P_{{ji}_{0}}}$
5	$i_{0} = \underset{1 \leq i \leq m}{argmin} {r_{i}}$	$j_{0} = \underset{1 \leq j \leq n}{argmax} {P_{{ji}_{0}}}$
6	$i_{0} = \underset{1 \leq i \leq m}{argmin} {r_{i}}$	$j_{0} = \underset{1 \leq j \leq n}{argmin} {P_{{ji}_{0}}}$
7	$i_{0} = \underset{1 \leq i \leq m}{argmax} {P_{ji} j = 1, \dots, n}$	$j_{0} = \underset{1 \leq j \leq n}{argmax} {P_{{ji}_{0}}}$
8	$i_{0} = \underset{1 \leq i \leq m}{argmax} {P_{ji} j = 1, \dots, n}$	$j_{0} = \underset{1 \leq j \leq n}{argmin} {P_{{ji}_{0}}}$
9	$i_{0} = \underset{1 \leq i \leq m}{argmax} {\sum_{j = 1}^{n} P_{ji}}$	$j_{0} = \underset{1 \leq j \leq n}{argmax} {P_{{ji}_{0}}}$
10	$i_{0} = \underset{1 \leq i \leq m}{argmax} {\sum_{j = 1}^{n} P_{ji}}$	$j_{0} = \underset{1 \leq j \leq n}{argm in} {P_{{ji}_{0}}}$
11	$j_{0} = \underset{1 \leq j \leq n}{argmax} {\frac{\sum_{i = 1}^{m} P_{ji}}{w_{j}}}$	$i_{0} = \underset{1 \leq i \leq m}{argmax} {P_{j_{0} i}}$
12	$j_{0} = \underset{1 \leq j \leq n}{argmax} {\frac{\sum_{i = 1}^{m} P_{ji}}{w_{j}}}$	$i_{0} = \underset{1 \leq i \leq m}{argmin} {P_{j_{0} i}}$
13	$i_{0} = \underset{1 \leq i \leq m}{argmax} {\sum_{j = 1}^{n} w_{j} \times P_{ji}}$	$j_{0} = \underset{1 \leq j \leq n}{argmax} {w_{j} \times P_{{ji}_{0}}}$
14	$i_{0} = \underset{1 \leq i \leq m}{argmax} {\sum_{j = 1}^{n} w_{j} \times P_{ji}}$	$j_{0} = \underset{1 \leq j \leq n}{argmin} {w_{j} \times P_{{ji}_{0}}}$
15	$i_{0} = \underset{1 \leq i \leq m}{argmax} {\frac{\sum_{j = 1}^{n} w_{j} \times P_{ji}}{r_{i}}}$	$j_{0} = \underset{1 \leq j \leq n}{argmax} {w_{j} \times P_{{ji}_{0}}}$
16	$i_{0} = \underset{1 \leq i \leq m}{argmax} {\frac{\sum_{j = 1}^{n} w_{j} \times P_{ji}}{r_{i}}}$	$j_{0} = \underset{1 \leq j \leq n}{argmin} {w_{j} \times P_{{ji}_{0}}}$

Example 4.1. Consider the data in example 3.3. Then, the feasible point achieved by the pseudocode shown in Figure 4 is θ = (O₁₂, O₄₁, O₄₂, O₄₃, O₃₁, O₁₃, O₂₂, O₃₃, O₁₁,

O₂₃, O₃₂, O₂₁) ,

in which WTCT is 246. If we reverse the order of operations, the feasible point θ₁ = (O₂₁, O₃₂, O₂₃, O₁₁, O₃₃, O₂₂, O₁₃, O₃₁, O₄₃,

O₄₂, O₄₁, O₁₂)

is obtained, that has a WTCT equal to 226. For another feasible point, by changing $j_{0} = \underset{1 \leq j \leq n}{argmax} {P_{{ji}_{0}}}$ to $j_{0} = \underset{1 \leq j \leq n}{argmin} {P_{{ji}_{0}}}$ in the above mentioned pseudocode, we get θ′ = (O₃₂, O₂₂, O₂₁, O₁₁, O₃₁, O₄₂, O₂₃, O₃₃, O₁₂,

O₄₁, O₁₃, O₄₃) ,

with WTCT=226. □

5 Calibration of Algorithms and statistical analysis

In this section, we investigate the behavior of both MA and MPA with different parameters to realize the best performance of them. To this end, different methods of design of experiments (DOE) can be applied. However, we have chosen the Taguchi method for its accuracy and effectiveness [11].

There are two main classes of factors in Taguchi method: controllable and uncontrollable (noise) factors. The main objective of Taguchi method is to determine the best level of each controllable factor to improve the overall performance of experiment, which is measured by the signal to noise (S/N) ratio. It is proven that this strategy not only leads to best mean of output level, but also tends to the least variance of it. Taguchi has classified all objective functions into three categories [11]. For our problem, FOSIPM; the objective function falls into the category “smaller is better”, and hence the signal to noise ratio can be evaluated by $S / N = - 10 \log_{10}^{(WTCT)^{2}} .$ (5.16)

For MA, the probability of crossover (pc), probability of mutation (pm) and population size (npop) are selected as (controllable) factors, where probability of crossover(pc), probability of permutating operation (pperm) and population size (npop) are chosen for MPA. These factors and their levels are shown in Table 2. It can be seen that 3 levels are chosen for all factors in each algorithm. The software Minitab 17 suggested the L₉ orthogonal array for experiments as the most economical array. This array for 3 factors and 3 levels for each factor is given in [11].

Table 2

Factors and their levels for algorithms

MA			MPA
Factor	Levels	Value	Factor	Levels	Value
pc	3	A(1): 0.80	pc	3	A(1): 0.80
		A(2): 0.85			A(2): 0.85
		A(3): 0.90			A(3): 0.90
pm	3	B(1): 0.03	pperm	3	B(1): 0.15
		B(2): 0.05			B(2): 0.20
		B(3): 0.10			B(3): 0.25
npop	3	C(1): 20	npop	3	C(1): 20
		C(2): 30			C(2): 30
		C(3): 40			C(3): 40

To perform experiments, we generated two distinct sets of instances (sample data). The first set, known as small sized instances, contained 6 data sets in which n = 10, 20, 30 and m = 5, 10. In the second set (large sized instances) there were 10 combinations of (n, m) with n = 50, 100, 200, 400, 500 and m = 10, 20. The number of machines in each station was selected randomly from 1 to 5. Also the processing times were randomly generated from the set {0, 1, …, 15}. Each trial was repeated 10 times. We implemented both MA and MPA on a PC with specifications mentioned in section 2.1. Two stopping criteria were used simultaneously for all instances in both algorithms: the number of iterations should not be more than 50 times, and the running times were limited to n × m seconds. The optimal level of factors A, B and C for both MA and MPA algorithms became A (2), B (2) and C (2), as shown in Figure 5. Hence, the selected parameters for MA were pc = o . 85, pm = o . 05, npop = 30 and for MPA pc = o . 85, pperm = o . 2 and npop = 30.

Fig. 5

The mean S/N ratio plot for each level of the factors of MA (left) and MPA (right).

5.1 Evaluation of metaheuristics for small-sized instances

If we suppose that small sized instances for FOSIPM are those instances in which n ≤ 30 and m ≤ 10 (as stated in the above subsection), then we can compare the outputs of two algorithms MA and MPA with exact optimal solutions obtained by CPLEX. Table 3 shows the results. It should be noted that each algorithm is applied in two situations: using imposed solutions in addition to random ones in initial set (MAI and MPAI) and without imposing them (MA and MPA). Furthermore, the outputs of each algorithm is the average of 10 repetitions for each instance.

Table 3
Outputs and the RPD obtained for small sized instances

Data Instance MILP Model Algorithm output (WTCT) RPD

n m CPLEX MA MPA MAI MPAI MA MPA MAI MPAI

10 5 372 440 432 414 411 18.27 16.12 11.29 10.48

10 10 727 778 756 727 727 7.01 3.98 0.00 0.00

20 5 448 735 730 638 651 64.06 62.94 42.41 45.31

20 10 1471 1920 1982 1665 1674 30.52 34.73 13.18 13.80

30 5 1507 2946 2916 1983 1975 95.48 93.49 31.58 31.05

30 10 2558 4138 3940 3100 3021 61.76 54.02 21.18 18.10

Data Instance	MILP Model	Algorithm output (WTCT)	RPD
10	5	372	440	432	414	411	18.27	16.12	11.29	10.48
10	10	727	778	756	727	727	7.01	3.98	0.00	0.00
20	5	448	735	730	638	651	64.06	62.94	42.41	45.31
20	10	1471	1920	1982	1665	1674	30.52	34.73	13.18	13.80
30	5	1507	2946	2916	1983	1975	95.48	93.49	31.58	31.05
30	10	2558	4138	3940	3100	3021	61.76	54.02	21.18	18.10

Since by growing the size of input data in instances, the outputs of algorithms grow up; we applied the relative percentage deviation (RPD) criterion defined by $RPD = \frac{{Alg}_{sol} - {Opt}_{sol}}{{Opt}_{sol}} \times 100,$ to balance the results (as shown in Table 3). Here, Alg_sol is the average of WTCTs of a given algorithm and Opt_sol is the WTCT obtained by CPLEX. Hereafter, the significance level α = 0.05 is assumed for all statistical tests that use the hypothesis testing [6]. For statistical comparison of the performance of algorithms for small sized data, first we should check if each set of sample data (RPDs of MA, MPA, MAI and MPAI) in all algorithms are normal or not. We used the normality test Anderson-Darling, and found that all the sets follow the normal distribution. So we did the analysis of variance (ANOVA), and observed that the four methods did not show a meaningful difference in their means for small sized instances, although the means for MAI and MPAI showed better outputs than MA and MPA (Figure 6).

Fig. 6

ANOVA to compare means of RPDs for small-sized instances.

5.2 Evaluation of the proposed metaheuristics on large-sized instances

This subsection is devoted to evaluate and compare the performance of four algorithms MA, MPA, MAI and MPAI for large-sized instances. The number of jobs and stations, processing times and number of machines at each station are the main specifications for each instance. We tested n = 50, 100, 200, 400, 500 jobs and m = 10, 20 stations, where the processing times were randomly generated over [0, 15]. Also, the number of machines at each station were selected randomly over [1, 5]. For stopping criteria, the number of iterations was limited to 50, and moreover; the execution time was limited to 30000 seconds on our system. This caused that the number of iterations for each instance to be between 15 and 50. The results are shown in Table 4.

Table 4
Outputs and the RPD obtained for large sized instances

Data Instance Minimum Algorithm output (WTCT) RPD

n m solution MA MPA MAI MPAI MA MPA MAI MPAI

50 10 5470 6324 6358 5498 5504 15.60 16.23 0.51 0.62

50 20 8530 10150 10181 8580 8559 18.99 19.35 0.58 0.33

100 10 21547 25180 25003 21685 21562 16.86 16.04 0.64 0.07

100 20 31230 36985 36752 31238 31487 18.42 17.68 0.02 0.08

200 10 76722 98199 97367 77031 76748 27.99 26.91 0.40 0.03

200 20 113800 143810 144055 113874 113816 26.37 26.58 0.76 0.01

400 10 314556 482120 443390 317121 314601 53.27 40.96 0.81 0.01

400 20 467652 591020 584351 467679 467767 26.38 24.96 0.01 0.03

500 10 467158 781977 756400 468789 467187 67.39 61.92 0.35 0.01

500 20 713352 897997 880990 713792 713422 25.84 23.50 0.06 0.01

Data Instance	Minimum	Algorithm output (WTCT)	RPD
50	10	5470	6324	6358	5498	5504	15.60	16.23	0.51	0.62
50	20	8530	10150	10181	8580	8559	18.99	19.35	0.58	0.33
100	10	21547	25180	25003	21685	21562	16.86	16.04	0.64	0.07
100	20	31230	36985	36752	31238	31487	18.42	17.68	0.02	0.08
200	10	76722	98199	97367	77031	76748	27.99	26.91	0.40	0.03
200	20	113800	143810	144055	113874	113816	26.37	26.58	0.76	0.01
400	10	314556	482120	443390	317121	314601	53.27	40.96	0.81	0.01
400	20	467652	591020	584351	467679	467767	26.38	24.96	0.01	0.03
500	10	467158	781977	756400	468789	467187	67.39	61.92	0.35	0.01
500	20	713352	897997	880990	713792	713422	25.84	23.50	0.06	0.01

Again, the outputs are the mean values for 10 iterations of each algorithm. Here we didn’t have the real optimal solution, so; we computed RPD by $RPD = \frac{{Alg}_{sol} - {Min}_{sol}}{{Min}_{sol}} \times 100,$ where Alg_sol is the mean of WTCTs of a given algorithm on a given instance, and Min_sol is the best solution obtained by executing all algorithms on that instance (Table 4). For statistical analysis, since the normality test Anderson-Darling showed that the four sample data sets do not follow the normal distribution, we were persuaded to use nonparametric tests, although these kind of tests can only compare the media of sample data instead of their means. Here, we first applied Kruskal-Wallis test to determine if the media of these 4 data sets are equal. The output results indicated that the media were not equal. The median for MA, MPA, MAI and MPAI were 26.105, 24.23, 0.455 and 0.03 respectively; while the average ranks were 30.8, 30.2, 13.3 and 7.7. This showed that MAI and MPAI have a remarkable difference in performance when compared with MA and MPA. However, since the media of MA and MPA were close, we used Mann-Wittney test, which strongly confirmed the similar performance of them. Also, the Mann-Wittney test showed that the performance of MPAI is better than MAI by considering their media.

6 Conclusion and recommendations

A new mathematical model for FOSIPM is offered. Two metaheuristic methods are suggested to solve the problem: memetic algorithm (MA), and memetic algorithm in which permutating operation is replaced with mutation (MPA). Each algorithm is implemented in two situations: with and without imposing some predefined feasible points in the initial population. Statistical analysis indicated that for large-sized problems, MPA with imposed solutions worked better than the other algorithms.

For further research, it is proposed to increase the imposed feasible points, and apply them in more than one step of the suggested algorithms. Unfortunately, due to the limited background of this issue, no standard benchmark instances can be found yet. If so, examining new solving methods (for example, applying different EAs, or even other kinds of inexact algorithms) and comparing the results will be useful. Also, the problem FOSIPM can be redefined with more restrictions in any of the fields α, β or γ in its α|β|γ form. For example, considering the transportation times between stations, Limited capacity of buffers between stations, interruptable operations, and etc. Existence of two or more objective functions is a usual situation for which new algorithms should be developed. Finally, the multiprocessor open-shop problem (MPOS) is a generalization of FOSIPM whose mathematical model and solving methods are valuable challenges, even in its simplest form. However, new problems need their special mathematical models, computational complexity arguments and solving methods.

References

Ellu

and Ramasamy

, Literature review of open shop scheduling problems, Intelligent Information Management 7(01) (2015), 33–52.

Gupta

and Ong

Y.S.

, Memetic Computation: The Mainspring of Knowledge Transfer in a Data-Driven Optimization Era (Adoption, Learning and Optimization, 21), Springer International Publishing, 2018.

Naderi

, Fatemi Ghomi

S.M.T.

, Aminnayeri

and Zandieh

, Scheduling open shops with parallel machines to minimize total completion time, Journal of Computational and Applied Mathematics 235(5) (2011), 1275–1287.

Trail

C.D.

and Ventura

J.A.

, A multi-objective fixed product flexible open shop problem, In Proceedings of the 2012 Industrial and Systems Engineering Research Conference, edited by G. Lim and J.W. Herrmann, (2012), 1–6.

Bai

, Zhang

Z.H.

and Zhang

, Flexible open shop scheduling problem to minimize makespan, Computers & Operations Research 67 (2016), 207–215.

Montgomery

D.C.

, Design and analysis of experiments (9th edition), John Wiley & Sons, Inc, 2017.

Hurtado Villamizar

F.A.

, Espinosa Valderrama

D.A.

, SÃa̧nchez Duarte

J.D.

and Montoya Casas

C.E.

, Design of a solution technique based on an integral approach for the Flexible Open-Flow Shop scheduling problem, Technical report, INGENIERIA INDUSTRIAL, FACULTAD DE INGENIERIA, Pontificia Universidad Javeriana, Bogota, Colombia (2018).

Neri

and Cotta

, Memetic algorithms and memetic computing optimization: A literature review, Swarm and Evolutionary Computation 2 (2012), 1–14.

Neri

, Cotta

and Moscato

, (Eds), Handbook of Memetic algorithms. (Studies in Computational Intelligence, 379), Berlin, Heidelberg: Springer-Verlag, 2012.

10.

Woeginger

G.J.

, The Open Shop Scheduling Problem, In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), Leibniz International Proceedings in Informatics (LIPIcs), edited by R. Niedermeier and B. Vallée, Schloss Dagstuhl–Leibniz-Zentrumfuer Informatik, (2018), 4:1–4:12.

11.

Taguchi

, Introduction to quality engineering: designing quality into products and processes, John Wiley & Sons, Inc, 1986.

12.

Behnamian

, Dezfooli

S.M.

and Asgari

, Ascatter search algorithm with a novel solution representation for flexible open shop scheduling: a multi-objective optimization, The Journal of Supercomputing, Springer, (2021), 1–24.

13.

Achugbue

J.O.

and Chin

F.Y.

, Scheduling the open shop to minimize mean flow time, SIAM Journal on Computing 11(4) (1982), 709–720.

14.

Leung

J.Y.T.

, Handbook of scheduling: algorithms, models, and performance analysis, Chapman and Hall/CRC, 2004.

15.

Hassan

M.A.

, Kacem

, Martin

and Osman

I.M.

, Mathematical formulation for open shop scheduling problem, In 2017 4th International Conference on Control, Decision and Information Technologies (CoDIT) (2017), 0803–0808, IEEE.

16.

Matta

M.E.

, A genetic algorithm for the proportionate multiprocessor open shop, Computers & Operations Research 36 (2009), 2601–2618.

17.

Pinedo

M.L.

, Scheduling: Theory, Algorithms and Systems, (4th edition), New York, Dordrecht, Heidelberg, London: Springer, 2016.

18.

Ahmadian

M.M.

, Khatami

, Salehipour

and Cheng

T.C.E.

, Four decades of research on the open-shop scheduling problem to minimize the makespan, European Journal of Operational Research, Elsevier 295 (2021), 399–426.

19.

Rezapoor Mirsaleh

and Meybodi

M.R.

, Balancing exploration and exploitation in memetic algorithms: a learning automata approach, Computational Intelligence (Wiley Online Library) 34 (2018), 282–309.

20.

Kamatchi

and Saravanan

, Pareto-based Hybrid Multi-objective Firefly Algorithm for Flexible Open Shop Scheduling Problem, International Journal of Pure and Applied Mathematics 118 (2018), 3545–3558.

21.

Brucker

, Scheduling Algorithms (5th edition), Berlin, Heidelberg, New York: Springer, 2007.

22.

Sevastianov

S.V.

and Woeginger

G.J.

, Linear time approximation scheme for the multiprocessor open shop problem, Discrete Applied Mathematics 114 (2001), 273–288.

23.

Hungerford

T.W.

, Algebra, New York, Springer-Verlag, 1974.

24.

Marrouche

and Harmanani

H.M.

, Heuristic approaches for the open-shop scheduling problem, In Information Technology-New Generations (14th International Conference on Information Technology), edited by S. Latifi, Springer International Publishing (2018), 691–699.

25.

Huang

, Zhuang

, Cao

Q.L.

, Zhiyao

G.L.

and Qin

, A survey of intelligent algorithms for open shop scheduling problem, Procedia CIRP 83 (2019), 569–574.