Investigating a Machine Breakdown Genetic Programming Approach for Dynamic Job Shop Scheduling

Abstract

Dynamic job shop scheduling (JSS) problems with dynamic job arrivals have been studied extensively in the literature due to their applicability to real-world manufacturing systems, such as semiconductor manufacturing. In a dynamic JSS problem with dynamic job arrivals, jobs arrive on the shop floor unannounced that need to be processed by the machines on the shop floor. A job has a sequence of operations that can only processed on specific machines, and machines can only process one job at a time. Many effective genetic programming based hyper-heuristic (GP-HH) approaches have been proposed for dynamic JSS problems with dynamic job arrivals, where high quality dispatching rules are automatically evolved by GP to handle the dynamic JSS problem instances. However, research that focus on handling multiple dynamic events simultaneously are limited, such as both dynamic job arrivals and machine breakdowns. A machine breakdown event results in the affected machine being unable to process any jobs during the repair time. It is likely that machine breakdowns can significantly affect the effectiveness of the scheduling procedure unless they are explicitly accounted for. Therefore, this paper develops new machine breakdown terminals for a GP approach and evaluates their effectiveness for a dynamic JSS problem with both dynamic job arrivals and machine breakdowns. The results show that the GP approaches with the machine breakdown terminals do show improvements. The analysis shows that the machine breakdown terminals may indirectly contribute in the evolution of high quality rules, but occur infrequently in the output rules evolved by the machine breakdown GP approaches.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Job shop scheduling (JSS) problems are combinatorial optimisation problems that have been studied over the past 60 years [1]. Due to their direct application in important real-world manufacturing systems, extensive research has been carried out for JSS problems to find effective and practical techniques which may be incorporated to a real-world scenario for the manufacturers so that they gain a competitive edge in the respective markets [1]. In a JSS problem instance, there are machines on the shop floor that are used to process arriving jobs, and the manufacturer needs to make intelligent decisions to process the jobs as effectively as possible. In other words, machine resources need to be optimally allocated (given a specific criterion) by determining the sequence in which the jobs are processed. However, optimal allocation of machines can be a difficult task. Most job shop scheduling (JSS) problems are NP-hard [1], and mathematical optimisation techniques that return optimal solutions for problem instances do not scale effectively with the problem size. In addition, in a dynamic JSS problem instance there are unforeseen events that affect the properties of the shop floor, e.g., dynamic job arrivals and machine breakdowns [2]. To handle dynamic JSS problems, various heuristic approaches have been proposed to generate good solutions to problem instances while coping with the unforeseen events. For this paper, we handle dynamic JSS problems with dynamic job arrivals, where the jobs’ properties and their arrival times are unknown until the job arrival times are reached during processing [3]. Dispatching rule approaches are the most prominent method of handling dynamic JSS problems with dynamic job arrivals due to their short reaction times and their ability to cope with the dynamic environment [4].

In addition to manually designing effective dispatching rules for dynamic JSS problems with dynamic job arrivals, researchers have proposed various genetic programming based hyper-heuristic (GP-HH) approaches to automatically evolving dispatching rule from heuristic subcomponents [5]. GP evolved dispatching rules generally perform better than man-made dispatching rules for JSS problems [6]. However, GP approaches that have been proposed for dynamic JSS problems have mainly focused on dynamic job arrivals [3,4,5,6,7]. In a real-world scenario, it is likely that there are different types of dynamic events that occur during processing. An example is machine breakdown, where the machines need to be serviced and repaired [2]. It is likely that disruptions caused by machine breakdowns can likely impact the performance of the scheduling algorithm if they are not specifically accounted for. The only GP approach that explicitly accounts for machine breakdowns in the literature deals with a single machine JSS problem with no dynamic job arrivals [8]. Developing machine breakdown specific GP approaches may allow us to improve the overall quality of rules evolved by GP for dynamic JSS problems with dynamic job arrivals and machine breakdowns (DJSS-MB).

1.1 Goal

The goal of this paper is to develop new machine breakdown terminals for a GP terminal set commonly used in the literature [4, 7] to handle a DJSS-MB. By incorporating machine breakdown terminals into the GP terminal set, it may be possible to evolve rules that can account for machine breakdown information. This may result in the evolved rules being able to make better decisions for both machine breakdown and non-machine breakdown JSS problem instances than rules evolved without machine breakdown information, and generate better solutions overall. In other words, developing new machine breakdown terminals may allow GP to consistently evolve high quality rules for DJSS-MB. Afterwards, by analysing specific machine breakdown GP evolved rules, it may be possible to develop an insight into how the rules behave in DJSS-MB, allowing us to potentially develop more effective machine breakdown GP approaches in the future. Overall, this paper carries out the following objectives:

