Automatically evolving preference-based dispatching rules for multi-objective job shop scheduling

Heuristic selection methods search for a good solution by selecting existing heuristics. Instead of searching in the solution space, they operate on a set of low-level simple heuristics. In the scope of production scheduling problems, the low-level heuristics are usually represented by dispatching rules. These rules are used to assign a priority index to each job waiting in the queue. Hence, whenever a machine becomes idle, the job with the highest priority is selected to be processed next on that particular machine. One well-known and frequently investigated group of dispatching rules are simple priority rules, such as the earliest due date (EDD). For a comprehensive review of dispatching rules, the reader is referred to the surveys by Panwalkar and Iskander (1977) and Blackstone et al. (1982).

Dorndorf and Pesch (1995) proposed a GA to perform a high-level search for a sequence of dispatching rules to minimize the makespan for job shop scheduling problems. For the job sequencing decision, they consider a set of 12 simple priority rules, including the shortest processing time. Experimental results showed that the developed heuristic performs better than two previously published heuristics.

Vázquez-Rodíguez and Petrovic (2010) proposed a heuristic selection HH method to solve MO job shop problems. They aimed to overcome the sensitivity of their previously developed dispatching rule-based GA to the number of operations that each dispatching rule handled. The authors proposed using the well-known EA, NSGA (Non-dominated Sorting Genetic Algorithm)-II, as the high-level algorithm. The developed approach simultaneously searches for the best sequence of dispatching rules and for the number of operations to be handled by each dispatching rule. The authors tested their approach on different MO job shop problems, with a resulting improvement in the hyper-volume on all instances relative to their previous HH and also compared with other conventional GAs.

Hart and Ross (1998) introduced an HH to solve dynamic job shop scheduling problems. A GA was proposed to search for optimal solutions by iteratively selecting a simple heuristic out of a predefined set of 12 suitable priority rules at each step of schedule generation. In addition to the previously published HH, the developed approach is novel in that the genome encodes not only the choice of heuristic, which is used to select the next job out of the set of available jobs, but also the choice of algorithm to be used to generate the set of jobs. An experiment was carried out for different benchmark problems as well as for a variety of well-known objectives, such as minimization of the weighted flow time. The results showed that their algorithm outperformed other state-of-the-art approaches in most of the test instances. Moreover, the authors found that decisions in the early stages of the schedule generation process have a higher impact on the schedule’s performance than those in later stages.

Norenkov and Goodma (1998) developed an HH (or heuristic combination method (HCM), as they called it) to solve multi-stage flow-shop scheduling problems. They introduced an implicit representation of schedules on the chromosome, where each stage of the genes does not represent the number of a job or machine but instead the number of a heuristic to be used to select a job at that stage of generating a schedule. The hybrid algorithm they proposed is a combination of a GA with an EA. They tested different settings of their algorithm on a well-known benchmark scheduling problem. The results showed that their algorithm is superior to the individual use of simple scheduling heuristics.

Vazquez et al. (2007) discussed the principles of the search mechanism of HHs. They distinguished the search spaces between the associated and the original search space. The associated search space is defined by the combined set of dispatching rules, while the original space contains the set of feasible schedules. The authors showed that the size of the associated space depends on the number of decisions and the number of dispatching rules. Moreover, they introduced the notation of a decision block that is denoted as a set of decisions containing the same low-level heuristic and thus which can be treated as a single decision. The size of the associated space can be reduced by generating decision blocks. An experiment showed that the quality of the result for a given number of solutions used as stopping criteria was sensitive to the size of the decision blocks. Therefore, the design of the associated space was proven to have a relevant impact on the performance of an HH.

Rodríguez et al. (2007) developed a meta-HH method to solve flexible flow-shop problems. To schedule the jobs, for the first stage they applied a meta-heuristic, and for the subsequent stages they selected from a set of simple scheduling heuristics by using a GA. They tested and compared the performance to the individual simple heuristics for different test instances and regarding different objectives. The results showed that the developed approach performed better than the simple heuristics for most of the tested objectives, and especially for all objectives together. Furthermore, the authors discussed the interaction of heuristics to examine whether some of the individually poorly performing simple heuristics could be discarded from the set. A simple example proved that a combination of poorly performing heuristics could lead to better performance than the combination of well-performing heuristics.

Ochoa et al. (2009) carried out a landscape analysis of the heuristics search space to study the properties of the heuristics search spaces. Moreover, they formalized a notion of HH landscapes. A landscape analysis is conducted for different types of flexible flow-shop problems solved by a dispatching-rule-based HH. The main results revealed that the studied landscapes contain a large valley structure, which means they have a globally convex structure. Furthermore, the landscapes showed a large number of local optima and the existence of plateaus, where many local optima are located at the same level in the search space. In conclusion, the study found the HH search spaces to be “easy” to search.

