IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 17, NO. 5, OCTOBER 2013 621
A Computational Study of Representations in
Genetic Programming to Evolve Dispatching Rules
for the Job Shop Scheduling Problem Su Nguyen, Mengjie Zhang, Senior Member, IEEE, Mark Johnston, Member, IEEE,
and Kay Chen Tan, Senior Member, IEEE
Abstract—Designing effective dispatching rules is an important factor for many manufacturing systems. However, this time- consuming process has been performed manually for a very long time. Recently, some machine learning approaches have been proposed to support this task. In this paper, we investigate the use of genetic programming for automatically discovering new dispatching rules for the single objective job shop scheduling problem (JSP). Different representations of the dispatching rules in the literature are newly proposed in this paper and are compared and analysed. Experimental results show that the representation that integrates system and machine attributes can improve the quality of the evolved rules. Analysis of the evolved rules also provides useful knowledge about how these rules can effectively solve JSP.
Index Terms—Dispatching rule, genetic programming, hyper-heuristic, job shop scheduling (JSP).
I. Introduction
IN THE FIELD of sequencing and scheduling, job shop scheduling is one of the most popular problems because of its complexity and applicability in real-world situations. In the job shop scheduling problem (JSP), given a set of machines and a set of jobs with various predetermined routes through the machines, the objective is to find the schedule of jobs that minimizes certain criteria such as makespan, maximum lateness, total weighted tardiness, etc. Different approaches have been proposed to solve this problem and they can be classified into two main categories [1]: 1) theoretical studies of optimization methods that are usually restricted to static problems, and 2) experimental studies of heuristics or dis- patching rules to deal with both static and dynamic problems.
Manuscript received May 24, 2012; revised October 9, 2012; accepted October 20, 2012. Date of publication November 16, 2012; date of current version September 27, 2013. This work was supported in part by the Marsden Fund of the New Zealand Government under Grants VUW0806 and 12-VUW- 134 administrated by the Royal Society of New Zealand, and the University Research Fund, under Grant 200457/3230, at the Victoria University of Wellington.
S. Nguyen, M. Zhang, and M. Johnston are with the Evolution- ary Computation Research Group, Victoria University of Wellington, Wellington 6012, New Zealand (e-mail: nguyenphanbachsu@gmail.com; mengjie.zhang@ecs.vuw.ac.nz; mark.johnston@msor.vuw.ac.nz).
K. C. Tan is with the Department of Electrical and Computer En- gineering, National University of Singapore, 117576, Singapore (e-mail: eletankc@nus.edu.sg).
Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org.
Digital Object Identifier 10.1109/TEVC.2012.2227326
Although the dispatching rules do not guarantee to provide optimal solutions for the problems, they have been applied extensively in research and practice because of their simplicity and ability to cope with the dynamic environment. Different from optimization approaches that represent the scheduling solution in a very sophisticated way in order to employ specialized techniques to solve the scheduling problem, a dispatching rule provides a way to perform a scheduling task which is understandable to shop floor operators. Normally, a dispatching rule is considered a simple function that deter- mines the priorities of jobs in the queue of a machine and decides which one should be processed next. The popularity of the dispatching rule is derived from the fact that it can be easily modified when real-world aspects such as setup time, release time, or parallel machines are considered. Another aspect that makes dispatching rules attractive to both researchers and practitioners is that they do not have the scalability problems which are a big issue of almost all optimization methods. Moreover, effective dispatching rules can also be used to create good initial solutions for optimization methods.
Many studies have been done in order to discover new effective dispatching rules. One of the most straightforward ways to improve the performance of dispatching rules without affecting their simplicity is to use a combination of simple dispatching rules. Another way to employ different dispatching rules is to monitor the status of jobs in the system and make a change from one dispatching rule to another as planned. For example, FIFO/SPT will apply first-in-first-out (FIFO) when the jobs in the queue of the considered machine have been waiting for more than a specific time and shortest-processing- time (SPT) will be applied otherwise. This combination, even though very simple, can take advantage of each rule at proper decision making moments and is normally better than the application of a single dispatching rule. Another approach to improving the performance of dispatching rules is to create composite dispatching rules (CDR) [2], [3] which provide heuristic combinations of simple rules basically in the form of sophisticated human-made priority functions of various scheduling parameters (processing times, waiting times, etc.).
Although the combinations of different simple dispatching rules may create better rules, the task of developing such rules is complicated and time consuming. Recently, machine learning methods have been proposed to facilitate this task.
1089-778X
⃝c 2012 IEEE
622 IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 17, NO. 5, OCTOBER 2013
Some genetic programming (GP) methods [4]–[10] have been proposed to evolve dispatching rules. In these methods, the GP programs are used to calculate the priority of jobs in the queue of each machine and the job with highest priority will be processed first. The experimental results showed that the dispatching rules evolved by GP can outperform simple dispatching rules. Li and Olafsson [11] applied a data mining technique to discover new dispatching rules based on pro- duction data. Data engineering was also considered in their research in order to create more useful attributes besides the ones recorded as part of the raw production data. The results show that the discovered decision rules can accurately replicate the dispatching list obtained by specific rules. Ingimundar- dottir and Runarsson [12] proposed a supervised learning approach that tries to discover new dispatching rules using the characteristics of optimal solutions. The learned linear priority dispatching rules showed better results than simple rules.
With its ability to evolve sophisticated rules and flexible representations, GP is a very promising method for auto- matically generating dispatching rules for the JSP. Moreover, if properly implemented, GP can evolve effective reusable rules to solve the JSP. This feature makes GP more attrac- tive than other evolutionary computation and meta-heuristic methods where only a disposable solution is obtained for each problem instance. One of the key factors that can enhance the performance of dispatching rules is the incorporation of machines and shop status into the rules in order to make more informative sequencing decisions. Miyashita [8] pro- posed three models to evolve dispatching rules with GP and showed that the two models which evolved different dedicated dispatching rules for different machines in the shop are better than the model which only employed a common dispatching rule for all machines. One of the drawbacks with this method is that evolving different dedicated dispatching rules would significantly increase the computational time of the proposed GP system and can also lead to overfitting problems [8]. Another disadvantage is that the representation in these models required the specific knowledge of the environment which can be changed in real situations. For that reason, it is very difficult to create more generalized and effective rules to deal with such a complicated problem as JSP. Jakobovic and Budin [6] proposed a more dynamic method to incorporate machine attributes into the evolved dispatching rules. Their proposed GP-3 system evolved three components, including two dis- patching rules and a discrimination function to determine which dispatching rule the considered machine should employ based on the attributes of that machine. The results showed that GP-3 was better than the GP method that only evolved dispatching rules. Unfortunately, no analysis or description of the evolved dispatching rules were provided in the paper. It should be noted that these existing studies emphasized not only the importance of machine attributes in the evolved rules but also the importance of how to embed these attributes into the evolved dispatching rules. Although some GP systems for evolving dispatching rules have been proposed, no detailed comparison and analysis of those representations have been done, which is an important issue in GP.
In this paper, we use GP to evolve adaptive dispatching rules (ADR) for the static JSP with makespan and total weighted tardiness as objective functions. Basically, an ADR is a combination of different dispatching rules and it is adaptive because the master rule will choose a specific dispatching rule to sequence jobs in the queue based on the status of the machines at each decision making step. Three representations of dispatching rules are proposed and tested with the GP system. The objectives of this paper are to: 1) investigate the performance of the GP system with different types of representations; 2) compare the performance of the evolved rules with well-known dispatching rules both on the training set and test set; and 3) analyze the performance of the proposed algorithm as well as the evolved rules and compare evolved rules with improvement heuristics.
The remainder of this paper is organized as follows. In the next section, the background of JSP and heuristic gen- eration methods is given. Section III will provide a detailed description of the proposed method. The experimental setting is presented in Section IV and the results will be shown in Section V. Some insights regarding the proposed method and the evolved rules will be discussed further in Section VI. Section VII offers some conclusions and future research directions.
II. Background
This section provides a brief review of JSP and hyper- heuristic (HH) methods for heuristic generation which pro- vides essential background for later sections.
A. Job Shop Scheduling Problem
This paper concentrates on minimization of the makespan
and total weighted tardiness, known as Jm||C
and Jm|| wjTj in the JSP literature. In this case, the shop includes a set of M machines and N jobs that need to be scheduled. Each job j has its own predetermined route through a sequence of machines to follow and its own processing time at each machine it visits. In this paper, jobs are only allowed to visit a machine at most once; and therefore no recirculation can occur. Some basic definitions and notations are presented
max
1) Oj = {oj,1,…,oj,l,…,oj,Nj }: the set of all operations of job j where oj,l, is the lth operation of job j and Nj is the number of operations of job j;
2) wj: the weight given to job j in the weighted tardiness objective function;
3) dj: the due date assigned to job j;
4) p(σ): the processing time of operation σ;
5) m(σ): the machine that processes operation σ;
6) next(σ): the next operation of the job that contains σ or
null if σ is the last operation of that job (if σ = oj,l then
next(σ) = oj,l+1). Variables:
1) Rk: the ready time of machine k, which is the time that the machine becomes idle; in this paper, all machines are idle at the beginning;
below that will be used in the rest of this paper.
Parameters:
NGUYEN et al.: STUDY IN GENETIC PROGRAMMING TO EVOLVE DISPATCHING RULES 623
Fig. 1. 2)
3) 4)
Generic procedure to construct a schedule for JSP.
r(σ): the ready time of operation σ, which is the release time of job j (the time that job j is allowed to start, considered to be zero in all instances in the experiments) for the first operation or the completion time of its preceeding operation for other operations;
Tj: the tardiness of job j and Tj = max(Cj −dj,0). The
total weighted tardiness is w T . jj
2) Job Shop Scheduling Techniques: Over the last few decades, a large number of techniques have been applied to JSP, ranging from simple heuristics to artificial intelligence and mathematical techniques [14]. Because of the complexity of JSP, finding optimal solutions can be very time-consuming, particularly for large and complex shops. The research on meta-heuristics approaches for scheduling has been very active in the last two decades, mostly with makespan as the objective function, i.e., Jm||Cmax. Local search based approaches such as large step optimization [15], tabu search [16], and guided local search [17] have shown very promising results in solving the static JSP. The focus of these approaches is on the devel- opment of efficient neighborhood structures and diversifying strategies to escape from local optima. Since neighborhood structures play an important role in these approaches, the neighborhood structures and their related operators have to be redesigned in order to incorporate real-world constraints; even then it is still questionable whether they produce superior results.
A more general alternative for solving JSP is the use of
evolutionary computation methods. Genetic algorithm (GA) is
one of the most popular approaches in this line of research
(refer to [18] for a review of GA approaches for JSP).
Besides Jm||Cmax, research on other objective functions has
also been considered in the literature, especially due date
related objectives due to the need to improve the delivery per-
Cj: the completion time of job j. Makespan Cmax = max(C ,…,C );
1N
1)
schedule is called active if it cannot be altered to make some operations complete earlier without delaying the completion time of other operations. Active schedules were first proposed by Giffler and Thompson [13] in their seminal work and it has been proven that an optimal solution to JSP must be an active schedule. Schedules where no machine is allowed to be idle when there are jobs in the queue are called nondelay schedules. A nondelay schedule is more restricted than an active schedule and the set of nondelay solutions may not include the optimal solution. Nondelay schedules are often applied in experiments using simulation since a machine will immediately process all jobs in its queue in the order determined by a specific sequencing rule.
Fig. 1 shows a generic procedure to construct an active schedule, a nondelay schedule or a hybrid of both active and nondelay schedules. In this procedure, contains all the operations that are ready to be scheduled. The procedure will first determine the next operation that would complete first if scheduled and the corresponding machine m∗ (ties are broken arbitrarily). The nondelay factor α ∈ [0,1] controls the look ahead ability of the algorithm and decides which jobs should be considered by the dispatching rule . If α = 0, the procedure can only construct nondelay schedules and only operations that have already joined the queue are considered for scheduling. On the other hand, if α = 1, the procedure will consider all the potential jobs that are ready to join the queue of machine m∗ before the earliest completion time of m∗. In general, α determines the interval of time that a machine is allowed to wait even when there are operations in the queue. As a result, there are fewer operations to be considered in each step of the algorithm when α is small.
formance in modern manufacturing systems. For Jm|| wj Tj , several methods have been proposed in the literature and shown promising results. For example, Kreipl [19] proposed an efficient large step random walk (LSRW) method, which is still one of the best local search methods to deal with Jm|| wj Tj . Zhou et al. [20] introduced a general framework using a genetic algorithm and heuristic rules to solve a similar problem and showed that it is better than the pure genetic algorithm. Even though the proposed hybrid GA provides solutions that are inferior to those obtained by LSRW [19], it is still very promising since it is capable of solving a variety of scheduling problems without major redesign.
Although there have been many breakthroughs in the de- velopments of exact and approximate approaches for JSP, these approaches are mainly focused on static problems and simplified job shop environments. General approaches like GA can be extended to solve problems with realistic con- straints, but the major drawback is its weak computational efficiency. Moreover, as pointed out by McKay et al. [21], the conventional operational research and artificial intelligence approaches are often not applicable to the dynamic charac- teristics of the actual situation because these approaches are fundamentally based on static assumptions. For that reason, simple dispatching rules have been used consistently in prac- tice because of their ability to cope with the dynamics of shop changes [22]. There have been a large number of rules proposed in the literature and they can be classified into three categories [14]: 1) simple priority rules, which are mainly based on the information related to the jobs; 2) combinations of rules that are implemented depending on the situation that exists on the shop floor; and 3) weighted priority indices that employ more than one piece of information about each job to
Active Schedules and Nondelay Schedules: In JSP, a
624 IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 17, NO. 5, OCTOBER 2013
determine the schedule. Composite dispatching rules (CDR) [2], [3] can also be considered a version of rules based on weighted priority indices, where scheduling information can be combined in more sophisticated ways instead of linear combinations.
B. Hyper-Heuristics for Heuristic Generation
Hyper-heuristics are a new search method and have attracted a lot of attention from the research community. A HH is an automated methodology for selecting or generating heuristics to solve hard computational search problems [23]. Heuristic selection and heuristic generation are currently the two main research methodologies in HH [24]. The focus of this paper is on HH for heuristic generation. In order to generate a new heuristic, the HH framework must be able to combine various small components, normally common statistics or operators used in preexisting heuristics, and these heuristics are trained on a training set and evolved to become more effective.
1) Genetic Programming Based Hyper-Heuristics (GP- HH): Recently, GP has become popular in the field of HH and it is known as genetic programming based hyper-heuristics (GP-HH) [25]. Because GP is able to represent and evolve complex programs or rules, it naturally becomes an excellent candidate for heuristic generation. Bolte and Thonemann [26] proposed a GP system to evolve annealing schedule functions in simulated annealing to solve the quadratic assignment prob- lem (QAP). The experimental results showed that the method with GP as a meta-algorithm can find near optimal solutions for QAP. Fukunaga [27] used GP to evolve variable selection heuristics in each application of a local search algorithm for the satisfiability (SAT) problem and showed competi- tive results when compared with other heuristics. Bader-El- Den and Poli [28] also employed GP to evolve disposable local search heuristics to solve SAT for a specific set of instances and the evolved heuristics show very competitive results as compared to other well-known evolutionary or local search heuristics. Burke et al. [29], [30] proposed a GP-HH framework to evolve construction heuristics for online bin packing. The basic idea of this GP system is to generate a priority function from static and dynamic statistics of the problem to decide where the considered pieces should be placed. The experimental results showed that human designed heuristics can be obtained by GP. A similar idea was also applied to evolve 2-D strip packing heuristics and showed very good results [31]. Keller and Poli [32], [33] proposed a grammar-based linear GP method to solve the traveling salesman problem. Several grammars are introduced, includ- ing ones with a looping construct. Bader-El-Den et al. [34] introduced a sophisticated grammar-based GP for evolving timetabling heuristics. The evolved heuristics were able to produce competitive results when compared with some ex- isting search methods in the literature. Burke et al. [35] proposed a grammatical evolution method for automatic design of local search heuristics for cutting and packing problems. The experimental results showed the competitiveness of the evolved local search heuristics.
2) GP-HH for Scheduling Problems: Dimopoulos and Zalzala [36] used GP to evolve reusable dispatching rules for
the one-machine scheduling problem with a standard function set and a terminal set of scheduling statistics (processing time, release time, due date, number of jobs, etc.). The evolved dispatching rules were found to be better than traditional rules and these rules can be reused for a range of unseen problem instances. The best evolved rules were also examined and the analysis showed that these rules are interpretable. Jakobovic et al. [37] employed the same method for devel- oping dispatching rules for the parallel machine scheduling problem in both static and dynamic environments. However, the evolved rules obtained from these studies have not consid- ered the effects of different representations on the performance of the GP system and the machine and system attributes were not included in the evolved rules. Also, trying to learn new dispatching rules for the single machine environment, Geiger et al. [38] presented a learning system that combines GP with a simulation model of an industrial facility. The proposed GP system is used to create the priority rule for a single machine in static and dynamic environments. The terminal set of GP includes system attributes, job attributes, and machine attributes, and the function set consists of basic operators. The paper also proposed a method to learn dispatching rules for multiple machine problems in which GP will evolve multiple trees simultaneously with modified crossover and mutation operators. Comparison with the optimal rule in a simple two machine environment showed that the evolved rules are quite competitive. However, the use of an independent dispatching rule for each machine may rapidly increase the complexity of the scheduling systems and make it difficult to generate generalized rules for large manufacturing systems. Geiger and Uzsoy [39] also applied this system for learning dispatching rules for batch processor scheduling, with very promising results. For a stochastic single machine scheduling problem, Yin et al. [40] proposed a GP system employing a bi-tree struc- tured representation scheme to deal with machine breakdowns. The empirical results under different stochastic environments showed that GP can evolve high quality predictive scheduling heuristics.
Miyashita [8] developed an automatic method using GP to design customized dispatching rules for a job shop environ- ment and viewed JSP as a model of a multiagent problem where each agent represents a resource (machine or work station). Three multiagent models are proposed: 1) a homoge- neous model where all resources share the same dispatching rule; 2) a distinct agent model where each resource employs its own evolved rule; and 3) a mixed agent model where two rules can be selected to prioritize jobs depending on whether the resource is a bottleneck or not. Although the multiagent models perform better, the use of these models depends on the some prior-knowledge of the job shop environment, which can be changed in dynamic situations. A similar system was also proposed by Atlan et al. [41] but the focus of their paper is on finding the solution for a particular problem instance. Jakobovic and Budin [6] applied GP to evolve dispatching rules for both single machine and job shop environments. The results for the single machine environment are shown to be better than existing rules. For the job shop environment, a meta-algorithm is defined to show how the evolved rules
NGUYEN et al.: STUDY IN GENETIC PROGRAMMING TO EVOLVE DISPATCHING RULES 625
are used to construct a schedule. This paper also proposed an interesting way to provide some adaptive behaviors for the evolved rules. They proposed a GP-3 system that evolves three components, a discriminant function and two dispatching rules. The discriminant function aims at identifying whether the considered machine to be scheduled is a bottleneck or not. This function serves as the classifier in binary classification problems. Based on the classification decision obtained from the discriminant function, one of two dispatching rules will be selected to sequence jobs in the queue of that machine. Even though the purpose of the discriminant function in this case is to identify the bottleneck machine, there is no guarantee that the classification can help indicate the bottleneck machine or just some useful attributes of the shop or machines. The results show that the GP-3 system performed better than traditional GP with a single tree. Unfortunately, no demonstrations or analyses of the evolved rules are given. Tay and Ho [5] pro- posed a GP system to evolve dispatching rules for a job shop environment. The proposed GP program can be considered as a priority function which is used to calculate the priority of operations in the queue of a machine. The set of instances was randomly generated and it was shown that the evolved dispatching rules can outperform other simple dispatching rules. However, they did not consider the use of machine attributes in the priority function. Hildebrandt et al. [7] re-examined the GP system proposed in [5] in different dy- namic job shop scenarios and showed that rules evolved by Tay and Ho [5] are only slightly better than the earliest release date (ERD) rule and quite far away from the performance of the SPT rule. They explained that the poor performance of these rules is caused by using the linear combination of different objectives and the fact that the randomly generated instances cannot effectively represent the situations that happened in a long term simulation. For that reason, Hildebrandt et al. [7] evolved dispatching rules by training them on four simulation scenarios (10 machines with two utilization levels and two job types) and only aimed at minimising the mean flow time. Some aspects of the simulation models were also discussed in their study. The experimental results indicated that the evolved rules were quite complicated but effective when compared to other existing rules. Moreover, these evolved rules are also robust when tested with another environment (50 machines and different processing time distributions). Pickardt et al. [42] applied this system to evolve dispatching rules for semiconductor manufacturing to minimize weighted tardiness. Vazquez-Rodriguez and Ochoa [43] proposed a GP system to learn variants of the Nawaz, En-score, and Ham (NEH) procedure for flow shop scheduling. The results showed that the evolved heuristics can outperform the original and stochastic variants of NEH.
Other methods have also been proposed for generating new dispatching rules. Li and Olafsson [11] applied data mining techniques on production data to generate dispatching rules. For further improvement, the authors used data engineering to create more useful attributes besides ones recorded as part of the raw production data. The results show that the decision rules discovered can accurately replicate the dispatching list obtained by specific rules. However, since the rules are learned
from the historical records of the production system, it is difficult to generate new dispatching rules and the performance of the evolved rules may only be as good as the actual rules. Most recently, Ingimundardottir and Runarsson [12] proposed a supervised learning approach that tries to discover new dispatching rules using the characteristics of optimal solutions. The learned linear priority dispatching rules showed better results than simple rules. One of the drawbacks is that the proposed supervised learning approach tries to learn from the optimal solutions which are not available in many cases.
Dispatching rules have been a very practical tool for scheduling in real world situations. However, manual design of new dispatching rules is still a very time consuming process. Several machine learning methods have been proposed to ease this task. GP is one of the most popular methods because of its flexibility which helps it easily cope with different problem environments. Since the design process is automated by GP, not only priority functions but also complicated issues such as incorporating machine and system attributes can be considered in order to improve the effectiveness of evolved rules. However, the existing GP systems mainly focus only on evolving priority functions. Also, bottleneck was the only system attribute used in the previous studies [6], [8]. In this paper, we propose two new representations for GP that evolve rules with the ability to incorporate different machine and system attributes to make better sequencing decisions. A comparison between the proposed rules and the arithmetic representation used in previous studies is also presented. This paper also examines other important issues, such as the influence of fitness functions and analysis of evolved rules, to gain more understanding of how GP can evolve effective dispatching rules.
III. Methodology
This section discusses a new GP system that is able to learn new dispatching rules which can adaptively sequence operations in the queue based on the status of the shop and the machines to be scheduled. In this section, the representations of a dispatching rule are presented first, followed by the fitness function used to measure the performance of an evolved dispatching rule.
A. Representations
Three representations of dispatching rules are considered in this paper. The first representation (R1) provides a way to incorporate machine attributes into the GP program along with simple dispatching rules and the hybrid scheduling strategy between nondelay and active scheduling. The second repre- sentation (R2) is the traditional arithmetic representation like that employed in [5]; the purpose of this representation is to generate composite dispatching rules. The last representation (R3) is a combination of R1 and R2, in which different composite dispatching rules exist and are logically applied to JSP based on the machine and system attributes.
1) Decision-Tree Like Representation (R1): The key idea of this representation is to provide the adaptive dispatching rules the ability to apply different simple dispatching rules
626
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 17, NO. 5, OCTOBER 2013
Fig. 2.
Grammar for the proposed GP system with R1.
cessing time of all operations in ′ that have to visit m∗. 3) Deviation of jobs, DJ = minσ∈′ {p(σ)} : this is a simple
total remaining processing time σ∈I p(σ) and amachine is called bottleneck if it has the largest workload σ∈′ p(σ) in ′. The following definitions of the machine and system attributes are used in this paper.
σ∈
1) Workload ratio, WR = ′ p(σ) : this indicates the work-
′ σ∈I p(σ)
load in compared to the total remaining workload that
m∗ has to process (including the operations in the queue
and operations that have notyet visited m∗).
2) Machine progress, MP = σ∈K p(σ) : this indicates the
∗ σ∈ p(σ)
progress of m , calculated as the ratio of the total
processing time that m∗ has processed to the total pro-
maxσ∈′ {p(σ)}
ratio of minimum processing time to the maximum
processing time of operations in ′.
4) Critical machine idleness, CMI: this is the workload
ratio WR of the critical machine.
5) Critical workload ratio, CWR = c p(σ ) : this is
the ratio of the workload of operations in c to the workload in ′ where c ⊂ ′ is the set of operations belonging to the jobs that have operations that still need to be processed at the critical machine after being processed at m∗.
6) Bottleneck workload ratio, BWR = σ ∈b p(σ ) : this is σ∈′ p(σ)
the ratio of the workload of operations in b to the workload in ′ where b ⊂ ′ is the set of operations belonging to the jobs that have operations that still need to be processed at the bottleneck machine after being processed at m∗.
While the first three attributes provide the local status at m∗, the last three attributes indicate the status of the shop with a special focus on the critical and bottleneck machines. The machine and system attributes here appear in the scheduling literature in different forms. The key difference between our attributes and the attributes used in other studies is that our at- tributes have been scaled from 0 to 1. The scaled (normalized) attribute values aim to enhance the generality of the evolved rules and also make the evolved rules easier to understand. Jakobovic and Budin [6] employed attributes similar to ours without normalization (e.g. remaining work at the machine is similar to workload ratio in this paper). The definition of attributes for bottleneck and critical machines are adapted from the bottleneck concept [46] for static problems and these attributes are used to adjust the rules to react appropriately to the changes of the shop.
For representation R1, eleven simple dispatching rules are considered as the candidate rules in the ADR. The aim of these rules is to determine which operation σ in ′ will be processed next. Let n(σ) be the job which operation σ belongs to, j = n(σ) and oj,h = σ. The following are brief descriptions of the candidate dispatching rules. Detailed discussion of these rules can be found in [1] and [47].
1) FIFO: operations are sequenced first-in-first-out.
2) SPT: select the operation with the shortest processing
time p(σ ).
3) LPT: select the operation with the longest processing
time p(σ ).
σ∈
σ∈′ p(σ
Fig. 3.
α = 0.084. (b) If (WR ≤ 20%) then use SPT with α = 0.221 else use FIFO with α = 0.078.
based on machine attributes. In this case, the adaptive dis- patching rules are represented in a decision-tree form. To make the rules more readable and explainable, the proposed grammar in Fig. 2 is used when building the GP programs and performing the genetic operators (e.g., dispatching nodes must contain two arguments, which are a value of the nondelay factor and a single dispatching rule). Two example rules based on this grammar are shown in Fig. 3. In Fig. 3(a), the rule is similar to that of SPT which is applied with the nondelay factor α = 0.084. The rule in Fig. 3(b) is a bit more sophisticated. The rule firstly checks the workload ratio WR (the ratio of the total processing times of jobs in the queue to the total processing times of all jobs that have to be processed at the machine) of the considered machine m∗; if the workload ratio is less than or equal to 20%, dispatching rule SPT is applied with α = 0.221; otherwise, dispatching rule FIFO is applied with α = 0.078. This ADR can be considered as a variant of FIFO/SPT, in which the workload of the machine is used as the switch instead of the waiting times of jobs in the queue. Different from other applications [44], [45] where a single nondelay factor is evolved, the proposed GP system using this representation allows different values of nondelay factors to be employed based on the status of the shop.
In this paper, we will consider six attributes that indicate the status of machines in the shop. Let be the set of operations that are planned to visit the considered machine m∗, and K and I are the sets of all operations that have and have not yet been processed by m∗, respectively ( = K ∪ I). In the shop, we call a machine critical if it has the greatest
Example program trees based on representation R1. (a) SPT with
NGUYEN et al.: STUDY IN GENETIC PROGRAMMING TO EVOLVE DISPATCHING RULES
627
TABLE I
Terminal Set for R2 (j = n(σ) and oj,h = σ)
Notation RJ
RO
RT PR W DD RM #
Description
Operation ready time
Number of remaining operations of job j
Work remaining of job j Operation processing time Weight
Due date
Machine ready time Constant
Value
r(σ) Nj−h+1
Nj p(oj,l ) l=h
p(σ ) wj
dj
Rm∗ Uniform[0, 1]
Example program trees based on representation R2. (a) W%PR. (b)
Fig. 4.
(RT + RM) − DD.
4) LSO: select the operation belonging to the job that has the longest subsequent operation p(next(σ)).
5) LRM: select the operation belonging to the job that has
the longest remaining processing time (excluding the
operation under consideration) Nj p(o ). l=h+1 j,l
the smallest work remaining Nj p(o ).
l=h j,l
6) MWKR: select the operation belonging to the job that has the most work remaining Nj p(o ).
l=h j,l
7) SWKR:selecttheoperationbelongingtothejobthathas
Fig. 5.
Example program tree based on representation R3.
8) MOPR:selecttheoperationbelongingtothejobthathas the largest number of operations remaining Nj − h + 1.
9) EDD: select the operation belonging to the job that has
the earliest due date dj.
10) MS: select the operation belonging to the job that has
the minimum slack MS = d − Nj p(o )−t. Value j j l=h j,l
t = Rm∗ is the time at which the sequencing decision
needs to be made.
11) WSPT: select the operation that has the maximum
weighted shortest processing time wj/p(σ).
The nondelay factor is treated as Ephemeral Random Con- stants (ERC) [48]. The values of the nondelay factor will initially be a random number from 0 to 1. Meanwhile, attribute type, attribute threshold and dispatching rule terminals are randomly chosen from their candidate values as described in
the previous section with equal probabilities.
2) Arithmetic Representation (R2): For this representation,
the focus is to formulate composite dispatching rules that in- clude different pieces of information from jobs and machines. Basically, the GP programs are priority functions that can be used to calculate the priorities for operations in ′ and the operation with the highest priority will be scheduled to be processed next on the machine m∗. Different from R1 rules that become more effective by logical choices of single dispatching rules, R2 rules create their sophisticated behavior arithmeti- cally combining various terms into the priority functions. The advantage of this representation is that more information can be directly considered to determine the priorities of operations when sequencing decisions need to be made.
In our GP system, the four basic arithmetic operators (+,−,∗, protected division %) are used in the function set. Since we evolve a function to prioritize operations, it seems useful to include a single-argument function (−1∗) in the function set to provide a more convenient way to create priority functions. The terminal set contains popular terms that are used in developing existing dispatching rules. The
descriptions of the terminals used for calculating the priority of operation σ are shown in Table I. Fig. 4 shows two simple examples when WSPT and MS are represented by R2 rules. The nondelay scheduling strategy will be used along with this representation like common applications of composite dispatching rules.
3) Mixed Representation (R3): This representation tries to combine the advantages of R1 and R2 to create sophisticated adaptive dispatching rules. Within R3, the incorporation of both system/machine status and composite dispatching rules are considered. The representation R3 inherits the grammar in R1 and the composite dispatching rules will be used to calculate the priorities of operations for sequencing decisions besides the use of simple dispatching rules. An example of an R3 rule is shown in Fig. 5.
B. Fitness Evaluation
The focus of this paper is to learn effective rules for JSP to minimize the makespan or total weighted tardiness. In order to estimate the effectiveness of an evolved dispatching rule, it will be applied within the construction procedure in Fig. 1 to solve a set of instances in the training set and the resulting objective values from all instances are recorded. Since the objective values obtained by a dispatching rule for each instance are very different, we will measure the quality of an obtained schedule by the relative deviation of its objective value from its corresponding reference objective value as shown in (1)
Obj(,In)−Ref(In)
dev(,In) = Ref(In) . (1)
In this equation, Obj(,In) is the objective value obtained when applying rule to instance In , and Ref (In ) is the reference objective value for instance In. The fitness of rule on the training set is calculated by (2). The fitness function devaverage() will measure the average performance of
628
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 17, NO. 5, OCTOBER 2013
Population Size Crossover rate Mutation rate Reproduction rate Generations Max-depth Function set Terminal set
Function set Terminal set Function set Terminal set Fitness
1024
95%, 90%, 85%
0%, 5%, 10%
5%
50
6
If, Dispatch, ≤,>
attribute type, attribute threshold, nondelay factor, dispatching rule
+, −, ∗, %, (−1∗)
as shown in Table I
Function set (R1 ) and Function set (R2 ) Terminal set (R1 ) and Terminal set (R2 ) devaverage ()
TABLE II
Parameters of the Proposed GP System
(R1 ) (R1 )
Fig. 6.
across T instances in the data set
system will apply genetic operators such as reproduction (elitism), crossover, and mutation to the programs in the current population to generate new individuals for the next generation. More details of the genetic operators used in this paper will be provided in the next section. When the maximum number of generations is reached, the GP algorithm will stop and return the best found rule ∗, which will be applied to the test set to evaluate the performance of the GP system.
IV. Design of Experiments
This section discusses the configuration of the GP system and the data sets used for training and testing.
A. Parameter Setting
The GP system for learning ADRs is developed based on the ECJ20 library [50], a Java-based evolutionary computation research system. The parameter settings of the GP system used in the rest of this paper are shown in Table II. The population size of 1024 is used to ensure that there is enough diversity in the population. The initial GP population is created using the ramped-half-and-half method [48]. Since the rules are created based on the grammar in Fig. 2, we use strongly typed GP to ensure that the GP nodes will provide proper return types as determined by the grammar. In this case, the crossover and mutation operators of GP are only allowed if they do not violate the grammar. For crossover, the GP system uses the subtree crossover [48], which creates new individuals for the next generation by randomly recombining subtrees from two selected parents. Meanwhile, mutation is performed by subtree mutation [48], which randomly selects a node of a chosen individual and replaces the subtree rooted by that node by a newly randomly generated subtree. The combinations of three levels of crossover rates and mutation rates will be tested in our experiments to examine the influence of these genetic operators on the performance of GP. When generating random initial programs or applying crossover/mutation, the maximum depth of six is used to restrict the program from becoming too large. Greater maximum depths can also be used here to extend the search space of GP; however, we choose this maximum depth to reduce the computational times of the GP system and
GP algorithm to evolve dispatching rules for JSP.
devaverage() = In∈{I1,…,IT } dev(,In). T
(2)
(R2 ) (R2 ) (R3 ) (R3 )
The objective of the GP system is to minimize this fitness function. In the case of Jm||Cmax, the reference objective value is the lower bound obtained by other approaches (refer to [49] for a list of lower bound values obtained for popular benchmark instances). Since lower bounds are used in this case, the fitness values for the GP programs are always nonnegative. If the fitness value is close to zero, it indicates that the evolved rules can provide near optimal solutions. For Jm|| wjTj, because the lower bound values are not available for all instances, we will use objective values obtained by EDD using nondelay scheduling as the reference objective values for all instances in the data set since it is a widely used dispatching rule for due date related problems. Because EDD is just a simple rule, it can be dominated by more sophisticated rules.For that reason, the fitness value of the GP programs for Jm|| wjTj can be negative, which means that the evolved rules perform better than EDD with a given fitness function.
C. Proposed GP Algorithm
Fig. 6 shows the GP algorithm used in this paper to evolve dispatching rules for JSP. The GP system first sets up the training set D and randomly initializes the population. At a generation, each dispatching rule or individual i will be applied to solve all instances in the training set D to find the relative deviation dev(i , In ) for each instance. Then, the fitness value of each rule is calculated by using devaverage (i ). If the evaluated rule is better and has smaller fitness value than the best rule ∗, it will be assigned to the best rule ∗ and the best fitness value fitness(∗) is also updated. After all individuals in the population are evaluated, the GP
NGUYEN et al.: STUDY IN GENETIC PROGRAMMING TO EVOLVE DISPATCHING RULES
629
Data Set LA ORB TA DMU
Notation la01-la40 orb01-orb10 ta01-ta80 dmu01-dmu80
No. of Instances 40
10
80
80
Problem Size (N × M) From 10 × 5 to 15 × 15 10 × 10
From 15 × 15 to 100 × 20 From 20 × 15 to 50 × 20
Reference Lawrence [51] Applegate and Cook [52] Taillard [53] Demirkol et al. [54]
make the evolved rules easier to analyse. Tournament selection with the tournament size of seven is used to select individuals for genetic operations.
B. Data Sets
There are many data sets in the JSP literature that are
generated by different scheduling researchers [51]–[54] to
measure the performance of different heuristic and optimiza-
tion methods. The instances in these data sets are still very
useful because they include a wide range of instances with
different levels of difficulty. Moreover, lower bounds for these
instances are available and can be used to calculate the fitness
of the evolved dispatching rules as described in Section III-B.
Descriptions of the data sets used for the experiments are
shown in Table III. In this paper, we combine these data sets
and distribute them into the training set and test set used by the
proposed GP system. The training set and test set are created
to include halves of the instances of each individual data set
in Table III. In particular, the training set will contain {la01,
la03, . . . , la39}, {orb01, . . . , orb09}, { ta01, . . . , ta79},
{dmu01, . . . , dmu79}. The other even index instances will
be included in the test set. This allows a fair distribution of
problems with different instance sizes into both training set
values of JSP. In total, we need 3 × 3 × 2 = 18 experiments. For each experiment, 30 independent runs are performed with different random seeds. Tables IV and V-A show the means and standard deviations of fitness values of the best evolved rules from each run obtained from all experiments on the training set and test set. The triple ⟨c,m,r⟩ indicates the GP parameters used in a specific experiment. For example, ⟨85, 10, 5⟩ represents the experiment where the crossover rate is 85%, the mutation rate is 10% and the reproduction rate is 5%. All statistical tests discussed in this section are the standard z-tests and they are considered significant if the obtained p-value is less than 0.05.1
A. Makespan
As shown in Table IV, the evolved rules based on R1
show a performance close to those obtained by R2 and R3
on the training set. It is also noted that the R1 rules evolved
with higher mutation rates are significantly better than those
evolved without lower mutation (all p-values < 0.0174)
on the training set. Since R1 rules contain many possible
terminals higher mutation rates seem quite useful to improve
the performance of the GP system with the R1 representation.
However, the performance of R1 rules are quite poor on the
test set. This indicates the overfitting issue of R rules when 1
learning with the training set. The reason for this problem comes from the fact that the candidate rules used in R1 are too simple, and therefore the rules have to depend strongly on the machine and system status to provide better sequencing decisions on the training instances. However, the overuse of the machine and system attributes make R1 rules less effective when dealing with unseen instances in the test set.
Evolved R2 rules show a more consistent performance on both the training set and test set. Different from R1, the statistical tests indicate that the choice of GP parameters does not have significant influence (all p-values > 0.1434) when R2 is used as the representation of the dispatching rule. These results indicate that mutation is not really useful in this case and the crossover operator is sufficient for the GP system to evolve good individuals. Since R2 provides only one way to sequence operations, the effectiveness is obtained by good combinations of different terms. Hence, they are also less affected when working with unseen instances like R1 rules.
Taking the advantages of R1 and R2, the evolved R3 rules show very promising performance. Different from R1, the incorporation of the machine and system attributes into the R3 rules are supported by better composite dispatching rules,
1Wilcoxon tests are also performed and the results from these tests are consistent with those obtained z-tests.
and test set. There are 105 instances in each of the training
set and test set. For the case of Jm||w T , the due dates jj
for jobs in each instance will be generated (following Baker [55]) by a due date assignment rule
Nj dj=rj+h× p(oj,l).
l=1
(3)
The parameter h is used to indicate the tightness of due dates. We choose h = 1.3 for all instances in the training set and test set because it is the common value used in previous research [19], [20]. For the weights of jobs, we employ the 4 : 2 : 1 rule which has been used in [19] and [20]. This rule is inspired by Pinedo and Singer [56] when their research showed that 20% of the customers are very important, 60% are of average importance and the remaining 20% are of less importance. For that reason, in Jm|| wjTj, the weights of 4 are assigned to the first 20% of jobs, the next 60% are assigned a weight of 2 and the last 20% of jobs are assigned a weight of 1.
V. Results
The proposed GP systems with different settings are now applied to evolve new dispatching rules. This section shows the results obtained from the GP system with three representations, three levels of crossover/mutation rates, and two objective
TABLE III
JSP Data Sets
630
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 17, NO. 5, OCTOBER 2013 TABLE IV
Performance of Evolved Rules for Jm||Cmax on Training Set and Test Set with Different Settings (mean ± standard deviation)
Setting devaverage ()
R1 R2 R3
⟨95, 0, 5⟩
Training 0.188 ± 0.008 0.181 ± 0.003 0.180 ± 0.003
Testing 0.197 ± 0.007 0.192 ± 0.005 0.191 ± 0.006
Training 0.181 ± 0.003 0.181 ± 0.003 0.180 ± 0.003
Testing 0.187 ± 0.004 0.188 ± 0.005 0.188 ± 0.004
Training 0.183 ± 0.005 0.181 ± 0.005 0.179 ± 0.005
Testing 0.186 ± 0.005 0.184 ± 0.006 0.184 ± 0.004
⟨90, 5, 5⟩ ⟨85, 10, 5⟩
TABLE V
Relative Deviations Obtained by Evolved Rules and Other Rules for Jm||Cmax
Rules
Training Set
Min Mean Max 0.012 0.325 0.691 0.012 0.325 0.691 0.322 0.694 1.252 0.029 0.292 0.576 0.020 0.321 0.745 0.000 0.224 0.556 0.047 0.323 0.736 0.000 0.253 0.590 0.000 0.173 0.448 0.000 0.174 0.428 0.000 0.174 0.479 0.000 0.175 0.457 0.000 0.171 0.490 0.000 0.172 0.447
Test Set Min Mean 0.000 0.325 0.000 0.325 0.316 0.711 0.092 0.312 0.000 0.319 0.000 0.225 0.000 0.328 0.000 0.254 0.000 0.192 0.000 0.183 0.000 0.190 0.000 0.191 0.000 0.185 0.000 0.177
Max 0.654 0.654 1.091 0.664 0.723 0.529 0.713 0.584 0.525
0.479 0.442 0.446 0.572 0.428
FIFO SPT LRM MWKR
Evolved
Active
Nondelay
Active
Nondelay
Active
Nondelay
Active
Nondelay
c1 R1 c2 R1 c1 R2 c2 R2 c1 R3 c2 R3
and therefore they do not need to depend heavily on the use of machine and system attributes to be effective. The performance on the test set shows that the evolved R3 rules also have good generalization qualities like that of the R2 rules. Mutation does not affect the GP system with R3 as strongly as the GP system with R1. The significant difference is only observed between the experiment with no mutation and the experiment with the mutation rate of 10% (p-value < 0.0031). Although there is no obvious difference in the performance of evolved rules from different configurations on the training set, R2 rules and R3 rules evolved with nonzero mutation rate are significantly better than R1 rules on the test set (all p-values < 0.0361 over (3 + 2) × 3 = 15 statistical tests). Also, the evolved R3 rules from the GP system with nonzero mutation rates are significantly better than R1 and R2 rules on the test set (all p-values < 0.014 over 2 × (3 + 3) = 12 statistical tests).
Table V shows the performance of the evolved rules with
four selected existing dispatching rules for Jm||Cmax. The
values in this table are the statistics of relative deviations using
(1) obtained when applying the evolved rules to the instances
in the training set and test set. The values of Mean can be
calculated by using (2) to measure the average while min and
max values show the best-case and worst-case performance
of a dispatching rule on a given set of instances. From each
representation, two evolved rules that show the best fitness in
Each simple dispatching rule is used to generate both active
and nondelay schedules for all instances in the training set and
test set. The results show that LRM with nondelay scheduling
strategy is better than other simple rules. The performance of
the evolved rules are better than all of the simple dispatching
rules on the training set and test set. However, not all evolved
rules can produce consistent results when dealing with unseen
the training stage are used here for comparison. Rule yv is
Rx 3
the vth best rule that was evolved by using the representation
Rx to minimize objective function y for the JSP. For example,
c2 is the second best rule evolved with the representation R R2 2
and Cmax as the objective function (t will be used to indicate the total weighted tardiness).
instances. Rules c2 and c2 are the rules that provide the R1 R3
best performance on the test set even though they are not the
best rules on the training set. Generally, it seems quite difficult
to develop a rule that produces good average and worst-case
performance. One explanation is that the rules evolved with
devaverage() focus on the overall performance, therefore they
may ignore some extreme cases. Evolved rule c2 is one R3
specific case when the best average performance and very good worst-case performance is achieved.
B. Total Weighted Tardiness
In Table V-A, the experiments with R3 as the representation can produce rules with better fitness than experiments with R1 or R2 as the representation. The statistical tests show that evolved R3 rules from the GP system with nonzero mutation rates are significantly better than other evolved R1 and R2 rules on both training set and test set (all p-values < 0.0009 over 2 × (3 + 3) × 2 = 24 statistical tests). These results again confirm the effectiveness of the R representation. Also, the R1 rules from the GP system with nonzero mutation rates are significantly better than R2 rules in this case (all p-values < 2 × 10−16 over 2 × 3 × 2 = 12 statistical tests). This suggests that the machine attributes and scheduling strategies are quite important when dealing with Jm|| wj Tj .
NGUYEN et al.: STUDY IN GENETIC PROGRAMMING TO EVOLVE DISPATCHING RULES 631 TABLE VI
Performance of Evolved Rules for Jm||wjTj on Training Set and Test Set With Different Settings (mean ± standard deviation)
Setting devaverage () ⟨90, 5, 5⟩
R1 R2 R3
⟨95, 0, 5⟩ ⟨85, 10, 5⟩
Training −0.227 ± 0.004 −0.235 ± 0.006 −0.237 ± 0.006
Testing −0.221 ± 0.005 −0.223 ± 0.003 −0.222 ± 0.003
Training −0.216 ± 0.003 −0.216 ± 0.004 −0.216 ± 0.004
TABLE VII
Testing −0.203 ± 0.005 −0.205 ± 0.006 −0.204 ± 0.006
Training −0.240 ± 0.015 −0.245 ± 0.012 −0.247 ± 0.013
Testing −0.233 ± 0.015 −0.233 ± 0.014 −0.235 ± 0.013
Negative values mean the evolved rules are better than EDD.
Relative Deviations Obtained by Evolved Rules and Other Rules for Jm|| wj Tj
Rules FIFO
LRM
MS
WSPT W(CR+SPT) W(S/RPT+SPT) COVERT
ATC
Evolved
Active
Nondelay
Active
Nondelay
Active
Nondelay
Active
Nondelay
Active
Nondelay
Active
Nondelay
Active
Nondelay
Active
Nondelay t1
R1 t2 R1 t1
R2 t2 R2 t1
R3 t2 R3
Training Set
Min Mean Max −0.318 0.455 1.600
−0.318 0.455 1.600 0.193 0.832 2.129 −0.189 0.507 1.571 0.106 0.601 1.519 −0.040 0.387 1.205 −0.133 0.148 0.874 −0.394 −0.169 0.168 −0.133 0.140 0.670 −0.398 −0.173 0.177 −0.110 0.149 0.867 −0.394 −0.168 0.168 −0.171 0.146 0.722 −0.394 −0.173 0.177 −0.258 0.145 0.757 −0.394 −0.168 0.168 −0.586 −0.247 0.020
−0.531 −0.244 0.003 −0.467 −0.223 −0.003 −0.529 −0.223 0.151 −0.506 −0.265 −0.033 −0.581 −0.265 −0.022
Test Set Min Mean −0.159 0.442 −0.159 0.442 −0.125 0.836 −0.236 0.494 0.035 0.607 −0.133 0.363 −0.154 0.160
−0.459 −0.161 −0.234 0.147 −0.459 −0.165 −0.154 0.161 −0.459 −0.161 −0.235 0.147 −0.459 −0.160 −0.260 0.140 −0.459 −0.163 −0.560 −0.220 −0.507 −0.224 −0.517 −0.199 −0.523 −0.206 −0.616 −0.246 −0.555 −0.253
Max 1.196 1.196 1.813 1.425 1.321 0.822 0.946 0.253 0.858 0.435 0.853 0.253 0.853 0.253 0.795 0.253 0.150
0.018 0.326 0.116 −0.002 0.031
The comparison of the evolved rules and other dispatching rules are shown in Table VII. It is easy to see that non due daterelatedrulessuchasFIFOandLRMhaveverypoor performance when dealing with Jm|| wjTj even though LRM achieves good performance on Jm||Cmax. MS and WSPT show better performance than FIFO and LRM because in- formation about the due date and the weight of a job is considered in these rules. While MS is still much worse than EDD, WSPT shows good performance even though it still cannot totally beat EDD. Sophisticated due-date related rules W(CR+SPT), W(S/RPT+SPT), COVERT and ATC (see [47], [57] for a detailed description of these rules) which have not been included in the list of candidate dispatching rules are also presented here. The expected waiting time in COVERT and ATC is calculated based on the standard method [47] in which the expected waiting time W = b×PR, where PR is the operation processing time. For each method, two parameters needed to be specified which are k (look-ahead parameter) and b. 25 combinations of b ∈ {0.5, 1.0, 1.5, 2.0, 2.5} and k ∈ {1.5, 2.0, 2.5, 3.0, 3.5} are examined on the training set, and the combination that gives the best average performance is selected for comparison in the paper (k = 2.5, b = 2.5 for COVERT and k = 1.5, b = 0.5 for ATC). The performance
of these rules is quite good since they are customized to deal with weighted tardiness problems. However, in the worst case, they still cannot provide better schedules than those obtained by EDD.
The best two evolved rules obtained by the GP system with
different settings are now compared with these human-made
dispatching rules. On both the training set and the test set,
all evolved rules show better average performance than the
existing rules. Similar to what has already been stated for
Jm||Cmax, R1 and R3 rules here are also much better than
R2 rules. However, it is still not easy to find a rule that totally
dominates EDD. Among all the evolved rules, the evolved
R3 rules are the most promising ones. The best two evolved
R3 rules obtained very good average relative deviations for
both training set and test set compared to those obtained by
R and R rules. Rule t1 is also the only evolved adaptive 1 2 R3
dispatching rule that totally dominates EDD on all training and testing instances. Meanwhile, t2 produces a very good
R3 t1
average performance, even better than R3 on the test set and it
is just slightly worse than t1 in the worst case. The promising R3
results of R3 rules again confirm the need for integrating machine and system attributes with sophisticated dispatching rules to produce generalized and effective dispatching rules.
632
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 17, NO. 5, OCTOBER 2013
VI. Analysis and Discussion
The previous section shows the results obtained by the pro- posed GP system and it is noted that the evolved rules can ef- fectively provide good results for Jm||Cmax and Jm|| wjTj. In this section, we will further investigate the evolved rules to figure out how they can produce good performance. An anal- ysis on the components of the evolved rules is given in order to gain more understanding of each factor within the proposed representations that may influence the ability of the GP system to generate better rules. A comparison between the evolved rules and some meta-heuristic approaches is then provided. Finally, the dispatching rules evolved by the proposed GP system are tested under a simulated dynamic JSP environment.
A. Insights from the Evolved Rules
In the previous experiment, there are 540 rules evolved with different GP parameters and representations for Jm||Cmax and Jm|| wjTj. The performance of the two best evolved rules for each representation and each objective function of JSP were shown in Tables V and VII. As an example, we pick one evolved rule from each representation among these rules based on their overall performance on the training set and test set for further analysis (other evolved rules have a similar pattern).
1) Evolved Rules for Jm||C : Here, c1 , c1 and c2 max R1R2 R3
are chosen for analysis. The detailed representations of these rules are shown in Fig. 7. For c1 , the first observation is that
R1
even though the rule looks complicated, it is just a combination
Fig. 7. Selected evolved rules for Jm||Cmax. (a) Evolved rule c1 . (b) Evolved rule c1 . (c) Evolved rule c2 . R1
of four simple dispatching rules (LRM, SPT, LPT, and WSPT)
and three machine attributes (CMI, CWR, DJ). Since WSPT is
less relevant to Jm||Cmax and LPT is not very effective in this
case, they only appear once in the entire adaptive dispatching
rule. The root condition of c1 checks the critical machine R1
idleness and it is noted that LRM is the main dispatching rule when the idleness of the critical machine is greater than 10%. When CMI is small, the rule is more complicated and rules that favor small processing time operations like SPT and WSPT occur more in this case. This rule suggests that when the critical machine is idle, the considered machine should focus on completing operations with small processing times in order to feed more work to the critical machine and keep it busy; otherwise LRM should be used to prevent certain jobs from being completed so late and increase the makespan.
R2 R3
function.2 The rest of the function can be grouped in two
parts. The first part has RT , like rule MWKR, and the second RT
part contains PR , which is a combination of SPT and MWKR.
Different from c1 , c1 Fig. 7(b) is a pure mathematical R1 R2
are employed. However, with the condition that MP has to be
less than 100% at the second level, we can totally eliminate
the subtrees that contain the simple dispatching rules. After
some simplification steps, it is also noted that the arithmetic
rules are also variants of SPTtwk. With the support of the
machine attribute, the obtained arithmetic rules become much
function. In order to make it easy for analysis, we will simplify the whole function by eliminating terms which appear to be less relevant. The simplification step is as follows:
easier to analyse. The simplified version of c2 is as follows:
c1a = (PR+RM)W − (RJ+RM)PR + RT R2 PR RT
+ DD RT W +RT(RJ+RM) (PR+RM ) (PR2 ) PR
PR
c2a = R3
⟨ (RJ +0.594845)(RT +PR) , α = 0.069⟩, W+PR
R3
if CWR > 90%
otherwise
if CWR > 90%
otherwise.
When considering other terms in the second part as a constant
k, we have the approximation of c1 as a linear combination R2
of MWKR and SPT/MWKR. This rule is actually not new. If we omit RT in the approximation function, the rest is known as shortest processing time by total work (SPTtwk) rule in the literature.
Rule c2 [see Fig. 7(c)] is the most interesting rule in this R3
case because both arithmetic rules and simple dispatching rules
≈ RT + RT DD W + RT (RJ + RM)
(RT −PR)
⟨ (W +PR) , α = 0.128⟩,
PR (PR+RM) (PR) ≈ RT + k × RT .
⟨ (RJ +0.594845)(RT +PR) , α = 0.069⟩, ≈ PR
PR
Since the first and second terms of c1 do not make
⟨ (RT −PR) , α = 0.128⟩, PR
R2
much sense in this case, we just drop them from the priority
The revised rules after dropping these irrelevant terms have been tested
2
and it is noted that the performance is not significantly changed.
NGUYEN et al.: STUDY IN GENETIC PROGRAMMING TO EVOLVE DISPATCHING RULES 633 For t2 , we perform the following steps to simplify the
Fig. 8. Selected evolved rules for Jm|| wj Tj . (b) Evolved rule t2 . (c) Evolved rule t1 .
(a)
Evolved
rule
t1 . R1
The dispatching rule following the first priority function is a combination of EDD and WSPT and it is applied when the deviation of processing times of operations in ′ is less than 50%, which means that the minimum processing time is less than half of the maximum processing time. When DJ is larger than 50%, which means that the gap between the minimum and maximum processing time is small, RT is used instead of PR and W2 is used instead of W to increase the priority of jobs with small remaining processing times and high weights.
In general, even though the evolved rules can be very com-
plicated sometimes, they always contain some good patterns
which are very useful for creating good dispatching schedules.
While R1 rules can be easily explained with the support of the
machine and system attributes, R2 rules are quite sophisticated
and often possess very interesting properties. It is surprising
that the R3 rules presented here are quite straightforward
R2
R3
The notation ⟨·, ·⟩ indicates the dispatching rule and α value
as in the middle and right subtrees of Fig. 5. Although both
priority functions of c2 are variants of SPTtwk, the nondelay R3
factor α is smaller for the case when CWR > 90%. One explanation is that when ′ contains many critical operations, it is reasonable to start the available operations right away instead of waiting for the operations that will be ready after the ready time of m∗.
2) Evolved Rules for Jm|| w T : Here, t1 , t2 , t1 jj R1R2
and R3 are selected to represent the evolved rules for
although they contain both machine attributes and composite t1
Jm|| wj Tj . The three full rules obtained by the GP are
dispatching rules. Rule R3 could be quite tricky to represent as a pure mathematical function and it could be more difficult to discover its useful patterns; however, the use of machine and system attributes makes it much easier to identify and explain the rule.
shown in Fig. 8. For t1 , it is quite interesting that this rule R1
can obtain such a good result (as shown in Table VII) without
any due-date related components. The two main simple dis-
patching rules used in this case are WSPT and LPT. While
WSPT can be considered as a suitable rule for Jm|| wjTj,
it does not make sense to include LPT in this case. The result
when we replace LPT by WSPT shows that the refined rule
can still produce the results as good as t1 . For this reason, R1
the contribution for the success of the rule comes from WSPT and other factors instead of the combination of different rules as we observed in the previous section. It is noted that most values of α in this case are about 0.4. Using these values for the WSPT alone show that WSPT with appropriate choice of α can produce the results much better than the case when the nondelay scheduling strategy is used. In this rule, the contribution of the machine and system attributes are not very important and they are mainly employed to improve the worst- case performance.
B. Aggregate View of the Evolved Rules
Fig. 9 shows the frequency that machine and system at- tributes have occurred in all of the evolved R1 and R3 rules. For Jm||Cmax, critical machine related attributes are the most frequent ones while the bottleneck workload ratio has the low- est frequency. This result indicates that the information related to the critical machine is very important for the construction of a good dispatching rule to minimize the makespan. As shown in the previous section, suitable dispatching rules can be selected based on the idleness of the critical machineas well as the critical workload of m∗ . In the case of Jm|| wj Tj , the critical machine related attributes are still employed very
R2 evolved rule:
t2a =0.614PR2(−RM−RM)−RT×PR×RT R2 WW
−(RTPR −0.521)−0.614RMPR+2RT PR RM W W (W−0.5214191) W
≈−0.614RM×PR2(1+ 1 )−RTPR(RT +2 RM ) W W (W − 0.5214191)
≈−k1×PR2(1+ 1)−k2×RTPR. WW
The simplified rule is a linear combination of two sophis- ticated variants of WSPT where the first part includes PR2 instead of PR and the second part includes RT . Repeating the experiment on this simplified rule shows that it can perform better than sophisticated rules like ATC and COVERT regard- ing the average relative deviation with appropriate choice of k1 and k2 (with k2 > k1, similar to the original rule).
It is very surprising that the best evolved rule for Jm|| wjTj with the R3 representation is also the smallest
t1
rule. Rule can be formally described as follows:
R3
⟨−DD×PR,α = 0.331⟩, if DJ ≤ 50%
t1a =
R3 ⟨− DD×RT , α = 0.163⟩, otherwise.
W W2
634
instance la16 la17 la18 la19 la20 la21’ la22’ la23’ la24’ orb01 orb02 orb03 orb04 orb05 orb06 orb07 orb08 orb09 orb010
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 17, NO. 5, OCTOBER 2013 TABLE VIII
Comparison of Evolved Rules With Meta-Heuristic Methods forJm|| wj Tj (h = 1.3)
optimal t1 t2 t1 ATCα COVERTα GA-1 GA-2 LSRW(15) LSRW(200) R1 R2 R3
1170 2000(a) 900 1623(c) 929 1764 948 1884 809 2702 464 1280(c)
1068 1931 837 2053(a) 835 1948
2568 5247 1412 2526 2113 4276 1623 3285 1593 3360 1792 3759 590 1169 2429 2554(abcd) 1316 2388(abc) 1679 3075
2521 2477 2360 2107 1555(ac) 1936 1662 1325(a) 1439 2284 1505(bc) 1439(ab)
2360 1623 1777 1464 1694 1248 2189 1696 2069 1402 1530 1044
1870(a) 1550 2605 1094 1819 1403 4583 4005 2908 2143 4215 2866 3945 2326 3573 2533
3146(a) 3047 1239 927 4404 3792 3190 2061 3109 2217
1619∗∗ 1779 977 ∗ 1248 946 ∗ 1671 966 951 1402 819 ∗
often, and CWR along with DJ are the ones with the highest occurrence frequency. However, the distribution of attributes in Jm|| wjTj are more uniform than that in Jm||Cmax. This observation suggests that different attributes should be used to construct good dispatching rules for Jm|| wjTj.
For the priority functions for composite dispatching rules within R2 and R3 rules, Fig. 10 shows that RT and PR are the most used terms for Jm||Cmax. This explains the occurrence of SPTtwk variants in the best rules in the previous section. While W is theleast used term for Jm||Cmax, it is the most used term in Jm|| wjTj. This emphasizes the importance of weights for determining the priority of operations in Jm|| wj Tj . It is quite surprising that the second most frequent term in evolved rules for Jm|| wj Tj is PR instead of DD. Even though due- dates of jobs also depends on the processing times in aggregate form, the results here suggest that such local information as PR is still very useful for the dispatching tasks for due date related problems.
C. Comparison with Meta-Heuristic Methods
This section compares the performance of the evolved dis- patching rules to some improvement heuristics. Even though it seems unfair to the proposed GP method, since most meta- heuristic methods were especially developed for the static environment and iteratively explore the solution search space of each instance for better solutions, the comparison can provide an indicator about what kind of performance the evolved dispatching rules can achieve. In this section, we only compare the evolved rules with meta-heuristic methods for Jm|| wjTj because it is still a very challenging problem and total weighted tardiness is one of the most important and practical objective functions in the scheduling literature.
Fig. 9. (b) Jm||
Frequency of attributes in the evolved R1 and R3 rules. (a) Jm||Cmax.
wj Tj .
2898 1784(a) 2293 1047(ac) 2270 2600 2100 2131 2692 1136(abc) 5680 4210(ac)
1866 1530 2960 2605 1875 6289 3022 4215 3945 3511 3146(a) 1324 3777(bc) 2679 3418
1286 1909 1094 1479 4865 2075 4647 3188 2673 3689 982 4103 2628 2913
∗
1149 875 844 2726 1434 2289 1816 1802 1852 619 2717 1449 1837
∗
1086 875 ∗ 2616 1434 2204 1674 1662 1802 618 2554 1334 1775
2461(a)
3968
3060
4031
4098 834(abc)
5147 2949 3186
2797
2880(ac)
2280(abc)
1986(abc)
3371(c) 922(bc)
4570 2415(c) 2802(ac)
“GA-1” and “GA-2” represent GA-(R&M/COVERT) and GA-(R&R) [20]; ATCα and COVERTα showed the results from ATC and
“*” means the method found the optimal solution; “a” means that it is the best rule among the three evolved rules for the instance;
‘b” means that the evolved rule is better than GA-(R&M/COVERT) for the instance; “c” means that the evolved rule is better than GA-(R&R) for the instance;
“d” means that the evolved rule is better than LSRW(15) for the instance; and “e” means that the evolved rule is better than LSRW(200) for the instance
Table VIII shows the total weighted tardiness obtained
by the three best evolved rules for the three representations
mentioned above and dispatching rules ATC and COVERT
with fine-tuned α, and those obtained by the hybrid genetic
algorithm [20] and the large step random walk [19] on
selected problem instances from [20] and [19]. In the table,
GA-(R&M/COVERT) and GA-(R&R) are the two versions
of hybrid GA proposed by [20] (with population size of
100 and 2000 generations) while LSRW(t) is the large step
optimization method with running time equal to t seconds.
The instances with bold names are ones that have been used
in the training set. Instance la21’ to la24’ are subproblems
of instance la21-la24 where the last five jobs were omitted
here. In Table VIII, rule t1 produced the best performance R3
in most instances compared to other evolved rules. Although t1 is a very simple rule, it is still able to beat the hybrid GAs
R3 t1
in several cases. Among 19 instances, R3 outperforms GA-
COVERT with α = 0.4.
NGUYEN et al.: STUDY IN GENETIC PROGRAMMING TO EVOLVE DISPATCHING RULES
635
TABLE IX
Parameter Setting of the Simulation Model
Parameter
Number of machines
Arrival process
Processing time
Number of operations per job Visiting order of jobs
Weight
Value
6
Possion with λ from 0.5 to 0.9
Exponential with mean 1 = 1 μ
6
Randomly generated with no machine being revisited
Randomly sampled from {4, 2, 1} with the probabilities {0.2, 0.6, 0.2}
Fig. 10. Frequency ofterminals in the evolved R2 and R3 priority function. (a) Jm||Cmax. (b) Jm|| wjTj.
(R&M/COVERT) in five cases and GA-(R&R) in 12 cases, including ones that have not been included in the training set. Although the objective values obtained by the hybrid GAs are still far from the optimal solutions and those found by LSRW, they are still very promising because they can be directly applied to the real dynamic system without major redesign [20]. The hybrid GAs are also shown to dominate the GA approach [58]. The fact that the GP evolved rules in this paper can beat the hybrid GAs in some cases and be competitive in other cases shows the effectiveness of these rules. Also, while the hybrid GAs need 200000 evaluations and LSRW requires about more than 15 seconds to solve an instance, the GP evolved rules can solve the whole set of 210 instances in less than one second. This suggests new rules can produce better performance and still maintain the efficiency of a dispatching rule. This characteristic makes the GP approach particularly useful for real-time applications. Another advantage of the proposed GP method is that it is able to automatically incorporate information and constraints of different job shop environments into the rules; this it is a very hard task for conventional optimization methods.
D. Performance of Evolved Rules in a Dynamic JSP Environ- ment
This section examines the performance of the evolved
rules in a dynamic environment. A simulation model of a
simple job shop environment is built for the evaluation of
the evolved rules. Table IX shows the parameters of the
simulation model. With this configuration, the utilization of
each machine λ is equal to the arrival rate λ (since μ = 1). μ
The due-date assignment rule is the same as that used in the previous section. Each simulation experiment consists of 30 replications and the common random seeds are used for each experiment in order to reduce the variance of the obtained results. The interval from the beginning of the simulation until the arrival of job 50000 is considered as the warm-up time and all statistics are collected for the next 100 000 jobs. The results obtained from the experiments are shown in Fig. 11. Since the JSP instances in the data set do not consider the release times of jobs (all release times of jobs are assumed to be zero in all instances) which are very important for the dynamic Jm||Cmax, the evolved rules for Jm||Cmax are not suitable for these experiments. So, only the evolved rules for
Fig. 11.
and EDD curves are above all other curves).
Jm|| wjTj presented in Fig. 8 are investigated here. For ease of presentation, the total weighted tardiness is normalized using the formula proposed by [47]. Thus, the normalized
μ
Performance of the evolved rules in the dynamic environment(FIFO
weighted tardiness = wj Tj , where the number of jobs N × M × 1 × w ̄
N = 100000, the number of machines M = 6, the average processing time of an operation 1 = 1 and average weight of a job w ̄ = 2.2. μ
In Fig. 11, the performance of the evolved rules are quite
consistent with what has been shown when dealing with the
static problem. The results show that simple rules such as FIFO
and EDD are easily dominated by the sophisticated rules like
ATC, WSPT, COVERT and the evolved rules. When using
pairwise z-tests to compared the performance of these rules, it
is noted that rule t1 and rule t1 are significantly better (p- R1 R3
value ≪ 0.05) than existing rules ATC, COVERT and WSPT when the utilization is less than or equal to 0.8, but they are beaten by the existing rules when utilization is 0.9. On the other hand, the R2 rule is significantly worse than the existing rules for all levels of utilizations. The R2 rule is significantly worse than R1 and R3 rules when the utilization is less than or equal to 0.8 and better than R1 when utilization is 0.9. One of the reasons for the inferiority of the evolved rules when the utilization of the shop is high is that the evolved rules are trained on a set of static instances which usually reflect the situations in the dynamic job shop with a low utilization.
The investigation of the evolved rules in the dynamic environment shows that there is still a difference in the characteristics between the static problem and the dynamic problem which sometimes prevent the evolved rules from
636 IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 17, NO. 5, OCTOBER 2013
being effective in the dynamic environment. Although the evolved rules show good results in the dynamic Jm|| wj Tj , the fact that they are inferior to the existing rules suggests the lack of generality of the data set used to train the dispatching rules. The deteriorated performance of the evolved rules when utilizations of machines are high is not because the GP system is not able to evolve effective rules but because the static training instances cannot represent all possible scenarios happening in a dynamic environment. Thus, if the ultimate objective of the dispatching rules is to be applied to the dynamic environment, it seems reasonable to train the rules in the dynamic situation (e.g. via a simulation model) in order to ensure that the evolved rules can capture all critical features of the dynamic system.
E. Further Discussions
Many analyses have been performed and it has been noted that the GP system proposed in this paper can find effec- tive dispatching rules for the JSP. Different from traditional applications of evolutionary computation and meta-heuristic methods which can only find a particular solution for a problem instance, the GP system can evolve reusable rules to solve different problem instances without the need to rerun the search algorithm. Since a dispatching rule only provides one schedule for a static problem instance, it is very difficult for these rules to outperform meta-heuristic methods which perform improving steps by exploring thousands of schedules to find better schedules. However, the fact that the evolved rules can beat GA-(R&R) in many instances shows that it is possible to generate powerful dispatching rules for the JSP that are competitive with meta-heuristic methods. It is noted that the program trees are restricted to the maximum depth of six in this paper and many other machine attributes as well as terminals (scheduling parameters) are not considered when the GP system is used to evolve new dispatching rules. These restrictions are made to reduce the computational times of the GP system but they also prevent the GP system from finding better dispatching rules. If a better choice of function set, terminal set, and machine attributes is made, it may be possible that the GP system can evolve rules that are as good as effective meta-heuristic methods but much more efficient.
One major advantage of the evolved rules is that they are quite ready to be applied to the dynamic environment as shown in the previous subsection, which makes these rules more practical than meta-heuristic methods. Therefore the evolved rules are suitable for shops with rapid dynamic changes [22], [59], [60]. In these shops, even when mathematical programming methods are able to find optimal schedules, these schedules can quickly become suboptimal or even infeasible under dynamic conditions [22]. Besides, with its flexibility, the proposed GP system can easily be applied to generate good rules for complex manufacturing processes (e.g. batch process- ing, assembly station, etc.), which are difficult to be handled by conventional optimization methods. Another advantage of the evolved dispatching rules is that they are understandable to the users (managers, operators, and researchers), and therefore it is much easier for these people to incorporate these rules with
other planning decisions compared to the detailed schedules produced by other methods.
Most of the proposed GP systems [5], [8], [39], [40] in the literature is very similar to ours when the R2 representation is used. Miyashita [8] and Jakobovic and Budin [6] are the only works that focus on the use of system attributes, specifically bottleneck machines, to support the sequencing decisions. However, it is noted that the GP system proposed by Miyashita [8] is only suitable when we try to evolve dispatching rules for a specific shop with a small number of machines in which the bottleneck machine is known. Therefore, it is difficult to generalise the rules based on on this GP system. Jakobovic and Budin [6] improved this GP system [8] by using a dedicated GP tree to detect the bottleneck machine to apply suitable dispatching rules. The problem is that the bottleneck machine is not always a good feature to help decide which dispatching rules to be applied. When there are multiple bottleneck machines in the shop, especially with a symmetrical shop, applying a dedicated rule for the detected bottleneck is not very effective since the temporary bottleneck machine can change rapidly before that rule shows any noticeable effect. This explains why the proposed GP-3 system [6] performs significantly better than the simple GP system, but the gaps between the objectives obtained by GP-3 and the simple GP are not large. When examining the GP- 3 system with our training and testing instances, using the same terminal sets for dispatching rules in R2 and R3, the experimental results show that there is no significant difference between the rules evolved by GP-3 and rules evolved with the R2 representation. The analysis in Section VI-B also showed that the workload ratio WR, an indicator for the bottleneck level of the considered machine, is not a major attribute in the best evolved rules. This suggests that different machine and system attributes should be used instead of depend solely on bottleneck machines.
Compared to the existing methods, the novelties of this paper are: 1) the introduction of new representations (R1 and R3) that allow the GP system to evolve effective adaptive dis- patching rules by incorporating machine and system attributes; 2) the comparison of different representations for GP; and (3) the analysis of the evolved dispatching rules, which explain how they solve JSP instances effectively.
VII. Conclusion
Dispatching rules are one of the most crucial tools in production planning and control systems and a large number of studies were conducted to develop more effective rules. However, the development process is still very complicated and time consuming. The improvement in computing power provides some alternatives to facilitate this process. In this paper, we investigated the use of genetic programming as a hyper-heuristic method for automatically discovering new dispatching rules for the job shop scheduling problem. New representations of dispatching rules that take advantage of the machine and system attributes to support the sequencing decisions were developed and examined. The experimental results suggested that the GP system can evolve effective
NGUYEN et al.: STUDY IN GENETIC PROGRAMMING TO EVOLVE DISPATCHING RULES 637
dispatching rules for Jm||Cmax and Jm|| wj Tj with the representations that integrate system attributes and suitable composite dispatching rules. The evolved rules were also shown to outperform the existing rules on the training set and test set. Moreover, the best evolved rules produced competitive performances when compared to the hybrid GAs of [20]. Although the performance of the evolved rules was still far from the optimal solutions in the static JSP, they are still very promising because they are quite ready to be applied to a dynamic system whereas the solutions provided by the exact and meta-heuristic methods have trouble dealing with the dynamics of the shop change. The simulation experiments have confirmed the effectiveness of the evolved rules compared to well-known dispatching rules in the dynamic environment. Also, compared to the solutions obtained by the conventional meta-heuristic approaches, the evolved rules in this paper pro- vided much better interpretability of the sequencing decisions. Another advantage of the proposed GP system is that it only requires one run to generate dispatching rules which can be used to solve multiple problem instances.
In general, this is the first paper that has compared different representations of dispatching rules used in a GP system and investigated how representations influence the performance of the GP system when evolving dispatching rules for the JSP. With their flexibility, the proposed representations in this paper can be easily extended to deal with different manufac- turing environments. Moreover, these representations provide a convenient way to incorporate special system features of real world environments into the adaptive dispatching rules. Therefore, the GP system proposed in this paper can also be employed as a good tool to automatically discover effective dispatching rules for a particular manufacturing system. The analysis in the previous section has shown very interesting characteristics of the evolved rules.
For future studies, there are still many problems that need to be further investigated. This paper has shown that the explicit incorporation of machine and system attributes into the decision making process can provide favorable results. Therefore, it would be very useful to have a comprehensive study of potential attributes and their effects on each type of manufacturing environment. Also, since the dispatching rules will be applied to dynamic situations, whether it is necessary to evolve these rules in the dynamic environment through some simulation model would be an important question for the future research. In addition, while the technique of dis- patching rules can quickly react to changes encountered on the shop floor, some cognitive and organizational practical issues [59] need to be considered. It would be interesting to study these issues when designing the dispatching rules, such as by developing a multiobjective GP-HH method to evolve rules that can satisfy multiple practical requirements. Fitness landscapes defined by different fitness functions would be very interesting to explore and will be a good topic for future research. Finally, even though the proposed representation is useful, it also creates a large search space for the GP system to explore. For that reason, it would be worthwhile paying more attention to the design of specialized genetic operators to be able to find the good rules.
References
[1] S. S. Panwalkar and W. Iskander, “A survey of scheduling rules,” Oper. Res., vol. 25, no. 1, pp. 45–61, 1977.
[2] M. S. Jayamohan and C. Rajendran, “Development and analysis of cost- based dispatching rules for job shop scheduling,” Eur. J. Oper. Res., vol. 157, no. 2, pp. 307–321, 2004.
[3] M. S. Jayamohan and C. Rajendran, “New dispatching rules for shop scheduling: A step forward,” Int. J. Prod. Research, vol. 38, no. 3, pp. 563–586, 2000.
[4] L. Nie, X. Shao, L. Gao, and W. Li, “Evolving scheduling rules with gene expression programming for dynamic single-machine scheduling problems,” Int. J. Adv. Manufacturing Technol., vol. 50, no. 5, pp. 729– 747, 2010.
[5] J. C. Tay and N. B. Ho, “Evolving dispatching rules using genetic programming for solving multiobjective flexible job-shop problems,” Comput. Industrial Eng., vol. 54, no. 3, pp. 453–473, 2008.
[6] D. Jakobovic and L. Budin, “Dynamic scheduling with genetic program- ming,” in Proc. EuroGP, 2006, pp. 73–84.
[7] T. Hildebrandt, J. Heger, and B. Scholz-Reiter, “Toward improved dis- patching rules for complex shop floor scenarios: A genetic programming approach,” in Proc. GECCO, 2010, pp. 257–264.
[8] K. Miyashita, “Job-shop scheduling with GP,” in Proc. GECC, 2000, pp. 505–512.
[9] S. Nguyen, M. Zhang, M. Johnston, and K. C. Tan, “A coevolution genetic programming method to evolve scheduling policies for dynamic multiobjective job shop scheduling problems,” in Proc. IEEE Congr. CEC, Jun. 2012, pp. 3261–3268.
[10] S. Nguyen, M. Zhang, M. Johnston, and K. C. Tan, “Evolving reusable operation-based due-date assignment models for job shop scheduling with genetic programming,” in Proc. 15th EuroGP, 2012, pp. 121–133.
[11] X. Li and S. Olafsson, “Discovering dispatching rules using data mining,” J. Scheduling, vol. 8, no. 6, pp. 515–527, 2005.
[12] H. Ingimundardottir and T. Runarsson, “Supervised learning linear priority dispatch rules for job-shop scheduling,” in Proc. LION 5, 2011, pp. 263–277.
[13] B. Giffler and G. L. Thompson, “Algorithms for solving production- scheduling problems,” Oper. Res., vol. 8, no. 4, pp. 487–503, 1960.
[14] A. Jones, L. C. Rabelo, and A. T. Sharawi, “Survey of job shop schedul- ing techniques,” in Wiley Encyclopedia of Electrical and Electronics Engineering. New York: Wiley, 2001.
[15] H. R. Lourenco, “Job-shop scheduling: Computational study of local search and large-step optimization methods,” Eur. J. Oper. Res., vol. 83, no. 2, pp. 347–364, 1995.
[16] E. Nowicki and C. Smutnicki, “A fast taboo search algorithm for the job shop problem,” Manage. Sci., vol. 42, no. 6, pp. 797–813, 1996.
[17] E. Balas and A. Vazacopoulos, “Guided local search with shifting bottleneck for job shop scheduling,” Manage. Sci., vol. 44, no. 2, pp. 262–275, 1998.
[18] R. Cheng, M. Gen, and Y. Tsujimura, “A tutorial survey of job-shop scheduling problems using genetic algorithms, Part II: Hybrid genetic search strategies,” Comput. Industrial Eng., vol. 36, no. 2, pp. 343–364, 1999.
[19] S. Kreipl, “A large step random walk for minimizing total weighted tardiness in a job shop,” J. Scheduling, vol. 3, no. 3, pp. 125–138, 2000.
[20] H. Zhou, W. Cheung, and L. C. Leung, “Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm,” Eur. J. Oper. Res., vol. 194, no. 3, pp. 637–649, 2009.
[21] K. N. McKay, F. R. Safayeni, and J. A. Buzacott, “Job-shop schedul- ing theory: What is relevant?” Interfaces, vol. 18, no. 4, pp. 84–90, 1988.
[22] S. C. Sarin, A. Varadarajan, and L. Wang, “A survey of dispatching rules for operational control in wafer fabrication,” Prod. Planning Control, vol. 22, no. 1, pp. 4–24, 2011.
[23] E. K. Burke, M. R. Hyde, G. Kendall, G. Ochoa, E. Ozcan, and J. R. Woodward, “A classification of hyper-heuristic approaches,” in Handbook of Metaheuristics (Int. Series in Operations Research and Management Science, vol. 146). Berlin, Germany: Springer, 2010, pp. 449–468.
[24] E. K. Burke, M. R. Hyde, G. Kendall, G. Ochoa, E. Ozcan, and R. Qu, “Hyper-heuristics: A survey of the state of the art,” School of Computer Science and Inform. Technol., Univ. Nottingham, Computer Science Technical Report No. NOTTCS-TR-SUB-0906241418-2747, 2010.
638 IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 17, NO. 5, OCTOBER 2013
[25] E. K. Burke, M. R. Hyde, G. Kendall, G. Ochoa, E. Ozcan, and J. R. Woodward, “Exploring hyper-heuristic methodologies with genetic programming,” in Computational Intelligence (Series Intelligent Systems Reference Library), vol. 1, C. Mumford and L. Jain, Eds., Berlin, Heidelberg: Springer, 2009, pp. 177–201.
[26] A. Bolte and U. W. Thonemann, “Optimizing simulated annealing schedules with genetic programming,” Eur. J. Oper. Res., vol. 92, no. 2, pp. 402–416, 1996.
[27] A. Fukunaga, “Automated discovery of composite SAT variable- selection heuristics,” in Proc. 18th Nat. Conf. Artificial Intell., 2002, pp. 641–648.
[28] M. B. Bader-El-Den and R. Poli, “Generating SAT local-search heuris- tics using a GP hyper-heuristic framework,” in Proc. 8th Int. Conf. Artificial Evol., 2007, pp. 37–49.
[29] E. K. Burke, M. R. Hyde, and G. Kendall, “Evolving bin pack- ing heuristics with genetic programming,” in Proc. PPSN, 2006, pp. 860–869.
[30] E. K. Burke, M. R. Hyde, G. Kendall, and J. R. Woodward, “The scalability of evolved online bin packing heuristics,” in Proc. IEEE CEC, Sep. 2007, pp. 2530–2537.
[31] E. K. Burke, M. R. Hyde, G. Kendall, and J. R. Woodward, “A genetic programming hyper-heuristic approach for evolving two dimensional strip packing heuristics,” IEEE Trans. Evolu. Comput., vol. 14, no. 6, pp. 942–958, Dec. 2010.
[32] R. Keller and R. Poli, “Linear genetic programming of parsimonious metaheuristics,” in Proc. IEEE CEC, Sep. 2007, pp. 4508–4515.
[33] R. Keller and R. Poli, “Cost-benefit investigation of a genetic-
programming hyperheuristic,” in Proc. 8th Int. Conf. Artifcial Evolu.,
2007, pp. 13–24.
[34] M. B. Bader-El-Den, R. Poli, and S. Fatima, “Evolving timetabling
heuristics using a grammar-based genetic programming hyper-heuristic
framework,” Memetic Computing, vol. 1, no. 3, pp. 205–219, 2009.
[35] E. K. Burke, M. R. Hyde, and G. Kendall, “Grammatical evolution of local search heuristics,” IEEE Trans. Evolu. Comput., vol. 16, no. 3, pp.
406–417, Jun. 2012.
[36] C. Dimopoulos and A. M. S. Zalzala, “Investigating the use of genetic
programming for a classic one-machine scheduling problem,” Adv. Eng.
Software, vol. 32, no. 6, pp. 489–498, 2001.
[37] D. Jakobovic, L. Jelenkovic, and L. Budin, “Genetic programming
heuristics for multiple machine scheduling,” in Proc. EuroGP, 2007,
pp. 321–330.
[38] C. D. Geiger, R. Uzsoy, and H. Aytug, “Rapid modeling and discovery
of priority dispatching rules: An autonomous learning approach,” J.
Heuristics, vol. 9, no. 1, pp. 7–34, 2006.
[39] C. D. Geiger and R. Uzsoy, “Learning effective dispatching rules for
batch processor scheduling,” Int. J. Prod. Res., vol. 46, no. 6, pp. 1431–
1454, 2008.
[40] W. J. Yin, M. Liu, and C. Wu, “Learning single-machine scheduling
heuristics subject to machine breakdowns with genetic programming,”
in Proc. IEEE CEC, Dec. 2003, pp. 1050–1055.
[41] L. Atlan, J. Bonnet, and M. Naillon, “Learning distributed reactive
strategies by genetic programming for the general job shop prob- lem,” in Proc. 7th Annu. Florida Artificial Intell. Res. Symp., 1994, p. 11.
[42] C. Pickardt, J. Branke, T. Hildebrandt, J. Heger, and B. Scholz-Reiter, “Generating dispatching rules for semiconductor manufacturing to min- imize weighted tardiness,” in Proc. WSC, 2010, pp. 2504–2515.
[43] J. A. Vazquez-Rodriguez and G. Ochoa, “On the automatic discovery of variants of the NEH procedure for flow shop scheduling using genetic programming,” J. Oper. Res. Soc., vol. 62, no. 2, pp. 381–396, 2011.
[44] D.J.John,“Co-evolutionwiththeBierwirth–Mattfeldhybridscheduler,” in Proc. 9th Annu. Conf. GECCO, 2002, p. 259.
[45] S. Petrovic and E. Castro, “A genetic algorithm for radiotherapy pre-treatment scheduling,” in Proc. Appl. Evolu. Comput., 2011, pp. 454–463.
[46] W. J. Hopp and M. L. Spearman, Factory Physics: Foundations of Manufacturing Management. New York: McGraw-Hill, 2000.
[47] A. P. J. Vepsalainen and T. E. Morton, “Priority rules for job shops with weighted tardiness costs,” Manage. Science, vol. 33, no. 8, pp. 1035–1047, 1987.
[48] J. R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: MIT Press, 1992.
[49] P. Pardalos and O. Shylo, “An algorithm for the job shop scheduling problem based on global equilibrium search techniques,” Comput. Man- age. Sci., vol. 3, no. 4, pp. 331–348, 2006.
[50] S. Luke. (2009). Essentials of Metaheuristics[Online]. Available: http://cs.gmu.edu/∼sean/book/metaheuristics/
[51] S. Lawrence, “Resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques,” Ph.D. dissertation, Graduate School Ind. Adm., Carnegie-Mellon Univ., Pittsburgh, PA, 1984.
[52] D. Applegate and W. Cook, “A computational study of the job-shop scheduling instance,” ORSA J. Computing, vol. 3, no. 2, pp. 149–156, 1991.
[53] E. Taillard, “Benchmarks for basic scheduling problems,” Eur. J. Oper. Res., vol. 64, no. 2, pp. 278–285, 1993.
[54] E. Demirkol, S. Mehta, and R. Uzsoy, “Benchmarks for shop schedul- ing problems,” Eur. J. Oper. Res., vol. 109, no. 1, pp. 137–141, 1998.
[55] K. R. Baker, “Sequencing rules and due-date assignments in a job shop,” Manag. Sci., vol. 30, no. 9, pp. 1093–1104, 1984.
[56] M. Pinedo and M. Singer, “A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop,” Naval Res. Logistics, vol. 46, no. 1, pp. 1–17, 1999.
[57] P. Mizrak and G. M. Bayhan, “Comparative study of dispatching rules in a real-life job shop environment,” Appl. Artificial Intell., vol. 20, no. 7, pp. 585–607, 2006.
[58] D. C. Mattfeld and C. Bierwirth, “An efficient genetic algorithm for job shop scheduling with tardiness objectives,” Eur. J. Oper. Res., vol. 155, no. 3, pp. 616–630, 2004.
[59] J. Riezebos, J. M. Hoc, N. Mebarki, C. Dimopoulos, W. Wezel, and G. Pinot, “Design of scheduling algorithms: Applications,” in Behavioral Operations in Planning and Scheduling, J. C. Fransoo, T. Waefler, and J. R. Wilson, Eds., Berlin: Springer, 2011, pp. 371–412.
[60] T. Sloan, “Shop-floor scheduling of semiconductor wafer fabs: Exploring the influence of technology, market, and performance objectives,” IEEE Trans. Semiconductor Manufacturing, vol. 16, no. 2, pp. 281–289, May 2003.
Su Nguyen received the B.E. degree in industrial and systems engineering from the Ho Chi Minh City University of Technology, Hochiminh City, Vietnam, in 2006, and the M.E. degree in indus- trial engineering and management from the Asian Institute of Technology (AIT), Bangkok, Thailand. He is currently pursuing the Ph.D. degree with the Evolutionary Computation Research Group, Victoria University of Wellington (VUW), Wellington, New Zealand.
Prior to VUW, he was a Research Associate of industrial and manufacturing engineering with the School of Engineering and Technology, AIT. His current research interests include evolutionary computation, discrete-event simulation, and their applications in operations
planning and scheduling.
Mengjie Zhang (SM’10) received the B.E. and M.E. degrees from the Artificial Intelligence Research Center, Agricultural University of Hebei, Baoding, China, in 1989 and 1992, respectively, and the Ph.D. degree in computer science from RMIT University, Melbourne, Australia, in 2000.
Since 2000, he has been with the Victoria Univer- sity of Wellington, Wellington, New Zealand. He is currently a Professor of computer science and heads the Evolutionary Computation Research Group. His current research interests include evolutionary com-
putation, genetic programming, and particle swarm optimization with ap- plication areas of image analysis, multiobjective optimization, classification with unbalanced data, and feature selection and dimension reduction for classification with high dimensions.
Dr. Zhang is a member of the IEEE Computer Society, the IEEE CI Society, and the IEEE SMC Society. He is also a member of the IEEE CIS Evolutionary Computation Technical Committee, a member of the IEEE CIS Intelligent Systems Applications Technical Committee, a Vice Chair of the IEEE CIS Task Force on Evolutionary Computer Vision and Image Processing, and a Committee Member of the IEEE New Zealand Central Section. He is a member of the ACM and the ACM SIGEVO Group. He has been serving as an Associate Editor or Editorial Board Member for five international journals.
NGUYEN et al.: STUDY IN GENETIC PROGRAMMING TO EVOLVE DISPATCHING RULES
639
Mark Johnston (M’10) received the B.Sc. degree in mathematics and computer science and the Ph.D. degree in operations research from Massey Univer- sity, Palmerston North, New Zealand.
He is currently a Senior Lecturer with the Victoria University of Wellington, Wellington, New Zealand, where he teaches various operation research courses. His current research interests include primarily com- binatorial optimization and evolutionary computa- tion, with a particular interest in scheduling models, genetic programming, and multiple-objective opti-
Kay Chen Tan (SM’08) received the B.Eng. degree (First Class Honors) in electronics and electrical en- gineering and the Ph.D. degree from the University of Glasgow, Glasgow, Scotland, U.K., in 1994 and 1997, respectively.
He is currently an Associate Professor with the Department of Electrical and Computer Engineering, National University of Singapore, Singapore. He has published over 100 journal papers, over 100 papers in conference proceedings, co-authored five books, and co-edited four books.
He served as the General Co-Chair for the IEEE Congress on Evolutionary Computation, Singapore, in 2007, and the General Co-Chair for the IEEE Symposium on Computational Intelligence in Scheduling, Tennessee, in 2009. He has been an IEEE Distinguished Lecturer of the IEEE Computational Intelligence Society since 2011. He is currently the Editor-in-Chief of the IEEE Computational Intelligence Magazine. He also serves as an Associate Editor and Editorial Board member of over 15 international journals. He was a recipient of the 2012 IEEE Computational Intelligence Society Outstanding Early Career Award. He was a recipient of the Recognition Award in 2008 from the International Network for Engineering Education and Research (iNEER). He was a recipient of the NUS Outstanding Educator Award in 2004, the Engineering Educator Award in 2002, 2003, and 2005, the Annual Teaching Excellence Award in 2002, 2003, 2004, 2005, and 2006, and the Honor Roll Award in 2007.
mization.