• (a) Develop and evaluate new machine breakdown terminals for an existing GP approach [4, 7].

• (b) Carry out a structural analysis of the machine breakdown GP rules to gain an understanding of the useful features and properties of GP rules that are evolved under machine breakdown.

1.2 Organisation

First, we cover the background to dynamic JSS in Sect. 2, which includes the problem definition and outlines existing GP approaches for dynamic JSS problems. Afterwards, Sect. 3 describes the existing GP approach used in the literature [4, 7], the benchmark GP terminals, and the machine breakdown GP terminals investigated in this paper. Section 4 describes the dynamic JSS simulation model used in this paper, and the GP parameters. Finally, Sect. 5 gives the results and an analysis of the findings, and Sect. 6 gives the concluding remarks and the future works.

2 Background and Related Work

This section covers the problem definition for the DJSS-MB, and the GP approaches for dynamic JSS problems in the literature.

2.1 Problem Definition

In a dynamic JSS problem instance, an arriving job $j$ has a sequence of operations $\sigma _{1j},\dots ,\sigma _{N_{j}j}$. The operations must be processed sequentially (e.g. $\sigma _{1j}$ must be processed before $\sigma _{2j}$) and need to be processed on specific machines $m(\sigma _{1j}),\dots ,m(\sigma _{N_{j}j})$. An operation $\sigma _{ij}$ needs to be processed on machine $m(\sigma _{ij})$ for time $p_{ij}$ (which is called the processing time), and a machine can only process one job at a time. The time that a job arrives at the machine for an operation $\sigma _{ij}$ is denoted as $r_{ij}$, and the time that the job arrives on the shop floor ($r_{1j}$) is called the job arrival time $r_j$. For this paper, the objective is to minimise total weighted tardiness (MWT). MWT objective has been studied extensively in the literature [1], and tardiness related objectives have been shown to be quite sensitive to machine breakdown events [9, 10]. In a MWT objective, an arriving job has a due date $d_j$ and a weight $w_j$. If job $j$’s completion time $C_j$ (the time when the last operation of job $j$ completes) is below due date $d_j$, i.e., $C_j\le d_j$, then no penalty is incurred. Otherwise, job $j$ is considered tardy, and has tardiness $T_j=d_j- C_j$ [11]. After all $N$ arriving jobs are completed, the MWT of the schedule is given by $\frac{1}{N} \sum _{j=1}^Nw_jT_j$.

The two types of dynamic events that occur during processing are dynamic job arrivals and machine breakdowns. With a dynamic job arrival, the information about a job $j$, including its properties, are not known in advance until the job arrives at time $r_j$. With a machine breakdown event, a machine $m$ breaks down at time $b^m$ and the machine needs to be repaired for time $r^m$. During the repair time, the machine is unavailable to process any operations. If a job’s operation is currently being processed at the machine at the time of breakdown, then the job’s operation is resumed from the time it was interrupted after the machine is repaired. This means that if a job $j$’s operation $\sigma _{ij}$ is started at time $s_t$ and is interrupted by machine $m$’s breakdown, then the operation completes at time $s_t\,+\,p_{ij}\,+\, r^m$. A job operation resuming from the point of interruption is consistent with the machine breakdown definition in the literature [8, 9] to handle dynamic JSS problems with machine breakdown. In addition, a common assumption in the literature is that machine breakdowns events are unforeseeable [2]. However, for this paper we simplify the problem by allowing the shop floor to know when the machine breakdown occurs in advance. This is because GP approaches that handle both dynamic job arrivals and machine breakdowns have not yet been proposed in the literature. By doing this, we can carry out a preliminary investigation of machine breakdown terminals that incorporate informations about future machine breakdowns (described in Sect. 3.2). After analysing these terminals that take full information about future machine breakdowns into account, it may be possible to develop machine breakdown terminals in the future that can cope effectively even when the machine breakdown events are unforeseen events.

2.2 GP for Dynamic JSS Problems

GP approaches have been extensively applied to dynamic JSS problems to evolve dispatching rules [5, 6]. Many GP approaches use single arithmetic function trees as priority dispatching rules [5, 6]. Geiger et al. [12] showed that GP can evolve optimal priority dispatching rules for static JSS problems that are not NP-hard. They also showed that priority dispatching rules evolved for NP-hard static JSS problems and dynamic JSS problems perform better than benchmark man-made dispatching rules. Hildebrandt et al. [3] provided a GP approach for a dynamic JSS problem with the flowtime minimisation objective, and showed that the GP evolved rules outperform state-of-the-art man-made dispatching rules. Branke et al. [5] and Nguyen et al. [6] both carry out extensive survey of GP-HH approaches to scheduling problems in the literature. Nguyen et al. [13] also provide a unified framework for GP-HH to scheduling problems and categorises existing GP approaches using the framework.