Yu et al. (2020) examined bi-objective flexible flow-shop scheduling problems with the aim of minimizing the total tardiness and the total setup time. Using EA at the high level, the authors proposed two different HH approaches. First, they solved the problem a priori by transforming it into a single-objective optimization (SOO) model using the DM’s preferences for a scalarization of the objective function. In their second approach, they solved the problem a posteriori, meaning that they used the well-known NSGA-II algorithm to find a set of non-dominated solutions from which the DM can choose an appropriate solution after running the program. A numerical experiment was carried out, revealing that both methods have some drawbacks. The challenge in the a priori method is the correct determination of user preferences, which are usually difficult to elicit from the DM and generally imprecise due to a lack of knowledge about possible trade-offs or imprecise information. To overcome this issue, the a posteriori approach can be used to present a set of different non-dominated solutions to the DM, who can then have a deeper understanding of the solution space and choose the solution that best fits their preferences. Nevertheless, the authors identified that the Pareto front observed by the NSGA-II may be worse in certain specific regions compared with some of the single decoding algorithms. The reason for this lies in the compromise between the two parameters “width” and “depth” that needs to be chosen to achieve an efficient allocation of the computing resource.

Lin et al. (2017) proposed an HH to solve distributed assembly permutation flow-shop scheduling problems. At the high level, the authors employed a backtracking search algorithm to operate on a set of 10 simple low-level heuristics in order to minimize the makespan. They also applied an efficient encoding and decoding procedure to generate feasible schedules. The effectiveness and efficiency of the developed algorithm were then evaluated on small and large benchmark test instances. The results revealed the superiority of their algorithm over other state-of-the-art methods, where for many of the investigated instances a new best solution could be found.

Song and Lin (2021) investigated the distributed assembly permutation flow-shop scheduling problem with sequence-dependent setup times. At the high level of the introduced HH algorithm, they proposed a GP algorithm to operate on a set of 10 predesigned low-level heuristics. The developed algorithm iteratively evolves to new heuristic sequences, which are then applied to the search space, in order to find successively better solutions. Moreover, they embedded simulated annealing into the low-level heuristics to enhance the local search performance. Experimental results on a total of 540 benchmark test instances demonstrated the effectiveness of the proposed algorithm, where for 333 cases a new best solution could be obtained.

Heuristic generation methods are used to search for a new heuristic that is generated from the components of existing heuristics. Compared with heuristic selection methodologies, where the search space contains a set of simple dispatching rules, the search space of heuristic generation approaches includes a set of terminals and functions. Terminals of a production scheduling problem typically represent important parameters, such as the due date and processing time. Functions that are often used include the four basic arithmetic operators addition, subtraction, division, and multiplication.

An early heuristic generation approach to solving a single-machine shop was introduced in Dimopoulos and Zalzala (2001). The aim was to evolve a dispatching rule that challenged human-made dispatching rules. The authors proposed to employ GP for the evolution of a new dispatching rule that would be responsible for the sequencing of jobs. The developed method is applicable to any other scheduling problem, assuming that the training phase of the rule is carried out correctly. Moreover, a combination of the GP with local search algorithms was presented to increase the performance of the algorithm. Nine different dispatching rules were evolved from nine different training sets. The evolved heuristics were then compared with other previously developed algorithms, with the result that in most cases, the developed HH was able to find a dispatching rule that outperformed the former.

Geiger et al. (2006) presented a system to automatically learn effective dispatching rules for a given environment. A combination of an evolutionary learning mechanism with a simulation model of the industrial facility of interest was proposed to evolve and evaluate the rules in an iterative manner. An experiment was carried out wherein the training set size was identified as a critical parameter. Different training set sizes were tested, and a large number were revealed to be worse in terms of the generality of the identified rule. It was observed that 10 instances in the training set and the test set led to robust dispatching rules. The scalability to other shop configurations was also demonstrated, and an example was illustrated.

Abednego and Hendratmo (2011) proposed a GP-HH to evolve a scheduling priority rule in order to solve dynamic production scheduling problems for a single-machine shop configuration. The aim was to minimize the mean tardiness and the mean flow time. The authors proposed a weighted-sum approach to solving a bi-objective optimization problem, where the weights are assumed to be equal for both objectives. Applying the developed approach to a real-world problem from the metal industry revealed the efficiency of their method. Results showed that their approach outperformed six human-made heuristics under comparison for each of the five investigated machines.

Jakobović et al. (2007) developed an HH that evolves scheduling heuristics for a parallel machine environment. The authors proposed the use of GP to generate a suitable priority rule. A priority rule based on 100 test cases was evolved and then tested and compared with other existing and well-known scheduling heuristics. In their experiment, different cases regarding performance criteria and static or dynamic job arrivals were tested. The results showed that the authors’ evolved scheduling heuristic outperformed the traditional approaches in most cases.

