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
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.
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 oi,1, oi,2, ... ,oi,n and a set of machines such as M ={ M1, M2, …, M
m
}. There is a set of machines for each operation oi,j which is able to process it. Also, oi,j must be assigned to one of the machines. Therefore, each operation oi,j (1 ⩽ i ⩽ n, 1 ⩽ j ⩽ n
i
) has to be performed to complete one job. The oi,j operation processing time is Pi,j,k on a M
k
machine (M
k
ɛM). There is L
k
number of maintenance activities in the framework of
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].
Where Ω is the feasible solution space and x ={ x1, x2, …, 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:
f1: Makespan of the jobs (C M ) or maximal completion time of machines.
f2: Total workload of the machines, which represents the total workload time over all machines.
f3 : 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
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.
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].

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).

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.

The evolutionary cycle of CA.

The procedure of the CA 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.
CA for FJSP
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 (ν1) provides an assignment of operations to machines, and the other one (ν2) 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.
Problem FJSP 4×4/10
Problem FJSP 4×4/10

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

Gant chart of the solution shown in Fig. 5.
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 (v1);(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).
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 .
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 (f1) for a small maximal workload (f2) a small total workload (f3).
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.
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
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 (v2) or machine assignment vector (v1). The following mutation procedure is used in the CA algorithm as the formation of onlooker species:
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 (ν2) as follow: Suppose i and j are positions 3 and 6 from ν2, respectively. Also, the contents of positions 3 and 6 are numbers 3 and 4, respectively. First, we create the operation sequence vector (ν2) 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.

The formation of an onlooker species for indicator species in Fig. 5.
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.

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

The scheme from the progress of the sequencing process.
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 (ν2) whereas contents of (ν1) are transmitted together with the operation sequence vector (ν2) as follow: Two solutions (or complementary species) are selected from the current population as parents according to the selection process. Suppose P1 and P2 are selected as the parents of the available population (P1 ≠ P2). 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 P1 at positions with bit 0 while inherits the element of P2 at positions with bit 1. As shown in Fig. 11-a, when the offspring inherited the element from P1, 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.

Instances from parents and a mask.

Illustrate the procedure of uniform crossover.
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.

The framework of the CA algorithm.

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.
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):
Parameters of the CA in the FJSO problem
Parameters of the CA in the FJSO problem
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 f1(l), f2(l), and f3(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.
Comparison of CA algorithm with other methods
Comparison of CA algorithm with other methods

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

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

Optimization Solution 2 of problem 8×8/27, f1 = 16, f2 = 73, f3 = 13.
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.
The PM task in the problem 8×8/27 operations
The PM task in the problem 8×8/27 operations
Comparison of CA algorithm with other method in the maintenance task with non-fixed starting time

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

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.

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.

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.

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.

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.
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.

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

Optimization Solution 2 of problem 10×10/30 f1 = 7, f2 = 42, f3 = 6.
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.
The fixed starting time of PM task in the problem8×8/27 operation
The fixed starting time of PM task in the problem8×8/27 operation
The FJSP with maintenance tasks in the fixed starting time
The PM task in the problem 10×10/30

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.
The fixed starting time PM task in the problem 10×10/30

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

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

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

Optimization Solution 2 of problem 10×10/30 with maintenance activities fixed starting time in case (b): f1 = 10, f2 = 60, f3 = 8.
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.
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

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

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

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

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

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

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

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.
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.
