تکامل قوانین دیسپاچینگ با استفاده از برنامه نویسی ژنتیک برای حل مسائل تولید کارگاهی قابل انعطاف چند هدفه

We solve the multi-objective flexible job-shop problems by using dispatching rules discovered through genetic programming. While Simple Priority Rules have been widely applied in practice, their efficacy remains poor due to lack of a global view. Composite dispatching rules have been shown to be more effective as they are constructed through human experience. In this paper, we evaluate and employ suitable parameter and operator spaces for evolving composite dispatching rules using genetic programming, with an aim towards greater scalability and flexibility. Experimental results show that composite dispatching rules generated by our genetic programming framework outperforms the single dispatching rules and composite dispatching rules selected from literature over five large validation sets with respect to minimum makespan, mean tardiness, and mean flow time objectives. Further results on sensitivity to changes (in coefficient values and terminals among the evolved rules) indicate that their designs are robust.

In today’s highly competitive marketplace, a high level of delivery performance has become necessary to satisfy customers. Due to market trends, product orders of low volume, high variety types have been increasing in demand. Hoitomt, Luh, and Pattipati (1993) mentions that these products comprise between 50% and 75% of all manufactured components, thereby making schedule optimization an indispensable step in the overall manufacturing process. The job-shop scheduling problem (JSP) is one of the most popular manufacturing optimization models used in practice (Jain & Meeran, 1998). It has attracted many researchers due to its wide applicability and inherent difficulty (Carlier and Pinson, 1999, Kolonko, 1999, Nowicki and Smutnicki, 1996 and Yamada and Nakano, 1996). It is also well known that the JSP is NP-hard (Garey, Johnson, & Sethi, 1996), hence general, deterministic methods of search are inefficient as the problem size grows larger. The nxm classical JSP involves n jobs and m machines. Each job is to be processed on each machine in a predefined sequence and each machine processes only one job at a time. In practice, the shop-floor setup typically consists of multiple copies of the most critical machines so that bottlenecks due to long operations or busy machines can be reduced. As such, an operation may be processed on more than one machine having the same function. This leads to a more complex problem known as the flexible job-shop scheduling problem (FJSP). The extension involves two tasks; assignment of an operation to an appropriate machine and sequencing the operations on each machine. In addition, for complex manufacturing systems, a job can typically visit a machine more than once (known as recirculation). These three features of the FJSP significantly increase the complexity of finding even approximately optimal solutions ( Pinedo & Chao, 1999, chap. 3). Furthermore, instead of considering only a single objective, most scheduling problems in practice involve simultaneous optimization of several competing objectives. Therefore, in order to tackle the FJSP problems found in practice, efficient optimization strategies are required to deal with both multiple objectives and exponential search space complexity. The classical JSP and FJSP (in single or multi-objectives) have been solved by many stochastic local search methods, such as Simulated Annealing (Kolonko, 1999), Tabu Search (Brandimarte, 1993, Mastrolilli and Gambardella, 2000 and Nowicki and Smutnicki, 1996), Genetic Algorithms (Ho and Tay, 2004, Kacem et al., 2002a, Kacem et al., 2002b and Tay and Wibowo, 2004) or Artificial Immune Systems (Ong, Tay, & Kwoh, 2005). The reported results of applying them show that good approximations of optimality can be found, albeit at the expense of huge computational cost, particularly when the problem size is large. In practice, dispatching rules have been applied to avoid these costs (Blackstone et al., 1982, Oliver and Chandrasekharan, 1997 and Panwalkar and Wafik, 1977). Although the qualities of solutions produced by dispatching rules are no better than the local search methods, they are the more frequently applied technique due to their ease of implementation and their low time complexities. Whenever a machine is available, a priority-based dispatching rule inspects the awaiting jobs and selects one with the highest priority to be processed next. Recently, the introduction of composite dispatching rules (CDR) have been increasingly investigated by the some researchers (Jayamohan and Rajendran, 2004 and John and Xiaoming, 2004), but typically only for classical JSPs. These rules are the heuristic combination of single dispatching rules that aim to inherit the advantages of the former. Empirically, results show that with careful combination, the composite dispatching rules will perform better than the single ones with regards to the quality of schedules. However, little is yet known about the robustness of such human-made designs to changes in the parameter and operator spaces. In this paper, we investigate the potential use of genetic programming (GP) for evolving effective and robust composite dispatching rules for solving the multi-objective FJSP. Although there are many multi-objective approaches for searching continuous and/or discrete search spaces (Coello, 2005), a survey of the research literature shows that there are few previous works on dispatching rules that satisfy multiple objectives simultaneously (Barman, 1997, Jayamohan and Rajendran, 2004 and Oliver and Chandrasekharan, 1997). The purpose of this research is to find effective and robust CDRs that perform better than the dispatching rules presented in literature for solving the multi-objective FJSP problems. By using a wide training data set, we believe that the evolved CDRs can be applied directly in practice without further modifications. Furthermore, these CDRs can be used for population generation in other local search methods for solving FJSPs, such as Genetic Algorithms (Ho and Tay, 2004 and Tay and Wibowo, 2004) or Artificial Immune Systems (Ong et al., 2005). The remainder of this paper is organized as follows. Section 2 gives the formal definition of the multi-objective FJSP. Section 3 gives an overview of GP, reviews recent works for solving the JSP and FJSP using dispatching rules, as well as the development of multi-objective Evolutionary Algorithms in literature. Section 4 describes our proposed GP framework for evolving CDRs. Section 5 presents the design of experiments for performance evaluation while Section 6 analyzes the performance results of using the evolved CDRs obtained with GP in comparison to the other well-known dispatching rules such as EDD (Earliest Due Date) and SPT (Shortest Processing Time) for solving the multi-objective FJSPs. We present our results by evaluating the components of effective CDRs through single-objective optimizations, and then evaluating the evolved CDRs for multiple objectives simultaneously. Finally, Section 7 gives some concluding remarks and directions for future work.