Masood et al. (2017) investigated MO job shop scheduling problems. They proposed the use of GP and the NSGA-III algorithm to evolve efficient dispatching rules. The authors also found that the uniform distribution of the reference points, as is usually applied by the NSGA-III, is not perfectly tuned to the discrete and nonuniform Pareto front in job shop scheduling problems. Therefore, the authors introduced a reference point adaption mechanism based on particle swarm optimization to reduce the useless reference points and improve the performance. Experimental results showed that the developed adaption of the reference points led to a significant reduction in useless reference points, as well as improved performance in terms of hyper-volume and inverted generational distance of MO job shop scheduling problems.

Ho and Tay (2005) developed a GP to generate effective dispatching rules with the aim of minimizing the total tardiness of flexible job shop problems. By combining terminals such as the release date of a job, with functions such as addition, a GP tree can be identified. To generate good dispatching rules to solve a particular problem, first, training needs to be carried out. This is why this approach applies to a large variety of scheduling problems. An experiment was carried out where five generated dispatching rules were compared with selected human-made dispatching rules.

Tay and Ho (2008) extended their previous work to multiple objectives. The MO problem was transformed into a single-objective problem by using the weighted-sum approach, without taking the DM preferences into account. An experiment was presented in which dispatching rules were generated and compared with other human-made rules. The performance was first evaluated for each objective individually, and then the overall performance with respect to the weighted sum was shown. Moreover, a sensitivity analysis was carried out. One of the main conclusions identified by the authors was the need for incorporation of preference information in the MO approach in order to efficiently find a “good” compromise solution.

Pickardt et al. (2013) proposed a two-stage HH to solve a complex dynamic job shop scheduling problem. The aim is to generate a set of work-center-specific dispatching rules in order to minimize the mean weighted tardiness. In the first stage, a GP algorithm was used to evolve a problem-specific composite rule from basic job attributes. In the second stage, the evolved rules were assigned to the work centers by applying an EA. The developed two-stage approach was then tested and compared with the two developed HHs individually and some benchmark rules. The test instance was a real-world problem from the semiconductor industry. Results showed that the two-stage approach outperforms the GP and EA individually as well as any of the benchmark rules under investigation. Moreover, the authors carried out a sensitivity analysis proving the robustness of the resulting rules sets against different operational variables such as the arrival rate of jobs.

Park et al. (2018) investigated and carried out a systematic analysis of four popular ensemble combination schemes for GP-based HH approaches to solve dynamic job shop scheduling problems. Recent research has shown that ensemble GP-HH algorithms are more robust than traditional approaches for evolving single dispatching rules. Moreover, the authors established new measures to evaluate the behaviors of evolved ensembles. Based on these measures, an experiment was carried out to test four different combination schemes in order to minimize the weighted tardiness. For that purpose, the authors used an existing discrete-event simulation model proposed by Hunt et al. (2014). The main results of their study revealed that the linear combination scheme generally performed better than the other approaches under investigation and that the weighted schemes led to worse results than the unweighted ones.

Zhou and Yang (2019) proposed four MO HHs based on GP to solve dynamic flexible job shop scheduling problems to minimize the mean weighted tardiness, maximum tardiness, and mean flow time. The developed method simultaneously evolves job sequencing and machine assignment decision rules. For every generation in the population, a discrete-event simulation is used for evaluation with respect to the aforementioned performance measures. Based on that fitness evaluation, the NSGA-II or Strength Pareto Evolutionary Algorithm 2 (SPEA2) is then applied, and a new population is consequently built. Experimental results confirmed the efficiency, where the developed approaches outperformed 320 human-made scheduling techniques in most of the test scenarios. Moreover, the authors demonstrated that their method finds the Pareto front more comprehensively than the compared techniques.

As an extension to the previous work, Zhou et al. (2020) investigated different coevolutionary techniques, such as the cooperative coevolution GP, and introduced a surrogate simulation model to improve the fitness evaluation process. The main focus of this paper was to examine the impact of simulation configuration on the performance of the proposed HH algorithms. As one of the main experimental results, the authors showed that the simulation parameters of the discrete-event simulation model, such as the warm-up time, have a significant impact on the test performance in the evolutionary generation of scheduling policies. Furthermore, the implementation of a surrogate evaluation model led to a relevant improvement of the performance of evolved scheduling policies as the convergence speed of the algorithm was accelerated. Finally, the effectiveness and robustness of the proposed method were proven by carrying out a comparison experiment and sensitivity analysis.

