Introducing an effective meta-heuristic algorithm: Cosmogony algorithm (CA)

Abstract

The purpose of this paper is to introduce a new meta-heuristic algorithm and apply this for solving a multi-objective flexible job-shop scheduling problem. The name of this algorithm is Cosmogony (CA). This algorithm has inspired by the ecosystem process of creatures and their environment. For a better understanding, we make an effort to apply the concepts of the meta-heuristic algorithms up to a possible extent. This algorithm identifies local optimal points during the self-search process of problem-solving. Initial creatures have been generated randomly in a certain number. This algorithm incorporates many features of the other algorithms in itself. So that to prove the ability and efficiency of CA, a flexible job-shop scheduling problem has surveyed. This problem is in a Non-resumable situation with maintenance activity constraints in a two-time fixed and non-fixed state. The algorithm performance is evaluated by numerical experiments. The result has shown the proposed approach is more efficient and appropriate than the other methods. It also has high power in the searching process in the feasible region of the multi-objective flexible job-shop scheduling problem and high converge power.

Keywords

Cosmogony algorithm meta-heuristic algorithms flexible job shop scheduling problem multi-objective optimization

1 Introduction

Meta-heuristic algorithms are problem-solving approaches. They apply to different optimizing problems after making some reasonable adjustments. Besides, these algorithms are heuristic methods being capable of searching in the feasible region to find good solutions. Meta-heuristic algorithms have some common characteristics and features as follows [9]:

Generally, the meta-heuristic algorithms have been inspired by some concepts relate to biology, zoological and physics behaviorism.

Some of the mechanisms are applied to escape the local optimum in this respect.

Often, the meta-heuristic algorithms are presented for solving both continuous and discrete problems.

Meta-heuristics are divided into two categories: deterministic algorithms, and stochastic algorithms which find a solution with error [48]. In comparison with exact algorithms, the meta-heuristic algorithms are implemented for some problems with the great feasible region. Also, they present convincing solutions in a reasonable time. In recent decades, meta-heuristic algorithms became well-known because of their efficiency and effectiveness in solving NP-hard problems. Talbi (2009) presented an approach for implementing the meta-heuristic algorithms, which are applicable in fields such as designing engineering, optimization, production, facility layout, scheduling, transportation and so on [45]. Until now, many meta-heuristic algorithms have been presented for the scheduling and optimization problems, such as ant colonies optimization (ACO) [8], artificial immune systems (AIS) [2], bee colony (BC) [41], genetic algorithms (GA) [20], great deluge algorithm (GDA) [10], guided local search (GLS) [47], genetic programming (GP) [26], greedy adaptive search procedure (GRASP) [12], iterated local search (ILS) [30], noisy method (NM) [6], particle swarm optimization (PSO) [24], simulated annealing (SA) [5], smoothing method (SM) [19], scatter search (SS) [17], threshold accepting (TA) [11], and tabu search (TS) [18]. Also, many researchers have introduced new and hybrid algorithms for NP-Hard problems. For example, Dianzi Liu and et al. (2018) introduced an efficient hybrid algorithm to solve mixed discrete-continuous optimization problems, and Yuanyang Zou (2019) introduced the whirlpool algorithm based on the physical phenomenon for solving optimization problems [29, 59]. Omar Abu Arqub and et al. (2016) present a new method for solving fuzzy differential equations based on the reproducing kernel theory under strongly generalized differentiability [1].

Moreover, several criteria used to classify such algorithms:

The single solution approach and the population apprach that is called evolutionary algorithms.

Algorithms inspired by nature and those not inspired by it.

Algorithms with and without memory.

The deterministic and probabilistic algorithms.

The greedy and iterative algorithms.

Job shop scheduling problem (JSP), which is among the hardest combinatorial optimization problems [44], is a branch of production scheduling. It is well known that this problem is NP-hard [16]. The classical JSP consists of scheduling a set of jobs on a set of machines, and each job has specified processing orderly. According to Brucker and Schlie (1990), the flexible job-shop scheduling problem (FJSS) is an extension of the classical Job-shop scheduling problem [4]. In this problem, operations allow processing on the multiple available machines with the same function. This is closer to the real manufacturing situation due to its additional needs for determining the assignment of operations on the machines. Besides, it is a more complex NP-hard problem, because it is an extension of the JSP that is an NP-hard problem [16]. Pachpor and et al. (2017) applied Petri nets towards improved utilization of machines in job shop manufacturing environments [35]. Khoukhi (2002) introduced a cybernetical approach called prototyped genetic search to job-shop scheduling problems [25].

The problem of scheduling jobs in FJSP could decompose into two sub-problems, which are a routing sub-problem and scheduling sub-problem. In the first one, each operation assigns to a machine out of a set of machines authorize for each job. In the second one, the sequencing of operations is determined to obtain a feasible schedule that minimizes a predefined objective [53]. Brucker and Schlie (1990) developed a polynomial algorithm for solving the flexible job-shop scheduling problem (FJSP) with two jobs [4]. Brandimarte (1993) was the first who applied the decomposition approach into the FJSP [3]. He solved the routing sub-problem using some existing dispatching rules and then focused on the scheduling subproblem solved by using a tabu search heuristic. Mastrolilli and Gambardella (1996) proposed some neighborhood functions for the FJSP, which could be used in meta-heuristic optimization techniques [31]. Also, Mati et al (2001) proposed a greedy heuristic to deal with simultaneous assigning and sequencing sub-problems of the flexible job-shop model [32]. The advantage of Mati’s heuristic was its ability to incorporate the assumption of identical machines.

Parsopoulos and Vrahatis (2002) conducted the first research on the particle swarm optimization method in multi-objective optimization problems [36]. Kacem et al. (2002) used a genetic algorithm for two multi-objective approaches using either the weighted summation of objectives or Pareto approaches [22, 23]. Scrich et al. (2004) developed two heuristics based on tabu search: a hierarchical procedure and a multiple start procedure in a FJSP [40]. Wu and Weng (2005) considered the problem with job earliness and tardiness objectives and proposed a multi-agent scheduling method [52]. Xia and Wu (2005) applied the combination of particle swarm optimization (PSO) and simulated annealing algorithm (SA) to solve the problem [53]. Nouri and et al(2018) also uused the PSO for solving FJSP [34]. Zhang and Gen (2005) proposed a multistage operation-based genetic algorithm to deal with the FJSP problem from a point of view of dynamic programming [58]. Jain et al. (2012) presented a genetic algorithm to solve a multi-objective FSJP problem that is minimizations of the make-span time and total machining time [21]. Phanden and et al. (2012) optimized the job shop scheduling problem using simulation and genetic algorithm [38]. Yazdani and et al (2019) a multi-objective dual-resource constrained FJSP and present a controlled elitism based version of NSGA-II and NRGA [56]. Li and et la. (2016) present a discrete harmony search for FJSP objective which were, the maximum of the completion time (Makespan) and the mean of earliness and tardiness [28]. Mun-Bo Shim and et al. (2002) Pareto-based Continuous Evolutionary Algorithms for Multi-objective Optimization problems having continuous search space introduced [42]. The heuristic methods that have been used in flexible job shop scheduling are a lot so Türkyilmaz and et al. (2020) have reviewed these methods in the last decade for solving the flexible job shop [46].