The following are GP approaches that evolve scheduling rules for dynamic JSS problems with machine breakdowns. Yin et al. [8] proposed a two-tree GP approach for a single machine JSS problem. The first tree acts as a dispatching rule, and the second tree is used to calculate the idle time to add in between processing different jobs on a machine. They showed that the evolved rules outperform the benchmark man-made heuristics designed for JSS problems with machine breakdowns. Park et al. [10] carried out an investigation on the generality of GP over a JSS problem with different frequencies and durations of machine breakdowns, and found that the proportion of time the machines are being repaired is a significant factor in the qualities of the evolved rules. In addition, they showed that GP is not general enough to cover for all different scenarios effectively, and that it is likely that machine breakdown specific information is required to improve the generality of GP.

3 Machine Breakdown GP for the Dynamic JSS Problem

As machine breakdown GP approach for DJSS-MB have not been proposed, this paper proposes simple but novel machine breakdown terminals which are incorporated to a GP approach. This allows GP to evolve dispatching rules that may make better decisions during decision situations, potentially leading to better performance than GP evolved rules which do not incorporate machine breakdowns. First, we describe the GP representation, the benchmark terminal and function sets. This is followed by the descriptions and justifications for the machine breakdown GP terminals. The first approach replaces existing terminals related to operation processing times and add repair time of machines if necessary. This approach is denoted as “augmented” approach, as it attempts to improve certain benchmark terminals by incorporating machine breakdown information. The second approach adds new machine breakdown terminals, which “react” to the machine breakdowns happening on the shop floor, to the existing set of GP terminals.

3.1 GP Representation, Terminal Set and Function Set

For this paper, we use a tree-based GP representation [14]. The GP individuals represent arithmetic function trees that calculate the priorities of jobs during decision situations. Arithmetic GP representation has been used prominently in the literature to evolve effective priority dispatching rules for JSS problems [5]. A GP terminal corresponds to a job, machine and shop floor attribute value at a decision situation, or combines multiple base level shop floor attributes as a part of the terminal. For example, the ${\text {RT}}$ terminal returns the sum remaining total processing times of job $j$ waiting at a machine to process operation $\sigma _{ij}$, i.e., ${\text {RT}}(j) = \sum _{k=i}^{N_j} p_{kj}$. The GP terminals and the arithmetic operators used by the benchmark GP approach are listed in Table 1, which is based off existing terminal and function sets used by GP approaches to dynamic JSS problems in the literature [7, 10]. The function set consists of the arithmetic operators $+$, −, $\times$, protected  / , binary operators $\max$, $\min$ and a ternary operator ${\texttt {if}}$. The protected  /  returns one if the denominator is zero, and carries out the standard division operator otherwise. $\max$ and $\min$ returns the maximum and the minimum value of the two arguments respectively. ${\texttt {if}}$ returns the value of the second argument if the value of the first argument is greater than or equal to zero, or returns the value of the third argument otherwise.

Table 1. Terminal set for GP, where a job $j$ is waiting at the available machine $m$ at a decision situation.

A GP individual $\omega$ is evaluated over a set of dynamic JSS training instances to calculate its fitness as follows. GP individual $\omega$ is applied to a JSS problem instance $\gamma$ as a non-delay dispatching rule [11]. During a simulation when a machine $m$ becomes available, the jobs that are currently waiting at machine $m$ are assigned priority values by the dispatching rule. The job that has the highest priority value is selected to be processed at machine $m$. This continues until the termination criteria for the simulation has been reached (e.g. after a certain number of jobs have been completed), at which point the objective function value ${Obj}(\omega ,\gamma )$ is calculated from the solution generated by individual $\omega$. The individual $\omega$ is applied to all problem instances in the training sets, obtaining objective values ${Obj}(\omega ,\gamma _1),\dots ,{Obj}(\omega ,\gamma _{T_{train}})$.