Despite the existence of numerous publications on HH algorithms for solving different shop configurations of production scheduling regarding a single objective, there are very few approaches considering the optimization of multiple objectives simultaneously. MOO problems usually have no unique optimal solution; instead, they contain a set of mathematically incomparable solutions, so-called Pareto optimal solutions. To find the optimal solution among them, DM preference information is required. In MOO literature, there exist different ways of approaching this challenge. Some methods ask the DM to articulate the preferences prior to the actual optimization task. Other methods aim to determine the best possible representation of the Pareto front to enable the DM to choose the most appropriate solution from a set of non-dominated solutions after running the optimization task. Furthermore, there is another category of so-called interactive procedures, which contain an iterative exchange of information with the DM to find a solution that best corresponds to their preferences. To the best of the authors’ knowledge, there is currently no method that interactively guides the DM through the decision-making process by iteratively taking into account their preferences in order to evolve appropriate dispatching rules to solve MO job shop scheduling problems. Some of the reviewed works applied MO non-sorting GAs, such as the NSGA-II or NSGA-III, to find a good approximation of the Pareto front (Masood et al., 2017, Vázquez-Rodríguez & Petrovic, 2010, Yu et al., 2020, Y. Zhou & Yang, 2019). Another way to approach MO scheduling problems through the use of HH that was found in the literature is to transform the objective functions into a single-objective function by linear scalarization techniques, such as the weighted-sum approach (Yu et al., 2020; Tay & Ho, 2008; Abednego & Hendratmo, 2011). A classification of the reviewed MO articles with respect to their type of solving method is summarized in Table 2. Nevertheless, none of the reviewed articles addressed the challenge of how to incorporate the DM’s preferences into the solving process of MO production scheduling problems. To enhance the applicability of MO HH approaches for real-world cases, the development of an interactive MOO method thus represents a promising area of research to find the “best” compromise solution according to the DM’s preferences. This paper contributes to closing this knowledge gap by developing an interactive MO-HH-GP framework based on the reference point method. Our decision support system (DSS) aims to guide the DM through the whole decision-making process, where the interactive aspect of our procedure enables the efficient exploration of the objective space and the identification of a variety of non-dominated solutions.

MOO models represent an extension of SOO models, where instead of one objective function, a set of \(q\geqslant 2\) objective functions \(f_1(x),\ldots , f_k(x), \ldots , f_q(x)\) are included. Each objective function can individually embody either a maximization or minimization problem. Without loss of generality, we assume each objective to be simultaneously minimized in the remainder of this paper. Supposing we consider a problem containing o decision variables, the o-dimensional decision vector \(x=(x_1,\ldots ,x_u,\ldots ,x_v)\) represents a feasible solution in the decision space \(\mathbb {R}^u\), which is denoted by X. For each decision vector x, there exists a representation in the feasible region F of the objective function space \(\mathbb {R}^q\) in the form of a point \(f=\big (f_1(x), \ldots , f_k(x), \ldots , f_q(x)\big )\). The mathematical formulation of a MOO model where all objective functions are to be minimized is presented in (1).

HHs typically make use of EA as the high-level algorithm to carry out stochastic and iterative search procedures. Instead of searching directly in the search space of solutions, as is the case with most metaheuristics, they operate in a search space of heuristics or heuristic components (Burke et al., 2003; Ross, 2005). In this paper we will focus on the latter. The general procedure or conventional EAs are inspired by natural phenomena and start with a randomly or heuristically generated set of candidate solutions (individuals) that represents the initial population. During each iteration (generation), the individuals are decoded in order to evaluate their performance (fitness). According to the Darwinian evolutionary theory survival of the fittest, solutions are probabilistically selected for future generations based on their performance. Subsequently, new solutions (children) are generated by recombining (crossover) two of the selected solutions (parents) and/or adjusting an individual’s components (mutation). As in nature, where individuals increasingly adapt to their environment over generations, better solutions can be evolved with EAs, step by step, performing a variety of iterations. For an overview of different evolutionary-based algorithms and a detailed introduction, the interested reader is referred to Bäck (1996) and Eiben and Smith (2015). The evolutionary process is visualized as a cycle diagram in a simplified way in Fig. 1. For the implementation of the HH in this article, an extension of an evolutionary-based GA, the so-called GP, is used to automatically evolve dispatching rules that best meet the DM’s preferences. Therefore, the basic concepts of GP are introduced in the following.

The indices, parameters, and variables for the mathematical formulation of the MO job shop scheduling problem are denoted as follows:

For the problem at hand, a selection of the most common objectives in job shop scheduling problems represents the performance measures that are used to evaluate the fitness in the evolutionary generation of preference-based dispatching rules. The definition, an economical interpretation, and the mathematical formulation of the selected performance measures are provided in the following. Please note that the selection of the performance measures has no impact on the developed interactive MO-GP-HH framework since it is designed to work in a generic manner. However, a selection has been made to illustrate the functionality in the remaining sections of this article.