In this paper, we will introduce a new meta-heuristic algorithm called “Cosmogony Algorithm” (CA). This algorithm has been inspired by the ecosystem process of creatures and their environment. CA algorithm has generated the initial creatures randomly in a certain number. Then, creatures that are more compatible with their environment are identified as apt creatures. The apt creatures are considered as semi-active solutions in FJSP. The semi-active solutions are separated into two groups; elite creatures as elite solutions in the FJSP and superior creatures as superior solutions. Creatures are active during the process of the algorithm in a specified neighborhood structure in the several of sub-generations with local search as activated solutions in the FJSP. In addition, we explain its creation philosophy and its procedure, completely. To prove the efficiency of this algorithm, we apply several flexible job-shop problems (FJSPs) with considered constraints.

The remainder of this paper is organized as follows: In Section 2, the FJSP is described and formulated. In Section 3, CA’s philosophy and harmony, as well as the procedure of CA metaheuristic, are explained. In Section 4, CA algorithm parameters are introduced. In Section 5, we used some FJSP problems to show the advantage of the proposed algorithm and to compare those with the available proposed algorithms. In Section 6, we analyze the performance of the CA procedure in finding optimal solutions according to objective functions. Finally, the conclusion is discussed in Section 7.

2 Statement of a flexible job-shop scheduling problem with maintenance activities

In this section, FJSP is represented to explain CA. Also, the prposed algorithm is tested for the FJSP with maintenance activities. The FJSP surveyed with maintenance activities in this section is related to a board field of the deterministic scheduling with machine availability constraints.

