- author = "Shady Amgad Ahmed Ahmed Salama",
- title = "research on automatic generation of dispatching rules using genetic programming for job shop scheduling problems",
- school = "Department of System Science, Kobe University",
- year = "2022",
- address = "Japan",
- month = jul,
- keywords = "genetic algorithms, genetic programming, Gene Expression Programming, GEP, JSSPs, NSGA-II, NSGA2, MOGP, DES, PGP, DJSSP",
-
URL = "
https://da.lib.kobe-u.ac.jp/da/kernel/0100477892/D1008466y.pdf",
-
URL = "
https://hdl.handle.net/20.500.14094/0100477892",
-
URL = "https://da.lib.kobe-u.ac.jp/da/kernel/0100477892/D1008466.pdf",
- size = "225 pages",
-
abstract = "This dissertation focuses on the automatic generation
of high-quality dispatching rules in compact structures
and low computational requirements using the Genetic
Programming (GP) to solve static and dynamic Job Shop
Scheduling Problems (JSSPs). Precisely, the main
objective is to reduce the computational burden
required by the GP algorithm to evolve high-quality
dispatching rules for both static and dynamic JSSPs.
Five approaches are proposed in this thesis to address
the limitations of the conventional research. Two of
these approaches are developed to generate scheduling
rules for the static JSSPs, whereas the other three
approaches deal with the dynamic JSSPs.
Regarding the static JSSPs, two main limitations have been reported in the literature. The first limitation is premature convergence caused by low diversity among GP individuals that leads to low solution quality, whereas the second one is the high computational costs of GP approaches due to significant growth in the size of generated rules without a tangible return in fitness values, known as the bloat effect. Consequently, a distance metric is introduced to measure the genotypic similarity between the GP individuals and the best-evolved rule in this thesis. The proposed metric overcomes the limitations of the current metrics by considering the interaction effect between nodes and their parents, does not require additional simulation runs, and gives higher priority to the nodes closest to the root node. The aim is to represent population diversity in a numerical format that can be optimized and thus improve the exploration ability of the GP algorithm by avoiding early convergence. Therefore, a multi-objective GP framework is proposed by integrating Non-dominated Sorting Genetic Algorithm II (NSGA-II) with the GP algorithm to optimize three objectives simultaneously. The three considered objectives are diversity values estimated using the proposed metric, rule length, and solution quality. To assess the effectiveness of the proposed distance metric and multi-objective GP framework, two algorithms are developed and compared with three algorithms from the literature across ten static JSSP instances using makespan and mean tardiness as objective functions. Experimental results show the effectiveness of the proposed methods in generating a diverse population of high-quality rules with smaller sizes in a shorter computational budget compared with the conventional methods.
Regarding the dynamic JSSPs, two major limitations have been reported in the literature. The first limitation is similar to the static problems which is the high computational time of the GP algorithm due to the bloat effect. In contrast to the static problems where benchmark instances are used for fitness assessment, a Discrete Event Simulation (DES) model is the most common approach for the dynamic JSSPs. Therefore, the second limitation is the high fitness evaluation costs to assess the fitness values of evolved rules using a DES model. In order to address the first limitation, this thesis proposes a feature selection approach to reduce the size of evolved rules. The proposed approach uses a probabilistic selection scheme to estimate the weight of given terminals instead of the binary discrimination usually used in conventional methods. In addition, the proposed approach does not require pilot GP runs as the conventional methods. Because it uses the evolutionary information collected from previous generations in estimating the weights of the terminals in the next generation in an online manner. The proposed approach (PGP) is compared with three GP algorithms and 30 manually-made rules from the literature under different job shop configurations and scheduling objectives, including total weighted tardiness, mean tardiness, and mean flow time. Experimentally obtained results demonstrate that the proposed approach outperforms the other conventional methods in generating more compact rules in a shorter computational time.
Gene Expression Programming (GEP) algorithm is a modified version of the tree-based GP algorithm to evolve dispatching rules using a fixed-linear representation that is less susceptible to the bloat effect. Therefore, this thesis modifies the feature selection approach proposed for the GP algorithm to be applicable to the GEP algorithm for the dynamic JSSPs. The aim is to evaluate the effect of imposing an additional constraint on the size of evolved rules in the case of the contained GP representation. The proposed approach adds two main points to the existing literature. First, it is the first attempt to control the bloat effect for constrained GP representations in the literature on the automated design of scheduling rules. Second, it increases the likelihood of using the proposed approach in more complex manufacturing environments due to the significant reduction in training time. The proposed algorithm is compared with three algorithms from the literature using three objective functions namely total weighted tardiness, mean tardiness, and mean flow time. Experimental results confirm the ability of the proposed algorithm in evolving rules with smaller sizes in a shorter computational time without sacrificing performance. The weight of terminals across generations of the proposed algorithm is compared with the weights obtained using the PGP algorithm. Results demonstrate the ability of the proposed feature selection approach to identify the same set of critical terminals regardless of the evolutionary algorithm used.
Finally, a surrogate assisted GEP approach is introduced to reduce the time of expensive fitness assessments of dispatching rules generated for dynamic JSSPs. Reducing fitness assessment times significantly speeds up the most computationally demanding step of the GP algorithm. The proposed approach extends the conventional methods through three main contributions. First, it is the first attempt to use machine learning to abstract a DES model of DJSSPs. Second, it reduces fitness evaluation time without significantly affecting prediction accuracy. Third, it is independent of the structure of evolved rules, and thus it can be adopted with other hyper-heuristic approaches. Three surrogate models are developed by integrating the proposed approach with three simplified models from the literature. The proposed surrogates are compared with their counterparts from the literature using mean tardiness and mean flow time objective functions. Experimental results prove that the proposed surrogates have significantly lower computational costs with a neglectable loss in prediction accuracy across different training and testing scenarios.
It is verified that the proposed approaches significantly reduced the computational time of the GP algorithm to automatically evolve high-quality scheduling rules in compact structures compared to BibTeX entry too long. Truncated