Inspired by Zeiträg (2021) and based on the main steps for a general interactive DSS for MOO defined by Miettinen et al. (2008), the proposed interactive MO-GP-HH procedure contains three main phases: initialization, exploration, and decision phase. The procedure will be briefly described in the following. For more details, interested readers are referred to Zeiträg (2021). In the first step of the procedure, a sample of reference points is generated to identify a set of non-dominated solutions that provides the DM a “good” overview of the non-dominated region and possible trade-offs between the competing objectives. For that purpose, several reference points can be determined over a uniform distribution on a hyperplane between the approximated ideal and nadir points (see, e.g., Figueira, Liefooghe, Talbi, & Wierzbicki, 2010). In the next step, a dispatching rule is evolved that minimizes the distance of its performance measures to the corresponding reference point’s values by running the GP-HH-based dispatching rule generator (see Sect. 5.2). Operating on a processor with multiple cores, the GP-HH-based dispatching rule generator can be run in parallel for multiple reference points (Figueira et al., 2010). In the final step of the initialization phase, the obtained solutions are presented to the DM, who then can decide whether they want to explore new solutions or whether one of the identified solutions already satisfies the their aspirations regarding all performance measures simultaneously. If further exploration is desired, the interactive procedure continues with the exploration phase. In the first step of the exploration phase, the DM has the ability to select from the two following exploration options: For both of the provided options, the DM first needs to choose a solution out of the set of generated non-dominated solutions from the previous phase. The DM can then decide to either add an aspiration for a particular performance measure or explore the surrounding of the investigated solution. Assuming a solution performs well in all dimensions except one, the DM can try to “tune” the unsatisfying performance measure by adding an aspiration level and running the GP-HH-based schedule rule generator again (see Sect. 5.2). Moreover, the DM can add an acceptance level if they notice that one of the performance measures of the selected solution exceeded a certain level of expectation and could therefore be debased to a defined limit. In a mathematical sense, the aspiration level represents an upper bound and the acceptance level is equal to a lower bound for minimization problems. The second exploration option provides the DM the opportunity to intensify the investigation of promising areas. This choice is particularly suitable for solutions whose performance measures correspond more or less to the DM preferences in all dimensions. Under predefined variation of the scaling coefficient vector of the ASF, new solutions can be found that are placed in the surrounding of the promising solution by running the GP-HH-based dispatching rule generator (see Sect. 5.2). The newly evolved dispatching rule(s) and its corresponding performance measures can be subsequently evaluated by the DM for both exploration options, while a solution can either be kept for further investigations or be discarded if its performance is not acceptable. The exploration process can be repeated until no further interaction is desired by the DM. The iterative exploration procedure enables the DM to identify solutions that could have been remained hidden with classical a priori or a posteriori methods. Furthermore, the interaction with the DM leads to a deeper understanding of trade-offs of objectives. This learning effect facilitates the identification and articulation of the DM’s preferences throughout the procedure. In the final phase of the interactive MO-GP-HH procedure, a decision must be made as to which of the obtained solutions (if any) best meets the DM’s preferences. Therefore, a pairwise comparison of all solutions is carried out, where in each iteration one of the compared solutions should be eliminated. The pairwise comparison is repeated until a single solution is left. The final solution is supposed to represent a “good” compromise between all the assessed competing objectives. If the DM is satisfied with the final solution, the interactive procedure is finished. Otherwise, the procedure can be restarted, and different solutions might be obtained by varying the parameters.

The actual optimization task takes place in the GP-HH-based dispatching rule generator. In a stochastic search procedure, new dispatching rules are iteratively evolved by an evolutionary mechanism. In the first step, an initial population is randomly generated based on certain parameters. This population includes a set of individuals, where each one of them represents a candidate solution. The fitness of each individual is then determined by executing a discrete-event simulation (see Sect. 5.3). Implementing the returned performance measures for each solution of the current population in the ASF results in the final fitness value of each individual. Solutions with a shorter distance to the values of the performance measures desired by the DM and with respect to the scaling coefficient vector are therefore rated with a higher level of fitness. According to the Darwinian concept of striving for genetic survival, the fittest solutions of the current population are selected in the next step. Through the implementation of crossover and mutation operations, new solutions are subsequently generated. The resulting individuals form a new population, whose individuals are again assessed for their fitness by executing the discrete-event simulation (see Sect. 5.3). This procedure is repeated until the number of defined generations has been reached. The solution with the best fitness is then passed back to the interactive MO-GP-HH procedure, where the performance measures achieved by the evolved rule can be interactively evaluated by the DM.

For evaluating the fitness of the individual dispatching rules generated in the evolutionary process, we propose the use of discrete-event simulation. Because of the inadequacy of analytical techniques such as the queuing theory (see, e.g., Blackstone et al., 1982), particularly for more complex shop configurations or under consideration of dynamic events, simulation has become the predominant method for evaluating scheduling problems and is thus the most common method in the literature.

