Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems

Abstract

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.

Introduction

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, 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, Nowicki and Smutnicki, 1996), Genetic Algorithms (Ho and Tay, 2004, Kacem et al., 2002a, Kacem et al., 2002b, 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, 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, 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, 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, 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.