In the FJSP, a set of n jobs is scheduled on a set of m machines in a way that each i job 1 ⩽ i ⩽ n involves a sequence of n_i operation (routing) such as o_i,1, o_i,2, ... ,o_i,n and a set of machines such as M ={ M₁, M₂, …, M_m }. There is a set of machines for each operation o_i,j which is able to process it. Also, o_i,j must be assigned to one of the machines. Therefore, each operation o_i,j (1 ⩽ i ⩽ n, 1 ⩽ j ⩽ n_i) has to be performed to complete one job. The o_i,j operation processing time is P_i,j,k on a M_k machine (M_kɛM). There is L_k number of maintenance activities in the framework of ${PM}_{u}^{k}$ (u ∈ L_k) which have to be processed on each machine M_k during the time horizontal planning based on the specific criteria of maintenance policy (e.g., periodical planning policy, the sequential policy of Wang (2002), and prevented the maintenance planning policy Ruiz et al. (2007) [39, 49]. In the case of a non-fixed availability constraint, the start time of each maintenance task is based on a pre-determined time window (time interval) $[{LB}_{u}^{k}, {UB}_{u}^{k}]$ (K = 1, 2, …, m ; u ∈ L_k) $({LB}_{u}^{k} < {UB}_{u}^{k})$ . Also, the duration of the maintenance task is pre-determined as ${PM}_{u}^{k}$ while in the case of fixed availability constraint, it is $({LB}_{u}^{k} = {UB}_{u}^{k})$ .

Remark 1: Resumable means that if a job cannot be finished before a maintenance activity, it can continue the processing once the maintenance activity is finished. Non-resumable means a job must be reprocessed fully after the maintenance if its processing is interrupted by the maintenance activity on a machine. Also, semi resumable means that if a job is not fully processed before the machine is stopped for maintenance, additional set-up time is necessary when the processing is resumed [50].

In a general multi-objective minimization problem, a function f (x) is minimized with ρ, (ρ > 1) decision variables, and Q objectives (Q > 1) are subjected to several equality or inequality constraints. More precise definitions of the terms about the multi-objective optimization can be found in Deb (2001) [7].

$\begin{matrix} Minimizef (x) \\ = (f_{1} (x), f_{2} (x), \dots, f_{q} (x), \dots, f_{Q} (x)) . \end{matrix}$ (1)

Where Ω is the feasible solution space and x ={ x₁, x₂, …, x_p } is the set of p-dimensional decision variables (continuous, discrete, and integer); i.e., a possible solution for the considered problem; f_q (x) is the q^th objective the function (1 < q < Q). In this study, we seek to minimize three objectives as follows:

f₁: Makespan of the jobs (C_M) or maximal completion time of machines.

f₂: Total workload of the machines, which represents the total workload time over all machines.

f₃ : Critical machine workload is the maximum working time spend at any machine. This objective prevents a solution from assigning excessive work on a single machine and keeps the balance of work distribution over the machines.

The considered assumptions are as follows [50]:

Each operation cannot be interrupted during its performance (non-preemptive condition);

Machines are independent of each other, and also jobs;

An operation cannot be performed by more than one machine. In other words, each machine can perform only one operation at the same time;

Setting up times of machines and moving times between operations are negligible;

There is an unlimited availability time in the progress of products in a way that a job can wait for a machine until it is available;

There are two cases related to maintenance resources. First, there are sufficient maintenance resources; hence, a number of machines can be repaired simultaneously. Next, the maintenance resources should be limited; in other words, only some specified numbers of machines can be repaired each time; therefore, the maintenance activity on a machine cannot overlap with another one. The resources used in this paper deal with the first one; the sufficient maintenance resources.

When a maintenance task is performing on a machine, no other operation can be processed on;

In the time planning horizon, there is at least one maintenance task on each machine which satisfies the earliest and latest time interval regarding the start time of the maintenance task $({LB}_{u}^{k} < {UB}_{u}^{k})$ .

3 Cosmogony Algorithm (CA) for FJSP

In this section, we elaborate on the new meta-heuristic CA algorithm. This algorithm has many advantages that distinguish it from all other meta-heuristic algorithms in the future.

3.1 Genesis of CA

The CA is originated from the philosophy of interaction between creatures and their environment. Creatures interact with each other to achieve their own species evolution. The process of evolution will be realized by a specific ontology structure in the creatures and their environment. Therefore, each creature has a specific ontology structure that their interaction with each other and their environment will lead to evolution. Generally, every creature has a pre-determined specific ontology structure called “guidance route” (Fig. 1). For example, honey bee having some special capabilities in the ontology structure, (only one of the fruits used by it produces honey); moreover, it is guided in such a way that it is able to build a suitable hive. Also, it can recognize and identify the flowers around it and produce honey by their nectars and pollens [43].

Fig. 1

The base of cosmogony and existence.

The interaction between creatures and their environment is called an ecosystem in the ecology science. In each ecosystem, there are several distinct species of creatures. Most obvious of the species in an ecosystem are called indicator species. The food relationship exists between the creatures and their environment within each ecosystem. The food relationship between the creatures is called a food chain. Several chains are connected or linked to each other to produce a food net. Since the environmental condition of habitats is not always uniform, each change in the environment can cause some changes in species. These changes, which are part of the process of species evolution, lead to the creatures’ growth. A set of these changes is called a sequence (Fig. 2).

Fig. 2

The scheme related to the evolutionary sequence of one species like tree.

Generally, there is a sequence for each species of the creatures. Also, the behavior of habitats and food net provides a metamorphosis in the creature’s species. The metamorphosis occurs at birth for the balance of creatures with their environment in the ecology. The creatures that can be quickly adapted to their habitats behavior are the more apt creature. Also, the apt creatures have more chances for survival and the evolution of their species. The apt creatures have better fitness function in the problem. Therefore, this process will lead to a cycle of evolution in nature, making the apt creatures have better conditions to grow and evolve in the natural cycle (Fig. 3). The procedure of the CA algorithm is illustrated in Fig. 4. The CA is a new population-based meta-heuristic approach. There are many kinds of creatures in an ecosystem that very creature has several species which are called onlooker species. Most obvious of the onlooker species in each kind of creatures are called indicator species. The performance process of the CA can describe as follows. There are many indicator species in a habitat of ecology science. The indicator species have an effective role in the evolution process of the creatures in the ecosystem. The process of evolution achieves by the interaction of creatures with each other and their environment. Creature’s interaction with each other creates a specific sequence (Fig. 2). Each step of the sequencing process is implemented by the onlooker species of each creature. The best onlooker species replaces with the former species indicator of each sequencing process step. Once the sequencing process was finished for each species of creatures, the environmental conditions and creature’s habitat create a metamorphosis in the current evolved species for better compatibility with its habitat. The cycle of CA stops when creatures in the ecosystem according to the interaction with each other and food network in their own habitat reach the best adaptability with each other.

Fig. 3

The evolutionary cycle of CA.

Fig. 4

The procedure of the CA algorithm.

3.2 The harmony with a meta-heuristic algorithm

A meta-heuristic algorithm usually contains four following traits:

There is a random process in the feasible region.

It should be converged in the duration of time or in the last generations by the rule of most competent survival.

It should be able to escape from the local optimum trap.

It should have a suitable commix in order to search in the feasible region.

An issue about this algorithm, that is given less attention, is that moving the object toward should not only be randomly but should be to some extent intelligent (Fig. 1). Moreover, although most of the meta-heuristic algorithms try to escape from the local optimum trap, a strong meta-heuristic algorithm should be able to recognize and identify the depth of local optimum during the algorithm procedure for passing it easily; the TS algorithm has this characteristic naturally. Hence, the CA has two following characteristics to achieve the object as well as the four characteristics mentioned.

The movement toward the object is guided; which implies that the movement is not only a random but to some extent intelligent (Figs. 1 and 2).

It has some ability to recognize and identify the depth of local optimum and can pass it easily by implementing TS algorithm in the sequencing process.

4 CA for FJSP

4.1 Solution representation

Showing the structure of a solution is important when using the algorithm. The algorithm will proceed based on a presented structure. An appropriate structure of the solution leads to the correct guidance of problem-solving. Therefore, a solution of FJSP problem needs two sequences. First, assignment of operations to machines and the other processing sequence of operations on the machines. According to Wang et al (2010), we integrated the operation sequence vector and machine assignment vector as the representation of a feasible solution [51]. The first vector (ν₁) provides an assignment of operations to machines, and the other one (ν₂) provides a processing sequence of operations on the machines.

To explain the representation, we provide an example by considering a problem with four jobs and four machines shown in Table 1. Fig. 5 illustrates the representation of a feasible solution. For the operation sequence vector, the number of elements equals the total number of operations. The operations of each job are denoted by the corresponding job number, and the k^th occurrence of a job number refers to the k^th operation in the sequence of this job. For the machine assignment vector, each number represents the assigned machine for each operation. The Gantt chart of this solution is shown in Fig. 6.

Table 1
Problem FJSP 4×4/10

Job Operation M1 M2 M3 M4

1 O_1,1 4 7 6 5

O_1,2 2 6 – 5

2 O_2,1 4 5 7 –

O_2,2 5 – 6 3

O_2,3 – 5 4 7

3 O_3,1 5 3 – 6

O_3,2 – – 4 –

4 O_4,1 2 4 5 –

O_4,2 – 4 2 –

O_4,3 5 4 6 3

Job	Operation	M1	M2	M3	M4
1	O_1,1	4	7	6	5
	O_1,2	2	6	–	5
2	O_2,1	4	5	7	–
	O_2,2	5	–	6	3
	O_2,3	–	5	4	7
3	O_3,1	5	3	–	6
	O_3,2	–	–	4	–
4	O_4,1	2	4	5	–
	O_4,2	–	4	2	–
	O_4,3	5	4	6	3

Fig. 5

The structure of solution for FJSP with 4×4/10.

Fig. 6

Gant chart of the solution shown in Fig. 5.

4.2 Initial population

To guarantee an initial population with a certain appropriate quality, some different strategies are utilized in a hybrid way to generate the initial solutions as the indicator species. The initial process of the algorithm involves an operation sequence phase and machine assignment phase. Generally, a random production of operation sequence vector is applied for the processing of jobs. Also, in order to guarantee machine assignment phase in the initial population, there are three rules:(1) random rule randomly selects a machine among a set of candidate machines for each operation and replaces it at the current position in the vector of machine assignment (v₁);(2) local minimum processing time rule assigns the minimum workload among the set of machines waiting for processing the same job [27]; and (3) global minimum processing time rule considers the global workload among all machines [37].

In our algorithm, we applied the first rule to generate an initial population of machine assignment, because it provides a more varied population in a feasible space of problem with no restriction in the feasible space. Therefore, it can cause a great variation in the solutions (Fig. 5).

4.3 Selection

The evolution of creature’s species appears to be on the basis of favorable changes in acceptance and the rejection of undesired changes. Therefore, there is always a struggle for survival. Creatures that have an advantage over other creatures will survive more likely. After generating the initial population, the apt creatures are identified for more evolution from the available population. First, the population is sorted based on their fitness values. Then, a certain percentage (P_apt) of the sorted population is considered as apt creatures. The apt creatures have better conditions for survival in ecology. In other words, they can quickly adapt to their environment in order to save their species. In our study, the apt creatures were separated into two groups: elite species with a certain percentage of P_e and superior species with a certain percentage of P_s, P_e + P_s = 1, P_e < P_s.

4.4 Fitness function

The fitness function is used as the performance evaluation of indicator species. Fitness is usually represented with a function: S → R⁺; where S is the set of candidate schedules and R⁺; is the set of positive real values. In our study, we wish to minimize three objectives. To prevent these three considered objectives conflicting with each other, it is required a small makespan (f₁) for a small maximal workload (f₂) a small total workload (f₃).

For each solution, these objectives can be calculated. For example, consider Fig. 6 that is the Gant chart of Fig. 5. Makespan is the total length of schedule, and as it has shown in Fig. 6 it’s equal to 14. The maximal workload is equal to the maximal length between the machines’ operation time. The workload of machines M1 to M4 is 8,7,10 and 8 sequentially, so the maximal workload is 10. The total workload is equal to the sum of the time of the operating machine, and fo this solution is 33.

The fitness of a solution is calculated by synthesizing three objectives into a weighted sum. We have to scale the objective values on the three criteria before they are summed since they are at different scales [15].

Therefore, the fitness of l^th a solution is calculated using Equation 2.

$\begin{matrix} F_{T} (l) = & α_{1} \times \frac{f_{1} (l) - f_{1_{\min}} + ɛ}{f_{1_{\max}} - f_{1_{\min}} + ɛ} + α_{2} \\ \times \frac{f_{2} (l) - f_{2_{\min}} + ɛ}{f_{2_{\max}} - f_{2_{\min}} + ɛ} + α_{3} \frac{f_{3} (l) - f_{3_{\min}} + ɛ}{f_{3_{\max}} - f_{3_{\min}} + ɛ} . \end{matrix}$ (2) where, α₁, α₂, α₃ > 0 and α₁ + α₂ + α₃ = 1; also, ɛ is a negligible value greater than zero (ɛ > 0). For a conventional explanation of the fitness function (Equations 2), the following parameters are considered:

l : Index of population size. l = 1, 2, . . . , p.

f (l) _i: The value of i^th an objective function of l^th the candidate solution i = 1, 2, . . . , q .

f (i) _max: The maximum value of i^th objective in the current population

f (i) _min: The minimum value of i^th objective in the current population

4.5 Mutation for onlooker species

To generate a certain number of onlooker species for every indicator species, we applied a mutation operator. The number of onlooker species is different based on the species kind. The elite species has more onlooker species than superior species, (Nep > Nsp). One onlooker species is formed with a minor change in the indicator species. In FJSP, minor changes may appear in the operation sequence vector (v₂) or machine assignment vector (v₁). The following mutation procedure is used in the CA algorithm as the formation of onlooker species:

Step 1: Randomly generate two integers (i, j i ≠ j) from 1 to z, where z is the total number of operations.

Step 2: Select (i, j) positions from the operation sequence vector v₂ or machine assignment vector v₁.

Step 3: For selected positions, replace the contents of the i^th and j^th positions with each other from v₁ or v₂ (no change happens if the i^th and j^th positions of the operation sequence vector (v₂) have the same content).

Remark 2 : Some operations are only achievable on a part of the available machines set, where machine assignment is impossible. According to our approach, we need an infinite value such as 9999.

As shown in Fig. 5, to describe the formation of an onlooker species for indicator species, we presented an instance with minor changes in the operation sequence vector (ν₂) as follow: Suppose i and j are positions 3 and 6 from ν₂, respectively. Also, the contents of positions 3 and 6 are numbers 3 and 4, respectively. First, we create the operation sequence vector (ν₂) as Fig. 7-a. Then, we assigned machines in accordance with the appearance in the primary state from left to right as Fig. 7-b.

Fig. 7

The formation of an onlooker species for indicator species in Fig. 5.

4.6 Sequence for indicator species

To evolve an indicator species, we applied the sequencing process. For this purpose, first, a certain number of onlooker species (Nep or Nsp) was created for indicator species. Then, the best onlooker species was replaced with current indicator species as P_best. The best onlooker species is measured by the fitness function in the FJSP problem. In our study, the proposed sequence is guided by a local search to improve the fitness value; therefore, the TS algorithm is considered as a sequence process in order to evolution any indicator species. The applied sequence process is shown in Fig. 8.

Fig. 8

The sequencing process of CA Algorithm according to fig.

Applying sequence procedure causes a neighborhood structure that is able to detect local optimal solution in the process of implementing the CA algorithm. Fig. 9 shows a view of the applied neighborhood structure in the sequencing process. The proposed sequencing process is applied to all apt solutions from the current population. Therefore, the introduced sequencing process is used in Step 4 of Fig. 4

Fig. 9

The scheme from the progress of the sequencing process.

4.7 Metamorphosis

In ecology, the behavior of habitats and food net provides a metamorphosis in the creature’s species. Once an indicator species evolve in the sequencing process by a neighborhood structure as a local search, the metamorphosis occurs at birth for the balance of creatures with their environment in the ecology. In our approach, we applied the crossover operator for the metamorphosis of creatures in an ecosystem. Different crossover operators are proposed to solve the FJSP optimization problem.

In our study, the uniform crossover operator was used to implement metamorphosis in creatures. Also, the uniform crossover operator was applied in operation sequence vector (ν₂) whereas contents of (ν₁) are transmitted together with the operation sequence vector (ν₂) as follow: Two solutions (or complementary species) are selected from the current population as parents according to the selection process. Suppose P₁ and P₂ are selected as the parents of the available population (P₁ ≠ P₂). Then, a binary string is randomly generated by 0 and 1 with the same length as a mask (Fig. 10). Next, the offspring inherits the element of P₁ at positions with bit 0 while inherits the element of P₂ at positions with bit 1. As shown in Fig. 11-a, when the offspring inherited the element from P₁, the first element of the similar will be ignored by the other parent. The formation procedures of offspring are presented in Fig. 11 within four steps (a, b, c, and d) with respect to the produced mask.

Fig. 10

Instances from parents and a mask.

Fig. 11

Illustrate the procedure of uniform crossover.

Remark3: Metamorphosis process is based on the operation sequence vector in the FJSP whereas the elements of the machine assignment vector are transmitted together. The proposed metamorphosis process is applied in step 6 of Fig. 4.

4.8 The framework of CA

The CA algorithm possesses a high search efficiency by combining local search and global search. TS as a local search algorithm employs the certain probability to avoid entrapment in a local optimum. The framework of the proposed CA is illustrated in Fig. 12. Briefly, our algorithm can be summarized through the pseudo-code presented in Fig. 13.

Fig. 12

The framework of the CA algorithm.

Fig. 13

Cosmogony algorithm with pseudo-code.

Therefore, each solution of FJSP is controlled by TS as a local search in the population. The level of control for each solution depends on the search efficiency of TS.

5 Numerical results

In order to test the efficiency of the proposed CA, we took some experimental simulations. Flexible job-shop scheduling problem (represented by n × m/N operations) was selected based on practical data which all extracted from the work conducted by Xia & Wu (2005) and Kacem et al. (2002) [22 , 53].

The proposed CA algorithm is coded using a VBA programming language and runs on a PC with an Intel (R) core(TM)i3 4005u CPU @1.7 GH and 4 GB of RAM. The processing time is calculated for solving FSJP (problem 8×8/27 operations with maintenance activities) it was a minute and 19.36 seconds (01:19.36). The adopted parameters of the CA are listed in Table 2. In this paper, the considered FSJP with maintenance activities was extended from these two original FJSP problems by considering one PM activity on each machine in the planning horizon. The results are obtained by an objective function (Eq 3):

Table 2
Parameters of the CA in the FJSO problem

Parameters Value Parameters Value

Population size 400 f₁ 6

P _apt 30% f₂ 3

P _e 20% Generation 80

P _s 80% Number

Nep 20

Nsp 20

Parameters	Value	Parameters	Value
Population size	400	f₁	6
P _apt	30%	f₂	3
P _e	20%	Generation	80
P _s	80%	Number
Nep	20
Nsp	20

$\begin{matrix} F (l) = & α_{1} \times f_{1} + α_{2} \times f_{2} + α_{3} \times f_{3}, \\ where α_{1} + α_{2} + α_{3} = 1 \end{matrix}$ (3)

5.1 FJSP problem 8×8/27

5.1.1 Problem 8×8/27 operations without maintenance activities

This section presents an instance of the FJSP problem with partial flexibility. In this FJSP, there are 8 jobs with 27 operations to be performed on 8 machines. For further information upon this FJSP problem, see Xia and Wu (2005) [53].

The optimization can process a large number of operations on some machines, where machine assignment is impossible. As mentioned earlier, according to our approach, an infinite value such as 9999 is required. Therefore, the machines with infinite processing time (such as 9999) cannot be selected for operations in process optimization. Accordingly, the partial flexibility problem can be converted to a total flexibility problem. We can confirm the validity of our approach by comparing other methods. Assume f₁(l), f₂(l), and f₃(l) are the makespan, total workload, and critical workload of the l^th solution, respectively.

The computational results by the proposed CA algorithm are compared with those from other methods such as AL+CGA [22], PSO+SA [53], GA+VND [14], PSO+TS [57], SACO [54], MSE [55], and MOPSO+LS [33] presented in Table 3. Figs. 14, 15, and 16 show some computational results in a Gantt chart.

Table 3
Comparison of CA algorithm with other methods

Size Method AL+CGA PSO+SA GA+VND PSO+TS SACO SME MOPSO+LS CA

(n×m) object 1 2 1 2 1 1 2 1 2 1 2 3 4 1 2 3 4 5 1 2 3 4

8×8/27 makespan f₁ 15 16 15 16 14 15 14 15 14 15 17 14 16 15 16 14 16 17 15 16 14 16

Total work load f₂ 79 75 75 73 77 75 77 75 77 75 73 77 77 75 73 77 78 77 75 73 77 78

Max work load f₃ – – 12 13 12 12 12 12 12 12 13 12 11 12 13 12 11 11 12 13 12 11

10×10/30 makespan f₁ 7 – 7 – 7 7 – 7 8 8 7 8 – 8 7 8 7 – 8 7 8 –

Total work load f₂ 45 – 44 – 43 43 – 42 42 41 42 42 – 41 42 42 43 – 41 42 42 –

Max work load f₃ 5 – 6 – 5 6 – 5 7 6 5 – 7 6 5 5 – 7 6 5 –

Size	Method		AL+CGA	PSO+SA	GA+VND	PSO+TS	SACO	SME	MOPSO+LS	CA
(n×m)	object		1	2	1	2	1	1	2	1	2	1	2	3	4	1	2	3	4	5	1	2	3	4
8×8/27	makespan	f₁	15	16	15	16	14	15	14	15	14	15	17	14	16	15	16	14	16	17	15	16	14	16
	Total work load	f₂	79	75	75	73	77	75	77	75	77	75	73	77	77	75	73	77	78	77	75	73	77	78
	Max work load	f₃	–	–	12	13	12	12	12	12	12	12	13	12	11	12	13	12	11	11	12	13	12	11
10×10/30	makespan	f₁	7	–	7	–	7	7	–	7	8	8	7	8	–	8	7	8	7	–	8	7	8	–
	Total work load	f₂	45	–	44	–	43	43	–	42	42	41	42	42	–	41	42	42	43	–	41	42	42	–
	Max work load	f₃	5	–	6	–	5	6	–		5	7	6	5	–	7	6	5	5	–	7	6	5	–

Fig. 14

Optimization Solution 3 of problem 8×8/27, f1 = 14, f2 = 77, f3 = 12.

Fig. 15

Optimization Solution 1 of problem 8×8/27, f1 = 15, f2 = 75, f3 = 12.

Fig. 16

Optimization Solution 2 of problem 8×8/27, f1 = 16, f2 = 73, f3 = 13.

5.1.2 Problem 8×8/27 operations with maintenance activities

5.1.2.1. Constraint of non-fixed availability and sufficient maintenance resources. In this research, the considered FSJP with maintenance task is extended from this FJSP problem 8×8/27 by considering exactly one PM task on each machine during the scheduling horizon. The FJSP with maintenance task has the constraint of non-fixed availability and sufficient maintenance resources. The time window of starting time and duration of maintenance tasks in the FJSP (8×8/27) are shown in Table 4 [50]. As shown in this table, there is a maintenance task that is needed to be processed on machine 1. The earliest and last starting times are at one-time and six-time units, respectively. Besides, the duration of the maintenance task is four-time units. The optimal solutions of the FJSP-NFA problem and those reported in the work of Gao et al. (2006) and Wang (2010) are shown in Table 5 [13, 50]. Gao et al. (2006) employed a hybrid GA with nine pre-determined parameters [13]. In addition, Wang and Yu (2010) applied a filtered beam search [50]. None of the values obtained from three different objectives by the proposed methods was acceptable as non-dominate solutions. Gantt charts of the results are shown in Figs. 17 and 18.

Table 4
The PM task in the problem 8×8/27 operations

${PM}_{1}^{1}$ ${PM}_{2}^{1}$ ${PM}_{3}^{1}$ ${PM}_{4}^{1}$ ${PM}_{5}^{1}$ ${PM}_{6}^{1}$ ${PM}_{7}^{1}$ ${PM}_{8}^{1}$

Time window ${LB}_{1}^{1}$ 1 3 5 6 0 3 1 3

${UB}_{1}^{1}$ 6 6 10 14 7 11 11 9

Duration 4 3 5 3 3 5 3 4

		${PM}_{1}^{1}$	${PM}_{2}^{1}$	${PM}_{3}^{1}$	${PM}_{4}^{1}$	${PM}_{5}^{1}$	${PM}_{6}^{1}$	${PM}_{7}^{1}$	${PM}_{8}^{1}$
Time window	${LB}_{1}^{1}$	1	3	5	6	0	3	1	3
	${UB}_{1}^{1}$	6	6	10	14	7	11	11	9
Duration		4	3	5	3	3	5	3	4

Table 5

Comparison of CA algorithm with other method in the maintenance task with non-fixed starting time

Size (n×m)	Method object	Gao et al (2006)	Wang(2010)	CA approach
		1	1	1	2
8×8/27	Makespan	f₁	17	18	7	18
	Total work load	f₂	105	103	105	103
	Max work load	f₃	15	16	15	16
10×10/30	Makespan	f₁	8	9	9	–
	Total work load	f₂	61	60	60	–
	Max work load	f₃	7	8	8	–

Fig. 17

Optimization Solution 1 of problem 8×8/27 with maintenance task: f1 = 17, f2 = 105, f3 = 15.

Fig. 18

Optimization Solution 2 of problem 8×8/27 with maintenance task: f1 = 18, f2 = 103, f3 = 16.

5.1.2.2. Fixed availability constraint and sufficient maintenance resources In the case of fixed availability constraint, the earliest start time of the maintenance task is equal to its last start time, as the duration of the time window is zero. Suppose the maintenance task is set to start at the earliest possible time as a case (a) and at the last possible time as a case (b) (Table 6). In case (a), all maintenance tasks are shifted left and are processed at the earliest possible time. Also, in case (b) all maintenance tasks are shifted right and processed at the last possible time. The scheduling results for case (a) are shown in the Figs. 19 and 20. Also, for case (b) the scheduling results are shown in the Figs. 21 and 22. The results for these cases are compared with those of Wang and Yu (2010) in Table 7. The table shows that the results of the CA algorithm are more satisfactory than those of FBS method proposed by Wang and Yu (2010) [50]. The solution of FBS approach is dominated by the results of the CA approach in case (a) and (b). Also, the results of both cases are worse compared than those in Table 5 in the state of a non-fixed constraint.

Fig. 19

Optimization Solution 1 of problem 8×8/27 with a fixed starting time of maintenance tasks in case (a): f1 = 19, f2 = 108, f3 = 18.

Fig. 20

Optimization Solution 2 of problem 8×8/27 with a fixed starting time of maintenance tasks in case (a): f1 = 20, f2 = 103, f3 = 16.

Fig. 21

Optimization Solution 1 of problem 8×8/27 with a fixed starting time of maintenance tasks in case (b): f1 = 21, f2 = 103, f3 = 16.

Fig. 22

Optimization Solution 2 of problem 8×8/27 with a fixed starting time of maintenance tasks in case (b): f1 = 21, f2 = 105, f3 = 15.

5.2 FJSP problem 10×10/3

5.2.1 Problem 10×10/3 operations without maintenance activities

In this case, 10 jobs with 30 operations are performed on 10 machines (Xia and Wu, 2005). The computational results of the proposed CA algorithm are shown in Table 3. As the results show, compared with other methods, CA indicates higher efficiency. Figs. 23 and 24 show some sample optimum solutions in Gantt charts.

Fig. 23

Optimization Solution 1 of problem 10×10/30 f1 = 8, f2 = 41, f3 = 7.

Fig. 24

Optimization Solution 2 of problem 10×10/30 f1 = 7, f2 = 42, f3 = 6.

5.2.2 Problem 10×10/3 operations with maintenance activities

5.2.2.1. Non-fixed availability constraint and sufficient maintenance resources. In our studies, an FJSP-NFA problem was extended from FJSP problem in subsection 5.2.1 by considering only one PM task on each machine. The time window of starting time and duration of maintenance tasks are shown in Table 8 [50]. The Gantt chart of the optimal solution is shown in Fig. 25. Also, the optimal solution of the FJSP-NFA problem is compared in Table 5 with that of another method. The results show the high performance of our algorithm.

Table 6
The fixed starting time of PM task in the problem8×8/27 operation

${PM}_{1}^{1}$ ${PM}_{2}^{1}$ ${PM}_{3}^{1}$ ${PM}_{4}^{1}$ ${PM}_{5}^{1}$ ${PM}_{6}^{1}$ ${PM}_{7}^{1}$ ${PM}_{8}^{1}$

(a) Fixed as the earliest starting time of the time window:

Staring time ${LB}_{1}^{1} = {UB}_{1}^{1}$ 1 3 5 6 0 3 1 3

duration 4 3 5 3 3 5 3 4

(a) Fixed as the latest starting time of the time window:

Staring time ${LB}_{1}^{1} = {UB}_{1}^{1}$ 6 6 10 14 7 11 11 9

duration 4 3 5 3 3 5 3 4

	${PM}_{1}^{1}$	${PM}_{2}^{1}$	${PM}_{3}^{1}$	${PM}_{4}^{1}$	${PM}_{5}^{1}$	${PM}_{6}^{1}$	${PM}_{7}^{1}$	${PM}_{8}^{1}$
(a) Fixed as the earliest starting time of the time window:
Staring time ${LB}_{1}^{1} = {UB}_{1}^{1}$	1	3	5	6	0	3	1	3
duration	4	3	5	3	3	5	3	4
(a) Fixed as the latest starting time of the time window:
Staring time ${LB}_{1}^{1} = {UB}_{1}^{1}$	6	6	10	14	7	11	11	9
duration	4	3	5	3	3	5	3	4

Table 7

The FJSP with maintenance tasks in the fixed starting time

Size (n×m)		Method object		Wang, yu in 2010	CA approach
				1	1	2
8×8/27	Case (a)	Makespan	(f₁)	22	19	20
		Total work load	(f₂)	104	108	103
		Max work load	(f₃)	19	18	16
	Case (b)	Makespan	(f₁)	21	21	21
		Total work load	(f₂)	106	103	105
		Max work load	(f₃)	17	16	15
10×10/30	Case (a)	Makespan	(f₁)	9	9	9
		Total work load	(f₂)	62	61	60
		Max work load	(f₃)	8	7	8
	Case (b)	Makespan	(f₁)	12	9	10
		Total work load	(f₂)	65	61	60
		Max work load	(f₃)	8	8	8

Table 8

The PM task in the problem 10×10/30

	${PM}_{1}^{1}$	${PM}_{2}^{1}$	${PM}_{3}^{1}$	${PM}_{4}^{1}$	${PM}_{5}^{1}$	${PM}_{6}^{1}$	${PM}_{7}^{1}$	${PM}_{8}^{1}$	${PM}_{9}^{1}$	${PM}_{10}^{1}$
Time window	${UB}_{1}^{1}$	0	1	0	0	2	0	0	0	0	0
	${UB}_{1}^{1}$	2	6	5	3	6	4	3	4	3	3
Duration	2	1	1	2	1	2	2	3	2	3

Fig. 25

Optimization Solution 1 of problem 10×10/30 with maintenance activities with non-fixed time: f1 = 9, f2 = 60, f3 = 8.

5.2.2.2. Fixed availability constraint and sufficient maintenance resources. As shown in Table 9, suppose the maintenance task is set to start at the earliest possible time as a case (a) and at the last possible time as a case (b).[50]The optimal solutions for case (a) are shown in Figs. 26 and 27 while for case (b) the optimal solutions are presented in Figs. 28 and 29. Comparing the results of the CA algorithm with those of Wang and Yu (2010) in Table 7 indicate the higher performance of the CA algorithm [50]. Unlike case (b), in case (a) the solutions are not outperformed with those in Table 5. Thus, it can be stated that under the same set of algorithm parameters, the performance improvement of scheduling results benefits from optimizing maintenance and scheduling jointly.

Table 9

The fixed starting time PM task in the problem 10×10/30

	${PM}_{1}^{1}$	${PM}_{2}^{1}$	${PM}_{3}^{1}$	${PM}_{4}^{1}$	${PM}_{5}^{1}$	${PM}_{6}^{1}$	${PM}_{7}^{1}$	${PM}_{8}^{1}$	${PM}_{9}^{1}$	${PM}_{10}^{1}$
(a) Fixed as the earliest starting time of the time window:
Staring time ${LB}_{1}^{1} = {UB}_{1}^{1}$	0	1	0	0	2	0	0	0	0	0
duration	2	1	1	2	1	2	2	3	2	3
(a) Fixed as the latest starting time of the time window:
Staring time ${LB}_{1}^{1} = {UB}_{1}^{1}$	2	6	5	3	6	4	3	4	3	3
duration	2	1	1	2	1	2	2	3	2	3

Fig. 26

Optimization Solution 1 of problem 10×10/30 with maintenance activities with non-fixed time in case (a): f1 = 9, f2 = 61, f3 = 7.

Fig. 27

Optimization Solution 2 of problem 10×10/30 with maintenance activities with non-fixed time in case (a): f1 = 9, f2 = 60, f3 = 8.

Fig. 28

Optimization Solution 1 of problem 10×10/30 with maintenance activities with fixed starting time in case (b): f1 = 9, f2 = 61, f3 = 8.

Fig. 29

Optimization Solution 2 of problem 10×10/30 with maintenance activities fixed starting time in case (b): f1 = 10, f2 = 60, f3 = 8.

6 Analysis

6.1 Convergence

This section analyzes the framework of convergence for our CA in solving the FJSP problem. As mentioned earlier, we wish to minimize three objectives. Therefore, the algorithm should converge to the optimal solution over successive generations. The convergence is carried out on an available population. Chart 1 depicts the convergence curves of the average makespan, the best makespan and the worst makespan of the population when using CA to solve an 10 × 10/30 instance in a typical run mentioned in subsection (5.2.2.1). Also, Chart 2 and Chart 3 depict the convergence curves for total workload machines and critical machine workload of the population when using a CA like the one shown in Chart 1. The curves of standard deviation are depicted in Chart 4 for each of the three objective functions in each generation. In this chart, dispersion values are found to decrease over generations in the CA algorithm. This reduction process of dispersion is not uniform in the CA algorithm for all three objective functions; suggesting the validity of our proposed algorithm.

6.2 Correlation

This subsection presents the correlations (ρ) between the objective functions in different generations of the algorithm. The convergence of evolutionary population is not affected by the correlation between the objective functions. The lower correlation between the objective functions leads to a good dispersion infeasible space of the problem. The correlation coefficient is used to determine the relationship between the two properties.

For example, one can examine the relationship between a location’s average temperature as a set (X) and the use of air conditioners as a set (Y). The correlation coefficient is calculated using Equation 3 (ρ ⩽ 1), where $\bar{x}$ and $\bar{y}$ are the sample mean of the set (X) and set (Y), respectively. If ρ is close to 1, it has a strong and direct correlation while being close to -1 indicates its strong and inverse correlation. Moreover, ρ= 0 indicates the presence of no correlation between these two variables. In this problem, f₁, f₂, and f₃ are the makespan, total workload machines, and critical Workload respectively. Therefore, the correlation coefficient ρ_i,j is calculated among the objective functions in each generation of the CA algorithm. Chart 5 presents the correlation curve between the makespan (f₁) and total workload machines (f₂) in each generation of the CA algorithm. Furthermore, Chart 5, 6 and 7 depict the correlation curve between f₁ and f_2, f₁ and f₃ and f₂ and f₃ respectively.

Chart 1

Convergence curves in solving 10×10/30 Non-fixed problem by CA.

Chart 2

Convergence curves in solving 10×10/30 Non-fixed problem for total workload machines by CA.

Chart 3

Convergence curves in solving 10×10/30 in solving Non-fixed problem for critical workload by CA.

Chart 4

Dispersion rate curves in solving 10×10/30 Non-fixed problem by CA.

Chart 5

Correlation curve in solving 10×10/30 non-fixed problem between makespan, the total workload.

Chart 6

Correlation curve in solving 10×10/30 non-fixed problem between makespan, critical workload.

Chart 7

Correlation curve in solving 10×10/30 non-fixed problem between total workload, critical workload.

In the initial generations, correlation coefficients are reduced between the objective functions, because the FJSP problem is an NP-hard problem, and its feasible region is very large. In the middle generations, they are correlated to each other directly or inversely, because there is an appropriate fitness function for the selected solutions. In the final generations, the correlation is very low because there is a convergence in the evolutionary population.

$\begin{matrix} ρ = & \sum_{i = 1}^{n} (x_{i} - \bar{x}) (y_{i} - \bar{y}) / \sqrt{\sum_{i = 1}^{n} (x_{i} - \bar{x})} \\ \times \sum_{i = 1}^{n} (y_{i} - \bar{y}) \end{matrix}$ (4)

7 Conclusion

The new Cosmogony Algorithm (CA) presented in this work indicates high compatibility and efficiency regarding the search process in the problem feasible region, and it also has a high converge power. As elaborated in previous sections, the CA algorithm is inspired by the ecosystem process existing in ecology. To prove the efficiency of this new algorithm, multi-objective FJSP problem with activity maintenance constraint was surveyed in two fixed and non-fixed time states in the non-resumable situation implemented by other researchers.

Based on the simulation tests and comparisons with several existing algorithms, it was found that the proposed CA algorithm is capable of solving the FJSP effectively and robustly. Due to the compatibility explained in Section 2, this algorithm will bring about a change in finding optimal or rather optimal solutions for the problem in future, because CA algorithm has many features of the other algorithms such as SA, TS, GA, and BA as well as elitism algorithms in its core. Moreover, this algorithm simply identifies the local optimum point during the self-search process and simply passes through it.

The future work is to study the CA algorithm for solving the multi-objective optimization problems with due date constraint and Pareto approach.

References

Arqub

O.A.

, et al., Numerical solutions of fuzzy differential equations using reproducing kernel Hilbert space method, Soft Computing 20(8) (2016), 3283–3302.

Bersini

and Varela

F.J.

, Hints for adaptive problem solving gleaned from immune networks, in International Conference on Parallel Problem Solving from Nature (1990), Springer.

Brandimarte

, Routing and scheduling in a flexible job shop by tabu search, Annals of Operations Research 41(3) (1993), 157–183.

Brucker

and Schlie

, Job-shop scheduling with multi-purpose machines, Computing 45(4) (1990), 369–375.

Černý

, Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm, Journal of Optimization Theory and Applications 45(1) (1985), 41–51.

Charon

and Hudry

, The noising method: a new method for combinatorial optimization, Operations Research Letters 14(3) (1993), 133–137.

Deb

, Multi-objective optimization using evolutionary algorithms, 16 (2001), John Wiley & Sons.

Dorigo

, Optimization, learning and natural algorithms [Ph. D. thesis]. Politecnico di Milano, Italy, (1992).

Dréo

, et al., Metaheuristics for hard optimization: methods and case studies. 2006 Springer Science & Business Media.

10.

Dueck

, New optimization heuristics: The great deluge algorithm and the record-to-record travel, Journal of Computational Physics 104(1) (1993), 86–92.

11.

Dueck

and Scheuer

, Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing, Journal of Computational Physics 90(1) (1990), 161–175.

12.

Feo

T.A.

and Resende

M.G.

, A probabilistic heuristic for a computationally difficult set covering problem, Operations Research Letters 8(2) (1989), 67–71.

13.

Gao

, Gen

and Sun

, Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm, Journal of Intelligent Manufacturing 17(4) (2006), 493–507.

14.

Gao

, Sun

and Gen

, A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems, Computers & Operations Research 35(9) (2008), 2892–2907.

15.

Gao

, et al., A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problems, Computers & Industrial Engineering 53(1) (2007), 149–162.

16.

Garey

M.R.

, Johnson

D.S.

and Sethi

, The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research 1(2) (1976), 117–129.

17.

Glover

, Heuristics for integer programming using surrogate constraints, Decision Sciences 8(1) (1977), 156–166.

18.

Glover

, Tabu search—part I, ORSA Journal on Computing 1(3) (1989), 190–206.

19.

Glover

and McMillan

, The general employee scheduling problem, An integration of MS and AI, Computers & Operations Research 13(5) (1986), 563–573.

20.

Holland

J.H.

, Outline for a logical theory of adaptive systems, Journal of the ACM (JACM) 9(3) (1962), 297–314.

21.

Jain

, et al., Scheduling of a flexible job-shop using a multi-objective genetic algorithm, Journal of Advances in Management Research(2012).

22.

Kacem

, Hammadi

and Borne

, Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic, Mathematics and Computers in Simulation 60(3–5) (2002), 245–276.

23.

Kacem

, Hammadi

and Borne

, Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems, IEEE Transactions on Systems Man and Cybernetics Part C (Applications and Reviews) 32(1) (2002), 1–13.

24.

Kennedy

and Eberhart

, Particle swarm optimization, in Proceedings of ICNN’95-International Conference on Neural Networks. (1995), IEEE.

25.

Khoukhi

, Prototyped genetic search: a cybernetical approach to job-shop scheduling problems, Kybernetes (2002).

26.

Koza

J.R.

and Koza

J.R.

, Genetic programming: on the programming of computers by means of natural selection, 1 (1992), MIT press.

27.

J.-Q.

, et al., A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem, The International Journal of Advanced Manufacturing Technology 52(5–8) (2011), 683–697.

28.

and Gao

, An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem, International Journal of Production Economics 174 (2016), 93–110.

29.

Liu

, et al., Efficient hybrid algorithms to solve mixed discrete-continuous optimization problems, Engineering Computations (2018).

30.

Martin

, Otto

S.W.

and Felten

E.W.

, Large-step Markov chains for the traveling salesman problem, (1991), Citeseer.

31.

Mastrolilli

and Gambardella

L.M.

, Effective neighbourhood functions for the flexible job shop problem, Journal of Scheduling 3(1) (2000), 3–20.

32.

Mati

, Rezg

and Xie

, An integrated greedy heuristic for a flexible job shop scheduling problem, in 2001 IEEE International Conference on Systems, Man and Cybernetics. e-Systems and e-Man for Cybernetics in Cyberspace (Cat. No. 01CH37236). (2001), IEEE.

33.

Moslehi

and Mahnam

, A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search, International Journal of Production Economics 129(1) (2011), 14–22.

34.

Nouiri

, et al., An effective and distributed particle swarm optimization algorithm for flexible job-shop scheduling problem, Journal of Intelligent Manufacturing 29(3) (2018), 603–615.

35.

Pachpor

P.S.

, et al., Application of Petri nets towards improved utilization of machines in job shop manufacturing environments, Journal of Manufacturing Technology Management (2017).

36.

Parsopoulos

K.E.

and Vrahatis

M.N.

, Recent approaches to global optimization problems through particle swarm optimization, Natural Computing 1(2-3) (2002), 235–306.

37.

Pezzella

, Morganti

and Ciaschetti

, A genetic algorithm for the flexible job-shop scheduling problem, Computers & Operations Research 35(10) (2008), 3202–3212.

38.

Phanden

R.K.

, Jain

and Verma

, A genetic algorithm-based approach for job shop scheduling, Journal of Manufacturing Technology Management 23(7) (2012), 937–946.

39.

Ruiz

, García-Díaz

J.C.

and Maroto

, Considering scheduling and preventive maintenance in the flowshop sequencing problem, Computers & Operations Research 34(11) (2007), 3314–3330.

40.

Scrich

C.R.

, Armentano

V.A.

and Laguna

, Tardiness minimization in a flexible job shop: A tabu search approach, Journal of Intelligent Manufacturing 15(1) (2004), 103–115.

41.

Seeley

, The Wisdom of the Hive Harvard University Press, Cambridge, Massachusetts, London, England, (1995).

42.

Shim

M.B.

, et al., Pareto-based continuous evolutionary algorithms for multiobjective optimization, Engineering Computations (2002).

43.

Sih

, Bell

and Johnson

J.C.

, Behavioral syndromes: an ecological and evolutionary overview, Trends in Ecology & Evolution 19(7) (2004), 372–378.

44.

Sonmez

and Baykasoglu

, A new dynamic programming formulation of (nxm) flowshop sequencing problems with due dates, International Journal of Production Research 36(8) (1998), 2269–2283.

45.

Talbi

E.-G.

, Metaheuristics: from design to implementation, 74 (2009), John Wiley & Sons.

46.

Türkyilmaz

, et al., A research survey: heuristic approaches for solving multi objective flexible job shop problems, Journal of Intelligent Manufacturing 2020, 1–35.

47.

Voudouris

, Guided Local Search—An illustrative example in function optimisation, BT Technology Journal 16(3) (1998), 46–50.

48.

Wang

G.-G.

, et al., A novel improved accelerated particle swarm optimization algorithm for global numerical optimization, Engineering Computations (2014).

49.

Wang

, A survey of maintenance policies of deteriorating systems, European Journal of Operational Research 139(3) (2002), 469–489.

50.

Wang

and Yu

, An effective heuristic for flexible job-shop scheduling problem with maintenance activities, Computers & Industrial Engineering 59(3) (2010), 436–447.

51.

Wang

, et al., A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem, The International Journal of Advanced Manufacturing Technology 51(5-8) (2010), 757–767.

52.

and Weng

M.X.

, Multiagent scheduling method with earliness and tardiness objectives in flexible job shops, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 35 (2) (2005), 293–301.

53.

Xia

and Wu

, An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems, Computers & Industrial Engineering 48 (2) (2005), 409–425.

54.

Xing

L.-N.

, Chen

Y.-W.

and Yang

K.-W.

, An efficient search method for multi-objective flexible job shop scheduling problems, Journal of Intelligent Manufacturing 20(3) (2009), 283–293.

55.

Xing

L.-N.

, Chen

Y.-W.

and Yang

K.-W.

, Multi-objective flexible job shop schedule: Design and evaluation by simulation modeling, Applied Soft Computing 9(1) (2009), 362–376.

56.

Yazdani

, Zandieh

and Tavakkoli-Moghaddam

, Evolutionary algorithms for multi-objective dual-resource constrained flexible job-shop scheduling problem, Opsearch 56(3) (2019), 983–1006.

57.

Zhang

, et al., An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem, Computers & Industrial Engineering 56(4) (2009), 1309–1318.

58.

Zhang

and Gen

, Multistage-based genetic algorithm for flexible job-shop scheduling problem, Journal of Complexity International 11(2) (2005), 223–232.

59.

Zou

, The whirlpool algorithm based on physical phenomenon for solving optimization problems, Engineering Computations (2019).

Introducing an effective meta-heuristic algorithm: Cosmogony algorithm (CA)

Abstract

Keywords

1 Introduction

2 Statement of a flexible job-shop scheduling problem with maintenance activities

3.1 Genesis of CA

4 CA for FJSP

4.1 Solution representation

Table 1 Problem FJSP 4×4/10 Job Operation M1 M2 M3 M4 1 O1,1 4 7 6 5 O1,2 2 6 – 5 2 O2,1 4 5 7 – O2,2 5 – 6 3 O2,3 – 5 4 7 3 O3,1 5 3 – 6 O3,2 – – 4 – 4 O4,1 2 4 5 – O4,2 – 4 2 – O4,3 5 4 6 3

4.3 Selection

4.4 Fitness function

Table 2 Parameters of the CA in the FJSO problem Parameters Value Parameters Value Population size 400 f1 6 P apt 30% f2 3 P e 20% Generation 80 P s 80% Number Nep 20 Nsp 20

5.1.1 Problem 8×8/27 operations without maintenance activities

Table 4 The PM task in the problem 8×8/27 operations PM 1 1 PM 2 1 PM 3 1 PM 4 1 PM 5 1 PM 6 1 PM 7 1 PM 8 1 Time window LB 1 1 1 3 5 6 0 3 1 3 UB 1 1 6 6 10 14 7 11 11 9 Duration 4 3 5 3 3 5 3 4

5.2.1 Problem 10×10/3 operations without maintenance activities

6.1 Convergence

6.2 Correlation

References

Table 1
Problem FJSP 4×4/10

Job Operation M1 M2 M3 M4

1 O_1,1 4 7 6 5

O_1,2 2 6 – 5

2 O_2,1 4 5 7 –

O_2,2 5 – 6 3

O_2,3 – 5 4 7

3 O_3,1 5 3 – 6

O_3,2 – – 4 –

4 O_4,1 2 4 5 –

O_4,2 – 4 2 –

O_4,3 5 4 6 3

Table 2
Parameters of the CA in the FJSO problem

Parameters Value Parameters Value

Population size 400 f₁ 6

P _apt 30% f₂ 3

P _e 20% Generation 80

P _s 80% Number

Nep 20

Nsp 20

Table 4
The PM task in the problem 8×8/27 operations

${PM}_{1}^{1}$ ${PM}_{2}^{1}$ ${PM}_{3}^{1}$ ${PM}_{4}^{1}$ ${PM}_{5}^{1}$ ${PM}_{6}^{1}$ ${PM}_{7}^{1}$ ${PM}_{8}^{1}$

Time window ${LB}_{1}^{1}$ 1 3 5 6 0 3 1 3

${UB}_{1}^{1}$ 6 6 10 14 7 11 11 9

Duration 4 3 5 3 3 5 3 4