In the proposed discrete-event simulation, the job shop problem at hand is first loaded with all the necessary information, such as the processing time of each operation or the due date of each job. For more detail on how the training and test instances are randomly generated, see Sect. 6.1. After collecting the necessary information, the simulation run can then start with the dispatching of operations. The priority index for each of the waiting operations is calculated by using the dispatching rule from the examined individual in its decoded form. As soon as a machine becomes idle, the operation with the lowest priority index is selected from the waiting queue. The respective machine is then blocked for other activities for the period of the processing time of the scheduled operation. When the processing time expires, the next operation of the respective job is released. Moreover, the machine returns to the idle state and is available for the next operation in the queue with the next-lower priority index. This procedure is repeated until all operations have been scheduled and all jobs have been completed. The performance measures defined in Sect. 4.2 are calculated and saved for the current simulation run. The simulation is repeated until the maximum number of defined simulation runs is reached. To calculate the fitness of the tested dispatching rule, the mean values of the performance measures of all simulation runs are finally determined and returned to the GP-HH-based dispatching rule generator. This module can then calculate the final fitness by inserting the performance measures into the ASF. In this context, the fitness value represents the distance to the observed reference point with respect to the weighted Chebyshev metric.

In job shop literature, there are many different sets of benchmark problems available that are designed to measure the performance of an optimization method (Taillard, 1993; Demirkol et al., 1998). Typically, the application of dispatching rules is known to be more effective and therefore more prominent for job shop scheduling problems in a dynamic environment. However, because of their lower complexity, it can make sense to first introduce newly developed algorithms on static job shop scheduling in order to analyze and validate their functionality (Masood et al., 2016). To evolve a dispatching rule that meets the DM’s preferences, we propose using a set of 10 randomly generated training instances for a medium-sized job shop environment that contains 15 machines and 20 jobs. Each job consists of 15 operations (one operation on each machine) which need to be processed for a given duration (processing time) and in a predefined order. The attributes of the jobs and operations for each instance are generated according to the procedure proposed by Taillard (1993). Therefore, each operation is randomly assigned to one of the machines, without allowing a machine to be revisited. The processing time for each operation follows a discrete uniform distribution between 1 and 99.

Since the original dataset developed by Taillard (1993) was designed to measure the makespan, the test instances do not include any due dates. To consider due date-based performance measures such as the total tardiness, we attach a due date for each job of the test instance using the due date assignment rule of Baker (1984):where parameter h indicates the due date’s tightness. A value of 1.3 is a typical practice in research (see, e.g., Kreipl, 2000, Masood et al., 2009, H. Zhou, Cheung, & Leung, 2017) and is therefore also applied in this study. Moreover, the release date \(r_i\) of all jobs \(i=1,\ldots ,n\) is assumed to be zero in Taillard’s instances, which means all jobs are ready to be processed from the beginning.

The aim of the proposed interactive MO-GP-HH procedure is to generate a dispatching rule that is able not only to reach a certain compromise between objectives on a particular set of training instances, but also to reproduce a similar compromise for problems that are likely to occur in future applications of the examined job shop environment. Therefore, another independent set of 10 randomly generated instances are used to test the evolved dispatching rule and compare its performance to other well-known dispatching rules, such as the earliest due date first (EDD) or the shortest processing time (SPT).

A summary of all parameters used to generate the training and test instances in the proposed MO-GP-HH framework is presented in Table 3.

The performance of a schedule might be influenced by a large number of operational parameters. Since the search space grows by an increasing number of terminals, their selection can be stated as a crucial process to ensure the efficiency of the proposed interactive MO-GP-HH framework. Moreover, the set of terminals should be kept sufficiently small in order to generate short and meaningful dispatching rules. Therefore, the most prominent and promising parameters for evolving effective dispatching rules from GP-HH literature (see, e.g., Branke et al., 2016) are chosen for application to the following experiment. The abbreviation and a brief description of the terminals are shown in Table 4. In addition, the terminals are categorized into job parameters, attributes that concern the work center, and global attributes.

As is common practice in the application of GP-HH methods, the function set of our experiment consists of the four basic arithmetic operators: addition, subtraction, multiplication, and division. Please note that the division function works as a protected division, which means that if the denominator is equal to zero, the value 1 will be returned. Otherwise, the result of the division of the two input values represents the output of the function. Furthermore, other mathematical operators such as “MIN” and “MAX” and logical operators such as “if-then-else (IFTE)” that have been revealed as viable functions when dealing with more complex performance measures such as tardiness are also included (Nguyen et al., 2017). Arity is set to 2 for all functions except for the “IFTE” function. The ternary operator requires three arguments, while the first value represents the condition. If the first argument is greater than or equal to zero, the second argument will be returned by the function and the third argument otherwise. An overview of the set of functions is given in Table 5.