After the GP individual $\omega$ is applied to the problem instances in the training set, the objective values obtained are normalised to reduce the likelihood that the GP individuals are biased towards specific instances [3, 15]. In other words, an objective value ${Obj}(\omega ,\gamma )$ for a solution generated by individual $\omega$ for instance $\gamma$ is normalised using reference objective value ${Obj}(R,\gamma )$ as shown in Eq.  (1). The reference objective value ${Obj}(R,\gamma )$ is calculated from the solution generated by applying a reference rule $R$ to the problem instance $\gamma$. The reference rule used is the weighted apparent tardiness cost (wATC) rule [16], a man-made dispatching rule effective for weighted tardiness related objectives. This was also used by Park et al. [10] in the fitness function to evolve GP rules for the DJSS-MB.

$$\begin{aligned} {Obj}'(\omega ,\gamma ) = \frac{{Obj}(\omega ,\gamma )}{{Obj}(R,\gamma )} \end{aligned}$$

(1)

3.2 Augmented GP Terminals

The following terminals in the original GP terminal set (as described in Table 1) are replaced by terminals that add repair times of the machines: job’s operation processing time (${\text {PT}}$), job’s next operation processing time (${\text {NPT}}$) and work in next queue (${\text {WINQ}}$). The replaced GP terminals return the original value if the job’s operation is not interrupted by a machine breakdown, and adds the repair time of the machine otherwise. The terminals that incorporate the machine breakdown information is denoted with the prefix ‘MB-’ (e.g. for machine breakdown adjusted processing time). The GP approach that incorporates the , and terminals is denoted as GP-${\text {Aug}}$.

Machine breakdown adjusted processing time (MBPT): The machine breakdown adjusted processing time terminal () replaces the processing time terminal (${\text {PT}}$) in Table 1. Given that the current time during the decision situation is $t$ and the processing time of job’s current operation $j$ is $p_{ij}$, terminal returns the actual duration of time required to process the job’s operation by factoring the machine breakdown interruption into account. In other words, if the job is not interrupted by a machine breakdown, i.e., if the operation completes earlier than the breakdown time $b_t^m$ of the current machine $m$, then the job’s actual processing time $p'_{ij}$ is equal to the expected processing time $p_{ij}$. Otherwise, the actual processing time is the sum of the processing time and the machine repair time $r_t^m$ required to get the machine back up and running before the operation is resumed. The value returned by , where the calculation for $p'_{ij}$ is shown in Eq.  (2).

$$\begin{aligned} p'_{ij}&= \left\{ \begin{array}{lr} p_{ij} &{} \text {if } t+ p_{ij} < b_t^m\\ p_{ij} + r_t^m&{} \text {otherwise} \\ \end{array} \right. \end{aligned}$$

(2)

Machine breakdown adjusted next processing time (MBNPT): The machine breakdown adjusted next processing time terminal () replaces the next processing time terminal (${\text {NPT}}$) in Table 1. terminal returns zero if the job $j$’s current operation $\sigma _{ij}$ is the last operation before job $j$’s completion. Otherwise, given that the next operation $\sigma _{(i+1)j}$ is processed on machine $m'$, the repair time of $m'$ is added to the next processing time $p_{(i+1)j}$ if it is expected to be interrupted by a breakdown at machine $m'$ at operation $\sigma _{(i+1)j}$ earliest possible completion at machine $m'$. The earliest possible time that job $j$ can be completed is if operation $\sigma _{ij}$ is selected immediately by machine $m$, and then the successive operation $\sigma _{(i+1)j}$ is then processed by machine $m'$ as soon as operation $\sigma _{ij}$ is completed. The time when operation $\sigma _{ij}$ completes is given by the current time $t$ and the actual processing time $p'_{ij}$, which depends on whether the operation is interrupted by machine breakdown (Eq.  (2)). In other words, the earliest time operation $\sigma _{(i+1)j}$ can be processed at machine $m'$ is at $t+ p'_{ij}$ after operation $\sigma _{ij}$ is expected to complete. Therefore, if machine $m'$ breaks down before time $t+ p'_{ij} + p_{(i+1)j}$, then repair time $r_t^{m'}$ of machine $m'$ is added to the operation $\sigma _{(i+1)j}$’s processing time $p_{(i+1)j}$ as shown in Eq.  (3).

(3)

Machine breakdown adjusted work in next queue (MBWINQ): The machine breakdown adjusted work in next queue terminal () replaces the work in next queue terminal (${\text {WINQ}}$) in Table 1. Both ${\text {WINQ}}$ and terminals return zero if the job $j$’s current operation $\sigma _{ij}$ is the last operation before job $j$’s completion. Otherwise, given that machine $m'$ is required by operation $\sigma _{(i+1)j}$, the standard ${\text {WINQ}}$ terminal returns the sum processing times of the jobs that are currently waiting at machine $m'$ plus the remaining time required to process the operation currently being processed by machine $m'$, i.e., the work remaining. modifies the work remaining time calculated by ${\text {WINQ}}$, and adds the machine $m'$’s repair time if the work is interrupted by machine breakdown at time $b_t^{m'}$. In other words, , where $p_{j_1},\dots ,p_{j_{N_{m'}}}$ are the processing times of jobs waiting at machine $m'$, ${wr}'_{m'j'}$ is the actual work remaining required on $j'$ being processed on machine $m'$ before it becomes available. The calculation for actual work remaining ${wr}'_{m'j'}$ is given in Eq. (4), where $s_{j'}$ denotes the time when $j'$ started, $p_{j'}$ is the processing time required by $j'$ at machine $m'$ and $t$ is the current time.