In this paper, a GP-based approach for discovering effective composite dispatching rules for solving the multi-objective FJSP has been presented and analyzed. CDRs have been studied widely by previous researchers (Blackstone et al., 1982, Oliver and Chandrasekharan, 1997 and Panwalkar and Wafik, 1977). However, all of them were constructed based on the experience of a human scheduler. We employ a GP framework to generate a CDR based on algebraic fundamental terminals that can effectively solve the multi-objective FJSP (together with a machine assignment rule). Five composite dispatching rules were generated by our GP framework over a large training set. These rules are based on the combination of parameters such as processing time, release date, due date, current time, number of operations and average total processing time of each job. Extensive simulations have been carried out to evaluate the performance of the five evolved rules over varying degrees of problem flexibility and due date tightness. Five other popular rules selected from literature were also evaluated and used as performance benchmarks. The experimental results of these popular rules validate the literature finding that no rule performs well on all criteria, and the algebraic combination of the parameters contributes to the efficacy of the rules. It was found that EDD is significantly better than the other rules from literature in minimizing mean tardiness, mean flow time and percentage of tardy jobs while it is poor in minimizing the makespan. However, all the generated rules found by GP outperformed the EDD with respect to all objectives. It shows that the application of our GP framework for constructing effective composite dispatching rules for solving the multi-objective FJSPs has been successful. In particular, two parameters aTPT and nOps that have received limited study from previous research was found to contribute significantly to the effectiveness of evolved CDRs. We have also shown statistically that our evolved CDRs are sufficiently well-designed through the use of ANOVA (which analyzed the sensitivity to changes in the coefficient values and terminal parameters). Finally, by using a large training data set, we believe that our evolved CDRs can be applied directed in practice without further modifications. Several possible extensions of this study can be developed. Similar to other applications of GP where the parameters are sensitive, denser terminal sets and more varied ADFs should be investigated to improve the generated rules. The approach of this study can be applied to find the efficient composite dispatching rules for other similar problems, such as a flow shop or the classical job shop. Further research about minimizing both earliness and tardiness could be considered. The application of GP framework to construct CDRs for dynamic job shop with breakdown machines will be investigated. The rules evolved from this GP framework are still quite complex in structure. Therefore, an algebraic simplification tool could be used to make the formula more meaningful. Consideration could even be given to including the number of parameters used as a measure for minimization. In this paper, the same weight 1/3 is assigned to the three same priority objectives. Different specifications of the weight values of different priority objectives can also be considered.