Typical fitness functions in GP-HH scheduling methods include the performance measure to be optimized (for SOO, see, e.g., Dimopoulos and Zalzala (2001)), a scalarizing function of multiple performance measures (for a priori MOO, see, e.g., Tay and Ho (2008)), or multi-objective performance measures such as the hyper-volume ratio (for a posteriori MOO, see, e.g., Zhou and Yang (2019)). Since the proposed interactive MO-GP-HH framework is based on the concepts of the reference point method, the ASF (4) is used to calculate the fitness of a schedule. Therefore, the fitness of a schedule represents the maximum weighted deviation of the performance measures from a selected reference point. In general, the lower a schedule’s value for the ASF, the better its fitness.

The focus of our study is on validating the functionality of our developed interactive MO-GP-HH procedure to generate an effective dispatching rule that best meets the DM’s preferences rather than tuning its performance. Therefore, we propose selecting the most commonly used settings from the GP-HH scheduling literature (e.g., Zhou and Yang (2019); Pickardt et al. (2013); Dimopoulos and Zalzala (2001)). However, experiments could be carried out to tune the efficiency and effectiveness by optimizing the set of terminals and functions as well as the GP parameters. The GP parameter used in our experiment is shown in Table 6.

In the first step of the initialization phase, an approximation of the ideal and nadir points needs to be calculated. For that purpose, we use the GP-HH-based dispatching rule generator. Instead of evaluating the fitness based on the ASF, we propose directly evaluating a schedule’s fitness by each of the performance measures individually. The program automatically starts six individual GP-HH runs to search, for each performance measure, one dispatching rule that minimizes and another dispatching rule that maximizes the corresponding performance measure. The same GP parameters (see Sect. 6) are used for each run. The results aim to express a good approximation of the ideal and nadir points. Please note that these points do not represent an ideal or nadir solution to the actual scheduling problem, but rather an approximation of the best- and worst-performing dispatching rule evolved by the GP for a certain performance measure. Since the developed MO-GP-HH framework operates exclusively in the space of a dispatching rule’s components, it is obvious that the lower and upper bounds are portrayed in the same space. The solutions of the approximated ideal and nadir points can be seen in Fig. 5.

To generate an initial set of solutions that represent a wide range of the Pareto front, a uniformly distributed set of reference points will be placed on a hyperplane between the approximated ideal and nadir points. This phase aims to provide a sufficient overview of different alternatives to familiarize the DM with possible trade-offs and guide the DM’s search toward promising regions. Moreover, a selection of settings can already focus the search on a preferred area in this step. On the one hand, the DM can determine the position of the hyperplane between the ideal and the nadir point, a value of 0.5 being suggested by default. On the other hand, due to the range of performance measures presented to the DM, undesirable areas can be excluded when searching for possible solutions. In our experiment, the DM decided to place the hyperplane slightly closer to the ideal point by choosing 0.4. Moreover, the DM desired not to limit the search space in the first step and therefore to search the whole objective space for potential solutions. Figure 5 shows the results from the first step of the initialization phase as well as the selection of the fictional DM for the generation of the first sample of potential solutions.

After determining the settings, the program automatically evolves a dispatching rule for each of the reference points by minimizing the distance with respect to the ASF. The weighting vectors are assumed not to favor any of the performance measures. Therefore, a normalization based on the approximated ideal and nadir points is proposed:where \(f_k^{nad}(x)\) represents the approximated nadir and \(f_k^{\star }(x)\) the approximated ideal solution for objective \(k=1,\ldots ,q\). The observed solutions are then checked for their efficiency. Since we are using an EA to evolve a good solution for the problem at hand, we cannot guarantee that this solution represents the exact optimum. Some of the obtained solutions might be dominated by others. Therefore, a simple comparison is carried out to identify the dominated solutions and discard them from the set of potential solutions. Please note that choosing for a larger number of generations or individuals in the population could reduce the likelihood of dominated solutions appearing. Finally, the relative performance of each of the remaining solutions based on their approximated ideal and nadir points is presented to the DM in the form of a bar chart (see Fig. 6). First impressions of possible trade-offs can be elicited by the DM, and promising solutions can be selected for further exploration.

In this phase of the interactive procedure, the DM can select one of the previously presented solutions and can either limit the solution space by adding constraints in the form of aspiration levels or search the surroundings of the selected solution in order to find more suitable dispatching rules. Several iterations were carried out by the fictional DM, and a selection of two of them, one for each option, will be illustrated in the following.

