This paper proposes an effective discrete chemical-reaction optimization (DCRO) algorithm for solving the flexible job-shop scheduling problems with maintenance activity constraints. Three minimization objectives—the maximum completion time (makespan), the total workload of machines and the workload of the critical machine are considered simultaneously. In the proposed algorithm, each solution is represented by a chemical molecule. Four improved elementary reactions, i.e., on-wall ineffective collision, inter-molecular ineffective collision, decomposition, and synthesis, are developed. A well-designed crossover function is introduced in the inter-molecular collision, synthesis, and decomposition operators. Tabu search (TS) based local search is embedded in DCRO to perform exploitation process. In addition, the decoding mechanism considering the maintenance activity is presented. Several neighboring approaches are developed to improve the local search ability of the DCRO. The proposed algorithm is tested on sets of the well-known benchmark instances. Through the analysis of experimental results, the highly effective performance of the proposed DCRO algorithm is shown against the best performing algorithms from the literature.
Graphical abstract
An effective discrete chemical-reaction optimization (DCRO) algorithm is proposed for solving the flexible job-shop scheduling problems with maintenance activity constraints. Through the analysis of experimental results, the highly effective performance of the proposed DCRO algorithm is shown against the best performing algorithms from the literature. Comparison of the convergence curve for the average Pareto distance between DCRO and CRO for 15 × 10-m.
The flexible job-shop scheduling problem (FJSP) is a branch of the classical JSP, which is more computationally difficult than the latter because of the addition need of machine assignment for each operation [1] and [2]. Due to the complexity of the FJSP, meta-heuristic algorithms have become a practical alternative of solving techniques for these problems. For the FJSP with makespan criterion, many different approaches have been developed, such as tabu search (TS [2], [3], [4], [5], [6], [7] and [8]), genetic algorithm (GA [9], [10], [11] and [12]), particle swarm optimization (PSO [13], [14], [15] and [16]), the parallel variable neighborhood search (PVNS [17]), the knowledge-based ant colony optimization (KBACO [18]), the artificial immune algorithm (AIA [19]), and the climbing depth-bounded discrepancy search (CDDS [20]).
In very recent years, researchers have considered the importance of the FJSPs with multiple objectives. There are mainly two kinds of approaches for solving the multi-objective FJSP: the first is to combine all objectives into one weighted objective; the second is the Pareto based method. For the first kind, many heuristics and meta-heuristics have been used, such as the hybrid GA (hGA [12]), the hybrid of PSO and simulated annealing (PSO + SA [13]), the hybrid of PSO and TS (PSO + TS [16]), the framework of local search based algorithms [21], and the hybrid TS algorithm (HTSA [22]). The Pareto based method has taken little consideration. Kacem et al. [23] proposed a Pareto based algorithm which combines evolutionary algorithms and fuzzy logic. Ho and Tay [24] developed an approach named MOEA-GLS by utilizing evolutionary algorithm and guided local search. Moslehi et al. [25] conducted a Pareto approach using PSO and local search.
Nowadays, production scheduling and maintenance planning have been received considerable attention because of their importance both in the fields of manufacturing and combinatorial research. Ma et al. [26] surveyed the scheduling problems with maintenance activity constraints during very recent years. It shows that most literature considered machine availability constraints in solving single machine problems, parallel machine problems, flow shop scheduling problems, and job shop scheduling problems. There are few literature considers the availability constraints in the FJSP context. Gao et al. [27] proposed a hybridization of GA and local search method for solving the multi-objective FJSPs with preventive maintenance (PM) tasks. Zribi et al. [28] considered the MPM job shop scheduling problem with maintenance activity constraints. Wang and Yu [29] investigated a filtered beam search (FBS) based algorithm for FJSPs with PM tasks.
Very recently, by simulating the behavior of chemical molecular reaction, an efficient chemical-reaction optimization (CRO) algorithm is proposed by Lam and Li [30], [31] and [32] to optimize combinatorial problems. Experimental comparisons demonstrated that the performance of the CRO algorithm is competitive to other swarm intelligent algorithms. Due to its ability to escape from the local optima, CRO has been applied for solving many scheduling problems, such as grid scheduling, network scheduling optimization [30], [31] and [32]. Since there is no published work to deal with the flexible job-shop scheduling problem by using the CRO algorithm, we develop a novel discrete CRO (DCRO) algorithm for solving the multi-objective FJSPs. Furthermore, both maintenance activity case and non-maintenance activity case are considered, respectively.
The rest of this paper is organized as follows: In Section 2, we briefly describe the problem formulation. Then, the chemical-reaction optimization algorithm is presented in Section 3. The proposed DCRO algorithm is shown in Section 4. Section 5 reports the experimental results and compares with other algorithms in the literature to demonstrate the superiority of the DCRO performance. Finally, the last section presents conclusions of our work.
This paper aims at solving the multi-objective FJSPs with minimization of the maximal completion time, the total workload, and the maximal workload. We considered the problem under both the preventive maintenance constraints and non-maintenance constraints cases and presented a discrete chemical-reaction optimization algorithm. To the best of our knowledge, this was the first reported application of the CRO algorithm for solving the problem under consideration. In the proposed algorithm, a molecule is used to represent a solution for the problem. A decoding method is introduced to consider the maintenance activities. Four problem-relative elementary reactions are developed to implement the local search and global search. Computational simulations and comparisons demonstrated the effectiveness and efficiency of the proposed algorithm. Our future work is to investigate the other meta-heuristics for the multi-objective flexible job-shop scheduling problems and generalize the application of the CRO algorithm to solve other combinatorial optimization problems.