$$\begin{aligned} {wr}'_{m'j'}&= \left\{ \begin{array}{lr} s_{j'} + p_{j'} - t&{} \text {if } s_{j'} + p_{j'} < b_t^{m'} \\ s_{j'} + p_{j'} - t+ r_t^{m'} &{} \text {otherwise} \\ \end{array} \right. \end{aligned}$$

(4)

In summary, the augmented GP approach replaces three existing terminals (${\text {PT}}$, ${\text {NPT}}$ and ${\text {WINQ}}$) with equivalent terminals that incorporate information about future machine breakdowns. The existing terminals are related to the processing times of the jobs waiting on the shop floor, where repair times need to be added onto the processing times if we expect the jobs to be interrupted by machine breakdowns. By doing this, we expect the GP rule to be able to use the “actual” processing times of the jobs to make better decisions on what job should be processed next by a machines during decision situations.

3.3 Reactive GP Terminals

Reactive machine breakdown terminals are added to the GP terminal set described in Table 1 and incorporate information about current machine status. As the two terminals incorporate informations about the potential wait time of a job waiting at a machine for the next machine it visits, they are investigated separately. The two terminals being investigated are the repair time remaining next machine terminal (${\text {RTR}}$) and the minimum wait time next machine terminal (${\text {WT}}$). The two reactive GP terminals may allow rules to make better decisions by prioritising jobs with low expected wait time compared to jobs with high expected wait time. This may lead to jobs spending less time waiting at busy machines, and the evolved rules may generate higher quality schedules. The GP approach that incorporates the ${\text {RTR}}$ terminal is denoted as GP-${\text {RTR}}$, and the GP approach that incorporates the ${\text {WT}}$ terminal is denoted as GP-${\text {WT}}$.

Repair Time Remaining Next Machine (RTR): The repair time remaining next machine ${\text {RTR}}$ returns zero if a job $j$ waiting at a machine at time $t$ is currently on its last operation or the next machine $m'$ visited by $j$ is currently not broken down. Otherwise, given that machine $m'$ broke down at time $b_t^{m'}$ and the repair time is $r_t^{m'}$, the value given by ${\text {RTR}}=b_t^{m'}+r_t^{m'}-t$.

Minimum Wait Time Next Machine (WT): The minimum wait time next machine ${\text {WT}}$ returns the earliest time that the machine to be visited by job $j$ next becomes available. If the current operation of $j$ is the last operation before completion, then ${\text {WT}}$ returns zero. In addition, if the next machine $m'$ that job $j$ visits is currently not busy and is not broken down, i.e., is completely available, then ${\text {WT}}$ returns zero. Otherwise, the ${\text {WT}}$ returns the duration of time required for machine $m'$ to be available. If machine $m'$ is currently processing a job $j'$ or is broken down with an interrupted job, then it returns the actual work remaining ${wr}'_{m'j'}$ which is given in Eq.  (4). Otherwise, if the $m'$ is broken down and a job was not interrupted by the machine breakdown, ${\text {WT}}$ returns the remaining repair time of machine $m'$ as given by the terminal ${\text {RTR}}$.

4 Experimental Design

This section describes the setup used to evaluate the different GP approaches to tackle the DJSS-MB. To evaluate the machine breakdown GP approaches, a simulation model that is slightly modified from existing simulation models in the literature [9, 10] is used to both evolve and evaluate the evolved rules. Afterwards, we provide the parameter used by the GP approaches.

4.1 Dynamic Simulation Model with Machine Breakdown

Discrete-event simulations are the most prominent method of generating dynamic JSS problem instances [5, 6]. In a discrete-event simulation, the dynamic events such as the job arrivals and the machine breakdowns are stochastically generated from a set of parameters. A simulation configuration is the set of parameters required, along with a seed value, to generate a dynamic JSS problem instance. In a dynamic JSS problem instance, there are $M=10$ machines on the shop floor. The problem instance has a “warm-up” period of 500 jobs, where the first 500 jobs completed do not contribute towards the objective. The simulation is terminated after 2500 jobs are completed, and the objective function value is calculated from the 2000 jobs completed after the warm-up phase. The job arrivals times follow a Poisson process with arrival rate $\lambda =\rho \,\times \,\mu \,\times \,p_M$. In the equation, $\rho$ is the utilisation rate, $\mu$ the mean processing time, and $p_M$ the mean number of job operations to machine ratio. Utilisation rate ($\rho$) is the expected proportion of time the machines are spent processing job operations, and $\rho = 80\%$ for all problem instances. If the utilisation rate plus the machine breakdown level is too high, it is very likely that the shop will be unstable [11], i.e., job arrival rate is greater than the rate at which the shop floor can process them. Therefore, $80\%$ utilisation rate is used instead of higher utilisation rates used in the literature (e.g. $90\%$ or $95\%$ [4, 9]) to accommodate for the high level of machine breakdown used by the simulation model (described below). The mean processing time ($\mu$) is used in a uniform distribution with the interval $[1,2\mu -1]$ that the jobs’ processing times follow, and $\mu =25$ for all problem instances. The mean number of job operations to machine ratio ($p_M$) is the expected number of machines that a job will visit divided by the total number of machines. The number of operations a job has follows a uniform distribution in the interval [2, 10], i.e., the minimum and the maximum number of operations that a job can have is 2 and 10 respectively. Therefore, the expected number of operations is 6 for a job arriving on the shop floor and $p_M=0.6$ for all problem instances. In addition, a job’s weight has the value of 1, 2 or 4 with $20\%$, $60\%$ or $20\%$ probabilities respectively. Given a job $j$’s arrival time $r_j$, total processing time $\sum _{i=1}^{N_j} p_{ij}$ and the due date tightness simulation parameter $h$, the due date of job $j$ is $d_j= r_j+ h\times \sum _{i=1}^{N_j} p_{ij}$.

For generating machine breakdown events, the inter-breakdown times of the machines follow an exponential distribution, and the expected breakdown rate is given by $\eta =r_t/\pi -r_t$. In the equation, $\pi$ is the breakdown level and $r_t$ is the machine repair time. The breakdown level is the expected proportion of time for the machine to be broken down over the course of the simulation, and varies between the different simulation configurations used to generate the problem instances. For a problem instance the machine repair time is the same across all machines for a problem instance.

The dataset parameters for generating job arrivals and machine breakdowns are shown in Table 2. First, the simulation configurations have the possible breakdown levels $\pi =0\%$, $2.5\%$, $5\%$, $10\%$, or $15\%$ for a simulation configuration. Second, fixed repair times for the machine breakdowns are either $r_t=37.5$, 137.5, or 262.5 for a simulation configuration. These parameters were selected after running the benchmark GP approach on different breakdown levels and durations of repair times as part of a preliminary experiment. The simulation configuration consists of a combination of the dataset parameters, which means that there are $3 \times 5 \times 2 = 30$ different simulation configurations available in the dataset. We use the simulation configuration with $\pi =15\%$, $r_t=262.5$ and $h=3$ to generate the training problem instances. In addition, a different seed is used with the training simulation configuration every generation during the GP process, resulting in different dynamic JSS problem instances being used every generation.

Table 2. Dynamic JSS parameter settings

4.2 GP Parameters

The GP parameters are used by the GP approaches are shown in Table 3. The GP parameters are the same as the parameters that are same as the ones used by Park et al. [10] in their investigation into GP approaches for a DJSS-MB, which allows our benchmark GP approach to be consistent with the GP approach that was used during their investigation.

Table 3. GP parameter settings

5 Experimental Results

In this investigation, we first carry out a performance evaluation of the GP approaches. The performance evaluation first compares the GP approaches and how consistently they can evolve high quality dispatching rules for the dynamic JSS problem, i.e., measures the effectiveness of the GP approaches. This is done by evolving a set of rules for each approach and applying them over the dynamic JSS simulation model. Afterwards, the best rules are extracted from the sets of evolved rules for the GP approaches and compared individually to determine whether an individual machine breakdown rule can outperform an evolved rule generated by the benchmark GP approach. Finally, we carry out a structural analysis of the best rules evolved by the machine breakdown GP approaches to find out the useful properties from the evolve rules.

5.1 Performance Evaluation

For the performance evaluation, each GP approach is applied to a training set (described in Sect. 4.1) thirty times to evolve thirty independent rules. Afterwards, each of the rule is applied to the dynamic JSS simulation model as follows.

Performance Measure: First, an evolved rule $\omega$ is run multiple times over each simulation configuration in the simulation model. A single run consists of a seed value and a simulation configuration, which are used to generate a dynamic JSS problem instance. The rule is then applied to the problem instance and generates a schedule, which has a MWT objective value. Afterwards, the subsequent runs over the simulation configuration use unique seeds so that new problem instances are generated from the same simulation configuration. In other words, given a simulation configuration sim and rule $\omega$, schedules with MWT values ${Obj}(\omega ,\gamma _{(sim)1})$, ..., ${Obj}(\omega ,\gamma _{(sim)30})$ are generated by the rule for the given simulation configuration. These are used slightly differently for the rule set evaluation and best rule evaluation, which are described below.

Rule Set Results: In the rule set evaluation, the MWT values ${Obj}(\omega ,\gamma _{(sim)1})$, ..., ${Obj}(\omega ,\gamma _{(sim)30})$ generated by a rule $\omega$ for a simulation configuration sim is averaged out to obtain the “performance” $Perf$ of the rule over the simulation configuration, i.e., $Perf(\omega )=\frac{1}{30}\sum _{i=1}^{30} {Obj}(\omega ,\gamma _{(sim)i})$. The rule performances are then used to compare between the different sets of rules evolved by the GP approaches.

The results of the performance evaluation is shown in Table 4. In the table, $\langle \pi , r_t, h\rangle$ denotes that the simulation configuration has the respective breakdown level $\pi$, repair time $r_t$, and due date tightness $h$. In addition, each entry $\mu \pm \sigma$ is the mean ($\mu$) and standard deviation ($\sigma$) of the performance $Perf$ of the rules for the simulation configuration respectively. If a set of GP evolved rules that use the machine breakdown terminals is significantly better than the set of benchmark GP rules for a simulation configuration by satisfying the two sided Student’s t-test at $p=0.05$, then the particular entry is highlighted.

Table 4. Comparison of the rule sets evolved by the GP approaches over the simulation configurations. Rules are evolved from $\langle {0.15,262.5,3}\rangle$.

Although the differences are not significant, the results show that the three machine breakdown approaches (GP-${\text {Aug}}$, GP-${\text {WT}}$ and GP-${\text {RTR}}$) have slightly better performances than the benchmark GP for some simulation configurations. In particular, the GP-${\text {WT}}$ rules have slightly better performances for all simulation configurations than the benchmark GP rules. In addition, the GP-${\text {RTR}}$ rules have slightly better performance than the benchmark GP rules for most simulation configurations except configurations $\langle {0,37.5,5}\rangle$ and $\langle {0.15,37.5,5}\rangle$. Finally, the results of the comparison between the GP-${\text {Aug}}$ rules and the benchmark GP rules is most mixed, where GP-${\text {Aug}}$ rules are slightly better or worse than the benchmark rules on roughly the equal number of simulation configurations. However, due to the lack of statistical significance, no significant conclusions can be drawn on whether the machine breakdown GP approaches is more consistent in evolving higher quality dispatching rules than the benchmark GP approach. However, by analysing the rules further, it may be possible to gain a better understanding of how GP can be applied effectively to the machine breakdown problem.

Best Rule Results: The best rule from each GP approach are compared against each other after the performances of the rules are compared. The best rule is defined to be the rule that has the lowest average performance values over all the simulation configurations out of the evolved rules. The best rules are then compared on each simulation configuration by the MWT values from the generated schedules. In other words, best rule comparison uses the results ${Obj}(\omega ,\gamma _{(sim)1})$, ..., ${Obj}(\omega ,\gamma _{(sim)30})$ from the rules being applied to the 30 problem instances generated by each simulation configuration sim. The results of the best rules being applied to each simulation configuration is shown in Table 5, where each entry $\mu \pm \sigma$ is the mean ($\mu$) and standard deviation ($\sigma$) of the MWT values generated by the best rule after being applied to 30 independent problem instances generated from the simulation configuration.

Table 5. Comparison of the best rules over the simulation configurations.

The best rules from the machine breakdown GP approaches show greater difference in the performance to the best rule from the benchmark GP approach. The best machine breakdown GP rules are significantly better than the best benchmark GP rule for certain simulation configurations, e.g., all three machine breakdown GP rules perform better than the GP rule for the $\langle {0.15,262.5,3\rangle }$ simulation configuration. Therefore, it is likely for GP approaches with the machine breakdown terminals to evolve high quality individual rules than the benchmark GP approach.

5.2 Rule Analysis

The evolved machine breakdown GP rules are analysed further by carrying out a qualitative analysis based on the structures of the evolved rules. First, the best rules are simplified to remove any redundant branches (e.g. if an ${\texttt {if}}$ will only return the “if” sub branch, then the ${\texttt {if}}$ operator is replaced with the “if” branch) before analysing the structures of the rules. The simplified best rules for GP-${\text {Aug}}$, GP-${\text {WT}}$, and GP-${\text {RTR}}$ are shown in Fig. 1a, b and c respectively.

Fig. 1.

The structures of the best rules found by the GP approaches.

An important observation from the best rules evolved by GP-${\text {WT}}$ and GP-${\text {RTR}}$ is the lack of machine breakdown terminals that make up the best rules. The best rule from GP-${\text {WT}}$ has no occurrence of the ${\text {WT}}$ terminal that is incorporated into the terminal set, and the best rule from GP-${\text {RTR}}$ has one occurrence of the ${\text {RTR}}$ terminal. Therefore, it may be the case that the machine breakdown terminals do not directly contribute towards the qualities of the final evolved rules. Instead, the machine breakdown terminals may facilitate the evolution of good GP rules, and are discarded from the best GP individuals near the end of the GP process. This may explain the lack of machine breakdown terminals in best GP-${\text {WT}}$ and GP-${\text {RTR}}$ rules, but why the best rules generally perform better than the best benchmark rule In addition, it may also explain why GP-${\text {WT}}$ and GP-${\text {RTR}}$ rules also perform slightly better than the benchmark GP rules.

For the best rules from the GP approaches, the method in which the non-machine breakdown related terminals are combined may also be a factor in the effectiveness of the rules. These include the frequent occurrence of important terminals such as the job’s weights and processing time in the best evolved rules. Intuitively, important jobs with short processing time should be prioritised out of the jobs waiting at the available machine. However, in all three machine breakdown GP rules (and the best benchmark GP rule), there are many segments of the tree that form ${\text {DD}}/{\text {PT}}$, which indicates that the best rules prioritise jobs with high due date and low processing time. This is contrary to the expectation that jobs with low due date (i.e. jobs that are more urgent) should be prioritised first. A possible explanation is that the due date terminal is time variant, i.e., expected due dates of jobs steady increases with the duration of the simulation. On the other hand, the processing time terminal is time invariant, i.e., the expected processing times of jobs remains relatively the same over the whole duration of the simulation. Therefore, the relative differences in the due date between an urgent job and a non-urgent job waiting on a machine late in the simulation may not be as big as the differences in their processing time, due to the large due date values of both the urgent and non-urgent jobs. This may result in the due date of a job for long simulations being used as an arbitrary large value that can be combined with the processing time terminal using the protected  /  operator to form a composite that prioritises short processing times. Further experiments can be carried out to determine whether the same phenomenon occurs by replacing the processing time terminal with $1/{\text {PT}}$ terminal in future GP approaches.

6 Conclusions and Future Work

This paper is a very first piece of work that develops new machine breakdown GP terminals to improve the qualities of GP evolved rules for a DJSS-MB. The first set of GP terminals (called “augmented terminals”) replace existing processing time related terminals (${\text {PT}}$, ${\text {NPT}}$ and ${\text {WINQ}}$) with equivalent terminals that take potential machine breakdown into account. The second set of GP approaches (called “reactive terminals”) add new terminals (${\text {RTR}}$ and ${\text {WT}}$) that gives information on current state of the shop floor. The machine breakdown GP approach does not evolve significantly better rules overall, but the best rules evolved by the machine breakdown GP significantly outperform the best rule evolved by the benchmark GP. The analysis shows very interesting results and insights, where the machine breakdown terminals appear infrequently in the best rules for GP-${\text {WT}}$ and GP-${\text {RTR}}$. Hypotheses have been raised to explain why this is the case, and further work will be needed in this direction. We hope that this work can attract more people to start their work in this direction in the near future.

For the future work, further analysis based on the behaviours of the evolved rules will be carried out. Analysis of evolved rule behaviours in JSS problems have been carried out in the literature [17, 18], and further investigation into the behaviours of rules evolved for DJSS-MB may allow better machine breakdown specific approaches to be developed. In addition, the relation between the utilisation rate of job shop scheduling problems and the machine breakdown level will be explored further by analysing rule behaviours in different shop environments. For example, a rule evolved for shop with low utilisation rate and high machine breakdown will be compared against a rule evolved for shop with high utilisation rate and low machine breakdown. This relation may help us develop further insight into machine breakdowns and how the properties of the shop changes with such disruptions.