The aim of the last phase of the interactive MO-GP-HH procedure is to identify the solution that best meets the DM’s preferences. For this purpose, we propose a pairwise comparison of the remaining potential solutions. This procedure starts by randomly choosing two solutions and subsequently asking the DM to select the preferred solution. To facilitate the decision, the comparison is visualized in the form of a radar chart (see Fig. 9). If the DM can clearly state which solution they prefer, the “losing” solution will be removed from the set of potential solutions. Otherwise, the DM can decide to skip the decision and continue with the next iteration, where again two solutions are randomly selected from the set of remaining solutions. The procedure is repeated until a single solution is left. If the DM is satisfied with the performance of the final solution, the interactive MO-GP-HH framework is finished. Otherwise, the DM can return to the exploration phase and search for new solutions. The final solution of our experiment is shown in the form of a parse tree and its prefix notation in Appendix (see Fig. 12).

In this subsection, the performance of the final dispatching rule evolved by the developed interactive MO-GP-HH framework is tested and compared with other well-known dispatching rules on an independent set of instances. This evaluation aims to confirm that the evolved dispatching rule is able to achieve a similar compromise between performance measures for an unseen set of job shop instances. Moreover, a comparison with three other dispatching rules from the literature is carried out to illustrate the differences in trade-offs among performance measures. An overview of the dispatching rules for the test evaluation is provided in Table 7.

Since these dispatching rules are usually designed to optimize a single objective or a combination of objectives, it is obvious that they cannot meet the fictional DM’s preference in our example. Therefore, the schedules generated by these rules cannot compete directly considering the individual performance measures. However, a comparison can be used to illustrate that the evolved dispatching rule produces a compromise solution somewhere between the performance measures of the established dispatching rules with respect to the fictional DM’s preferences. To guarantee a fair comparison of the dispatching rules, using their relative performance on the training set and test set is proposed. Therefore, the ideal and nadir points of the test set are approximated by using the GP-HH-based scheduling generator. The mean of the absolute value for the three performance measures over the 10 test instances can be computed by running the simulation-based fitness evaluation module. Normalizing these values will result in the relative performance that represents the basis for our comparison. The final results are presented in Fig. 10, where the relative performance of each of the tested dispatching rules is shown for the training set on the left-hand side and for the test set on the right-hand side of the figure.

As expected, EDD performs well for the total tardiness and total waiting time on both sets of instances, while the relative performance of the makespan is the worst in our comparison. Moreover, MDD shows a slight improvement on all performance measures compared with the EDD. The relative performance of the makespan remains somewhat low. The best result for the makespan was achieved by using MTWR. However, without considering the jobs’ due dates, this rule performs poorly for the total tardiness. Finally, solution #37 which results from our previous experiment supposed to represent the DM’s preferences produces schedules with an aspired compromise between the makespan, the total tardiness, and the total waiting time. The performance on the set of test instances is very similar to the one on the training set. Small differences can be explained by the relatively small set of instances in the training set used for evolving the preference-based dispatching rule. Another factor that might have an impact on deviations between the two sets of instances is the approximation of the upper and lower bounds of each performance measure used as the basis to calculate the relative performance. Finally, it can be stated that the proposed interactive MO-GP-HH framework successfully guided the fictional DM to a dispatching rule that enables the production of schedules with respect to their expectations. Furthermore, the results of the tests and the comparison underline its usefulness and relevance, especially for real industrial applications, in which a compromise solution is often desired between competing goals.

As stated in Sect. 6.2, the selection of appropriate terminals can be seen as a crucial process in the design of the MO-GP-HH framework. While a too small number of terminals might decrease the quality of the evolving rules, a large terminal set usually has a negative impact on the framework’s efficiency. In order to assess the adequacy of the set of selected terminals for the experiment conducted, we propose counting their occurrence in the last individual of each iteration of the experiment. Figure 11 shows the total occurrence of each terminal in the 37 evolved rules in descending order. PT can be identified as the most significant terminal as it occurs a total of 211 times, which is almost twice as often as the second most frequently occurring candidate. Another interesting finding is that SPT is of less importance, as it appears only 46 times, which is almost half of the second-weakest appearing representative and less than a quarter of the most commonly employed terminal. The total number of occurrences of the remaining terminals is between 79 and 112.

In order to determine whether a reduction of the present set would enhance the performance of the proposed MO-GP-HH framework, we exclude the less frequently applied parameter SPT from the set of terminals. Subsequently, the entire experiment from the previous Section is repeated. The 37 obtained solutions using the reduced set of terminals (reduced set) are then compared with the 37 solutions identified by the framework using the original set of terminals (full set). To compare the quality of the two sets, we propose the application of the hyper-volume (see, e.g., Zitzler, Thiele, Laumanns, Fonseca, & Da Fonseca, 2003), as it represents one of the most frequently used performance measures in MOO (see, e.g., Riquelme, Von Lücken, & Baran,2015, Zitzler et al., 2003). To calculate the hyper-volume, we used the approximated nadir point that was obtained in the first step of the proposed MO-GP-HH framework. The results of the evaluation are shown in Table 8. Therefore, the reduction of the terminal set leads to a slight improvement of the solution set with respect to the hyper-volume.