الگوریتم مصنوعی گسسته زنبور عسل برای مساله برنامه ریزی چند هدفه انعطاف پذیر تولید کارگاهی با فعالیت های تعمیر و نگهداری

This paper presents a novel discrete artificial bee colony (DABC) algorithm for solving the multi-objective flexible job shop scheduling problem with maintenance activities. Performance criteria considered are the maximum completion time so called makespan, the total workload of machines and the workload of the critical machine. Unlike the original ABC algorithm, the proposed DABC algorithm presents a unique solution representation where a food source is represented by two discrete vectors and tabu search (TS) is applied to each food source to generate neighboring food sources for the employed bees, onlooker bees, and scout bees. An efficient initialization scheme is introduced to construct the initial population with a certain level of quality and diversity. A self-adaptive strategy is adopted to enable the DABC algorithm with learning ability for producing neighboring solutions in different promising regions whereas an external Pareto archive set is designed to record the non-dominated solutions found so far. Furthermore, a novel decoding method is also presented to tackle maintenance activities in schedules generated. The proposed DABC algorithm is tested on a set of the well-known benchmark instances from the existing literature. Through a detailed analysis of experimental results, the highly effective and efficient performance of the proposed DABC algorithm is shown against the best performing algorithms from the literature.

Scheduling is one of the most important key issues in planning and controlling the manufacturing systems [1] and [2]. The classical job-shop problem is one of the most difficult problems in this area. It is basically concerned with scheduling a set of jobs through a set of machines in order to minimize a creation performance criterion such that each job is consisted of a sequence of consecutive operations, each operation demands only one machine which is continuously available and can process one operation at a time without interruption. On the other hand, the classical JSP can be generalized into the flexible job shop scheduling problem (FJSP) where two sub-problems are solved: the first one is called a routing sub-problem that assigns each operation to a machine selected from any of a set of suitable machines, the second one is called a scheduling sub-problem consisting of sequencing all the assigned operations on all machines in order to yield a feasible schedule to minimize a predefined performance criterion. In the classical JSP, job routings are known in advance and each operation is performed on a predefined machine. However, in the FJSP, each operation can be performed on any among a set of available machines. Therefore, the FJSP is more difficult than the classical JSP due to the consideration of both job routing and job scheduling. The general JSP is strongly NP-hard, while the FJSP is a much more complex version of the JSP, so the FJSP is strongly NP-hard [3]. Due to the complexity of the FJSP, no exact method has so far been developed to tackle the problem within a reasonable amount of time [2]. Thus, meta-heuristic algorithms have become a practical tool for solving this problem. For the FJSP with makespan criterion, tabu search (TS) has been proved to an efficient algorithm such as in Brandimarte [4], Mastrolilli et al. [5], Fattahi et al. [3], Fattahi et al. [6], Ennigrou and Ghedira [7], Li et al. [8], and Bozejko et al. [9], whereas the genetic algorithm (GA) has also been applied by many researchers, such as Kacem et al. [10], Ho et al [11], Pezzella et al. [12] and Gao et al. [13]. The particle swarm optimization (PSO) has also been investigated by Xia and Wu [14], Gao et al. [15], Liu et al. [16] and Zhang et al. [17]. In addition to the above, some other meta-heuristics have been introduced for the problem on hand such as the parallel variable neighborhood search (PVNS) algorithm [18], the knowledge-based ant colony optimization (KBACO) algorithm [19], the artificial immune algorithm (AIA) [2], and the climbing depth-bounded discrepancy search (CDDS) algorithm [20]. Recently, Wang et al. [21] proposed an effective artificial bee colony (ABC) algorithm for solving the single-objective FJSP, where different crossover and mutation approaches are conducted, and local search based on moving critical operations is also embedded. Unlike the FJSP with a single objective, the FJSPs with multiple objectives have attracted attention by the researchers very recently. For example, Kacem et al. [22] proposed a hybrid approach combining the GA with a local search (AL + CGA). Xia and Wu [14] developed a hybrid method employing PSO with the simulated annealing (SA). Tay and Ho [23] developed a genetic programming with evolving dispatching rules. Gao et al. [13] provided a hybrid GA (hGA). Xing et al. [24] and [25] presented some local search algorithms, too. Zhang et al. [17] introduced a hybrid PSO with a TS algorithm. Li et al. [26] investigated the TS algorithm with some efficient neighborhood structures (HTSA). Most of the literature for the multiple-objective FJSPs adopts the aggregation approach where a deterministic weight is assigned to each objective and these objectives are aggregated into a single objective. The drawback of the above approach is to generate only a single solution at each run. Thus, little information can be provided to the decision maker about the quality of each performance criterion. The Pareto-based approach has recently become a practical tool for solving the multi-objective optimization problems [27]. Kacem et al. [22] proposed a Pareto-based algorithm which combines evolutionary algorithms with fuzzy logic. Tay and Ho [23] developed an approach called MOEA-GLS by combining the evolutionary algorithm with a guided local search. Moslehi and Mahnam [28] conducted a Pareto approach using PSO with a local search. Very recently, Li et al. [29] presented a discrete ABC for solving the multi-objective FJSP, where a crossover operator is developed for information sharing among employed bees, the Pareto archive set is used to record the non-dominated solutions, a fast Pareto set update function is designed, and several local search methods are introduced. Nowadays, production scheduling and maintenance planning have been received considerable attention because of their importance both in the fields of manufacturing and combinatorial research [30]. Schmidt [30] has outlined most of the literature related to deterministic scheduling problems with machine availability constraints until 1998 whereas Ma et al. [31] surveyed the scheduling problems with deterministic machine availability constraints very recently. It can be concluded from these survey papers that most of the literature considered machine availability constraints in solving single machine problems, parallel machine problems, flow shop scheduling problems, and job shop scheduling problems. However, it was pointed out that there are a few literatures considering the availability constraints in the FJSPs. Regarding the availability constraints, Gao et al. [32] proposed a hybridization of GA with a local search algorithm for solving the multi-objective FJSPs with preventive maintenance (PM) activities whereas Zribi et al. [33] considered the classical JSP with preventive maintenance (PM) activities. Chan et al. [34] also studied the distributed flexible manufacturing system (FMS) with availability constraints. Wang and Yu [35] proposed a filtered beam search (FBS) for solving the single-objective FJSP with at most one maintenance task for each machine. By simulating the behavior of honey bee swarm intelligence, an artificial bee colony (ABC) algorithm is proposed by Karaboga [36], [37] and [38] to optimize multi-variable and multi-modal continuous functions. Experimental comparisons demonstrated that performance of the ABC algorithm is competitive to other swarm intelligent algorithms. Due to its fewer control parameters and ease of implementation, researchers have adopted the ABC algorithm to solve many practical optimization problems [39]. In this study, we develop a novel discrete ABC (DABC) algorithm for solving the multi-objective FJSP with preventive maintenance activities. Both machine availability case and non-machine availability case are considered, respectively. The main features of the proposed DABC are as follows: (1) several problem-related neighborhood structures are designed; (2) a self-adaptive neighborhood structure strategy is conducted to balance the exploitation and exploration capability; (3) a TS-based local search heuristic is applied to enhance the exploitation performance; (4) a well-designed initialization method is embedded; (5) a decoding strategy considering the maintenance tasks is developed; (6) a Pareto archive set is constructed to record the non-dominated solutions. The rest of this paper is organized as follows: Section 2 briefly describes the problem formulation. Then, the artificial bee colony algorithm is presented in Section 3. The proposed DABC algorithm is given in detail in Section 4 whereas Section 5 gives the experimental results and compares to the best performing algorithms from the existing the literature to demonstrate the superiority of the DABC algorithm. Finally, Section 6 gives the concluding remarks and future research direction.

This paper aims at solving the multi-objective FJSPs with minimization of the maximal completion time, the total workload, the maximal workload. We considered the problem under both the preventive maintenance constraints and non-maintenance constraints cases and presented a discrete artificial bee colony algorithm. In the proposed algorithm, the food sources were represented as discrete machine number and job permutation. The ABC based searching mechanism with an effective population initialization approach and a TS based local search with a self-adaptive neighboring food source generation strategy were developed to perform exploration and exploitation for promising solutions within the entire solution space. Due to the reasonable hybridization of the ABC search and TS based local search, the proposed DABC algorithm had the ability to obtain promising solutions for the problem considered. 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 ABC algorithms to solve other combinatorial optimization problems.