بهینه سازی واکنش شیمیایی برای حل مسائل فازی برنامه ریزی تولید کارگاهی به همراه فعالیت های تعمیر و نگهداری انعطاف پذیر
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|21626||2013||14 صفحه PDF||سفارش دهید||10757 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : International Journal of Production Economics, Volume 145, Issue 1, September 2013, Pages 4–17
This paper proposes a hybrid chemical-reaction optimization (HCRO) algorithm for solving the job-shop scheduling problem with fuzzy processing time. The flexible maintenance activities under both resumable and non-resumable situations are also considered to make the problem more close to the reality. In the proposed algorithm, each solution is represented by a chemical molecule. Four elementary reactions, i.e., on-wall ineffective collision, inter-molecular ineffective collision, decomposition, and synthesis, are imposed. A well-designed crossover function is introduced in the synthesis and decomposition operators. In order to balance the exploitation and exploration, HCRO divides the evolution phase into two loop bodies: the first loop body contains on-wall ineffective collision and inter-molecular ineffective collision, while the second loop body includes all the four elementary reactions. Tabu search (TS) based local search is embedded in the proposed algorithm to enhance the convergence capability. A novel decoding approach is utilized to schedule each operation, while considering each flexible preventive maintenance activity on each machine. 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 HCRO algorithm is shown against three efficient algorithms from the literature, i.e., SMGA (Sakawa and Mori, 1999), GPSO (Niu et al., 2008), and RKGA (Zheng et al., 2010).
Recently, job-shop scheduling problem (JSSP) has received more and more research attentions (Armentano and Scrich, 2000). In the classical JSSP, n jobs are to be scheduled on m machines with predefined sequence and constraints. The processing time for each operation on each machine is generally deterministic. However, in most practical industries, the processing time for each operation is just a fuzzy value, because various factors are involved in the real-world problems. This is particularly true in the practical situations when human-centred factors are incorporated into the problems. Kuroda and Wang (1996) proposed a branch-and-bound algorithm for solving both the static and the dynamic JSSP. After that, many researchers have conducted different approaches for solving the fuzzy JSSP (FJSSP). Genetic algorithm (GA) is one of the most popular algorithms which have been utilized for the problem. Sakawa and Mori (1999) designed an efficient GA for solving the FJSSP with fuzzy processing time and fuzzy due date. Again, in 2000, a fuzzy programming based GA was presented by Sakawa and Kubota for the multi-objective FJSSP. Song et al. (2006) developed a hybrid algorithm combining GA, Ant colony optimization (ACO), and a local search approach. Inés et al. (2010) solved the multi-objective JSSP with uncertain durations and crisp due dates by an efficient GA embedded with a fuzzy programming approach. Lei (2010a) developed a random key GA algorithm for the problem. The other swarm intelligent algorithms have also been introduced for solving the FJSSP. Wu et al. (2006) designed an efficient algorithm by combining the fuzzy ranking method and shifting bottleneck procedure. Lei (2007) proposed an algorithm to apply particle swarm optimization (PSO) to solve the FJSSP with three objectives. Niu et al. (2008) introduced a hybrid algorithm combining PSO and GA for the problem. Very recently, a modified differential evolution (DE) algorithm was conducted by Hu et al. (2011) for solving the FJSSP with fuzzy processing time and fuzzy due date. Most literature considering JSSP assumes that each machine is available in the production horizon. However, in reality, operations may be interrupted by the preventive maintenance (PM) activity on the processing machines. Schmidt (2000) has summarized most results related to deterministic scheduling problems with PM constraints published before 1998. Ma et al. (2010) 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, and flow shop scheduling problems. There are few literature considering the availability constraints in the job-shop scheduling context. For solving the job-shop scheduling problem with deterministic processing time under PM situation, Gao et al. (2006) proposed a hybridization of GA and the local search method for solving the multi-objective flexible job-shop scheduling problems (FJSP) with PM tasks. Zribi et al. (2008) considered the MPM job-shop scheduling problem with maintenance activity constraints. Wang and Yu (2010) investigated a filtered beam search (FBS) based algorithm for FJSPs with PM tasks. For the fuzzy job-shop scheduling problem with PM activities (FJSSP-PM), Lei (2010b) solved the FJSSP under availability constraints with the objective to maximize the minimum agreement index subject to periodic maintenance. Zheng et al. (2010) proposed a random key based GA. Lei (2011) again developed an efficient swarm-based neighborhood search algorithm for the problem. However, the above literature considers PM tasks at a fixed interval in FJSSP context. The FJSSP with PM tasks at a flexible interval are more close to the production reality (Gao et al., 2006 and Wang and Yu, 2010), and therefore should be given more research focuses. Very recently, by simulating the behavior of molecules in chemical reactions, an efficient chemical-reaction optimization (CRO) algorithm was proposed by Lam and Li (2010b) to optimize combinatorial problems. CRO has four elementary reactions, namely, on-wall ineffective collision, inter-molecular ineffective collision, decomposition, and synthesis. The first two reaction operators perform the exploitation function, while the last two reactions complete the exploration tasks. Meanwhile, CRO has a buffer to collect energy produced by on-wall ineffective collision, and help the molecules to escape from the local optima. Based on the above characteristics, CRO is suitable for solving problems with many local optima, such as scheduling problems, and continuous optimization problems. Experimental comparisons demonstrated that the performance of CRO is competitive to other swarm intelligent algorithms (Lam and Li, 2010b, Lam et al., 2010a, Xu et al., 2010 and Lam and Li, 2012b). Due to its ability to escape from the local optima, CRO has been applied for solving many scheduling problems, such as peer-to-peer live streaming scheduling (Lam et al., 2010a), resource-constrained project scheduling problem (Lam and Li, 2010b), grid scheduling (Xu et al., 2010), task scheduling in grid computing (Xu et al., 2011), and continuous optimization problems (Lam et al., 2012a). Although the canonical CRO has many advantages, it should be improved in many aspects, especially its exploitation capability. Therefore, in this study, we propose a hybrid CRO (HCRO) for solving the fuzzy job-shop scheduling problem with flexible maintenance constraints. The main differences between CRO and HCRO are as follows: (1) TS-based local search is embedded in HCRO to enhance the exploitation capability; (2) A well-designed crossover operator is developed in HCRO; (3) HCRO divides the evolution phase into two loop bodies: the first loop body contains two reactions, i.e., on-wall ineffective collision and inter-molecular ineffective collision; the second loop body includes all the four elementary reactions. The evolution phase begins with the first loop body, that is, the exploitation task is firstly been performed. When the exploitation cannot be continued after certain number of generations, the second loop body starts to perform both exploration and exploitation functions. Then, the two loop bodies run alternatively. The rest of this paper is organized as follows: Section 2 briefly describes the problem. Then, the canonical CRO is presented in Section 3. Section 4 gives the framework of the proposed algorithm. Section 5 illustrates the experimental results and compares to the present performing algorithms from the literature to demonstrate the superiority of the proposed algorithm. Finally, Section 6 gives the concluding remarks and future research direction.
نتیجه گیری انگلیسی
In this study, a hybrid algorithm combing the chemical-reaction optimization and the tabu search algorithm is proposed for solving the fuzzy job-shop scheduling problem with flexible preventive maintenance activities. The detailed encoding and decoding mechanism is developed for the problem. The main contributions of the proposed HCRO are as follows: (1) To enhance the exploitation capability of the proposed algorithm, TS-based local search is embedded in HCRO; (2) In the canonical CRO, decomposition and synthesis reactions are used to produce molecules with very different structures. That is, the above two reactions complete the exploration task in the evolution phase. To make the two reactions perform exploration functions while maintaining convergence capability, a well-designed crossover operator is developed in HCRO; (3) HCRO divides the evolution phase into two loop bodies: the first loop body contains on-wall ineffective collision, inter-molecular ineffective collision; the second loop body includes all the four elementary reactions. The evolution phase begins with the first loop body, that is, the exploitation task is firstly been performed. When the exploitation cannot be continued after certain number of generations, the second loop body started to perform both exploration and exploitation function. Then, the two loop bodies run alternatively. Two sets of benchmarks with flexible PM activities are tested to make a detailed comparison between HCRO and other efficient algorithms from the literature. The benchmarks range from 10 jobs-10 machines to 15 jobs-10 machines. Experimental results show the robustness and efficiency of the proposed algorithm. The future work is as follows: (1) To improve the four elementary reactions and enhance the balance between the exploitation and exploration, and to increase the simulation result reliability; (2) To apply the proposed algorithm for solving other potential applications, such as the fuzzy flexible job-shop scheduling problem with flexible PM activities, and the flexible flow shop scheduling problem with flexible PM activities; (3) To apply HCRO for solving other kinds of job-shop scheduling problems, such as multi-objective JSSP, JSSP with setup-time, and no-wait JSSP. The proposed HCRO is suitable to be applied to JSSP in general, after completing the following issues: (a) problem adaptive encoding and decoding mechanism; (b) improved elementary reactions; (c) neighborhood structure considering the problem structure. (4) To apply the design of experiment (DoE) method to determine parameters for the experiments.