Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems
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.
Section snippets
Problem definition
Similar to the classical JSP, solving the FJSP requires the optimal assignment of each operation of each job to a machine with known starting and ending times. However, the task is more challenging than the classical one because it requires a proper selection of a machine from a set of machines to process each operation of each job. Furthermore, if a job is allowed to recirculate, this will significantly increase the complexity of the system (Pinedo, 2002, chap. 2). The multi-objective FJSP is
Multiple objective optimization for job-shop scheduling
Evolutionary Algorithms (EAs) have been used widely to solve multi-objective optimization problems. Generally, they can be classified into three approaches: population-based, pareto-based, and aggregation function (Coello, 2005). Population-based approaches, such as VEGA (Schaffer, 1985), are based on the division of the current population into s sub-populations where s is the number of objectives. At each generation, s sub-populations are generated by performing proportional selection
Design of the GP framework
In GP, an individual (i.e., computer program) is composed of terminals and functions. Therefore, when applying GP to solve a specific problem, they should be carefully selected and designed to satisfy the requirements of the current problem. After evaluating many parameters related to the FJSP, the terminal set and the function set that are used in our algorithm are described as follows.
Experimental design
In this section, we describe the parameter settings used for our GP framework and the generation of test cases for evolving and evaluating CDRs.
Analysis of experimental results
This section reports and analyses the results of our experiments for evolving CDRs using our GP framework. The system was implemented using C++, running on a 2 GHz PC with 512 MB RAM. Firstly, the best five evolved CDRs and five selected SDRs and CDRs in literature are reported. As mentioned earlier in Section 4.3, the least waiting time assignment (Ho & Tay, 2004) is used to find a suitable machine to process an operation Oi,j. However for the first assignment, all the machines are idle,
Conclusion and future works
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, 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
Acknowledgments
This research was funded in part by Nanyang Technological University and CEI Contract Manufacturing Limited Company, Singapore.
References (38)
- et al.
Investigating the use of genetic programming for a classic one-machine scheduling problem
Advances in Engineering Software
(2001) - et al.
Development and analysis of cost-based dispatching rules for job shop scheduling
European Journal of Operational Research
(2004) - et al.
Pareto-optimality approach for flexible job-shop scheduling problems: Hybridization of evolutionary algorithms and fuzzy logic
Mathematics and Computers in Simulation
(2002) Some new results on simulated annealing applied to the job shop scheduling problem
European Journal of Operational Research
(1999)Sequencing rules and due-date assignments in job shop
Management Science
(1984)Simple priority rule combinations: An approach to improve both flow time and tardiness
International Journal of Production Research
(1997)- et al.
A state-of-the-art survey of dispatching rules for manufacturing job shop operations
International Journal of Production Research
(1982) Routing and scheduling in a flexible job shop by tabu search
Annals of Operations Research
(1993)- et al.
Complexity of scheduling problems with multi-purpose machines
Annals of Operations Research
(1997) - et al.
An algorithm for solving the job-shop problem
Management Science
(1999)
Recent trends in evolutionary multiobjective optimization
A fast and elitist multi-objective genetic algorithm: NSGA-II
IEEE Transaction on Evolutionary Computation
The complexity of flow shop and job-shop scheduling
Mathematics of Operations Research
Optimization and approximation in deterministic sequencing and scheduling: A survey
Annals of Discrete Mathematics
Practical approach to job-shop scheduling problems
IEEE Transactions on Robotics and Automation
Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling
IEEE Transactions on Evolutionary Computation
Deterministic job-shop scheduling: Past, present and future
European Journal of Operational Research
New dispatching rules for shop scheduling: A step forward
International Journal of Production Research
Cited by (353)
The flexible job shop scheduling problem: A review
2024, European Journal of Operational ResearchShared manufacturing-based distributed flexible job shop scheduling with supply-demand matching
2024, Computers and Industrial EngineeringKnowledge-transfer based genetic programming algorithm for multi-objective dynamic agile earth observation satellite scheduling problem
2024, Swarm and Evolutionary ComputationOptimizing flexible job shop scheduling with automated guided vehicles using a multi-strategy-driven genetic algorithm
2024, Egyptian Informatics JournalSurrogate model for memetic genetic programming with application to the one machine scheduling problem with time-varying capacity
2023, Expert Systems with ApplicationsQ-learning based multi-objective immune algorithm for fuzzy flexible job shop scheduling problem considering dynamic disruptions
2023, Swarm and Evolutionary Computation