Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

Correlation Coefficient-Based Recombinative Guidance for Genetic Programming Hyperheuristics in Dynamic Flexible Job Shop Scheduling

Published: 01 June 2021 Publication History

Abstract

Dynamic flexible job shop scheduling (JSS) is a challenging combinatorial optimization problem due to its complex environment. In this problem, machine assignment and operation sequencing decisions need to be made simultaneously under the dynamic environments. Genetic programming (GP), as a hyperheuristic approach, has been successfully used to evolve scheduling heuristics for dynamic flexible JSS. However, in traditional GP, recombination between parents may disrupt the beneficial building blocks by choosing the crossover points randomly. This article proposes a recombinative mechanism to provide guidance for GP to realize effective and adaptive recombination for parents to produce offspring. Specifically, we define a novel measure for the importance of each subtree of an individual, and the importance information is utilized to decide the crossover points. The proposed recombinative guidance mechanism attempts to improve the quality of offspring by preserving the promising building blocks of one parent and incorporating good building blocks from the other. The proposed algorithm is examined on six scenarios with different configurations. The results show that the proposed algorithm significantly outperforms the state-of-the-art algorithms on most tested scenarios, in terms of both final test performance and convergence speed. In addition, the rules obtained by the proposed algorithm have good interpretability.

References

[1]
A. S. Manne, “On the job-shop scheduling problem,” Oper. Res., vol. 8, no. 2, pp. 219–223, 1960.
[2]
P. Brucker and R. Schlie, “Job-shop scheduling with multi-purpose machines,” Computing, vol. 45, no. 4, pp. 369–375, 1990.
[3]
F. Zhang, Y. Mei, S. Nguyen, and M. Zhang, “Evolving scheduling heuristics via genetic programming with feature selection in dynamic flexible job shop scheduling,” IEEE Trans. Cybern., early access, Oct. 20, 2020. 10.1109/TCYB.2020.3024849.
[4]
D. Yska, Y. Mei, and M. Zhang, “Genetic programming hyper-heuristic with cooperative coevolution for dynamic flexible job shop scheduling,” in Proc. Eur. Conf. Genet. Program., 2018, pp. 306–321.
[5]
F. Zhang, Y. Mei, and M. Zhang, “Genetic programming with multi-tree representation for dynamic flexible job shop scheduling,” in Proc. Aust. Joint Conf. Artif. Intell., 2018, pp. 472–484.
[6]
F. Zhang, Y. Mei, S. Nguyen, and M. Zhang, “A preliminary approach to evolutionary multitasking for dynamic flexible job shop scheduling via genetic programming,” in Proc. Genet. Evol. Comput. Conf. Companion, 2020, pp. 107–108.
[7]
J. Xiong, L. N. Xing, and Y. W. Chen, “Robust scheduling for multi-objective flexible job-shop problems with random machine breakdowns,” Int. J. Prod. Econ., vol. 141, no. 1, pp. 112–126, 2013.
[8]
J. Park, Y. Mei, S. Nguyen, G. Chen, and M. Zhang, “Investigating a machine breakdown genetic programming approach for dynamic job shop scheduling,” in Proc. Eur. Conf. Genet. Program., 2018, pp. 253–270.
[9]
Y. N. Sotskov and N. V. Shakhlevich, “NP-hardness of shop-scheduling problems with three jobs,” Discr. Appl. Math., vol. 59, no. 3, pp. 237–266, 1995.
[10]
C. D. Geiger, R. Uzsoy, and H. Aytuğ, “Rapid modeling and discovery of priority dispatching rules: An autonomous learning approach,” J. Schedul., vol. 9, no. 1, pp. 7–34, 2006.
[11]
J. C. Tay and N. B. Ho, “Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems,” Comput. Ind. Eng., vol. 54, no. 3, pp. 453–473, 2008.
[12]
S. Bennett, S. Nguyen, and M. Zhang, “A hybrid discrete particle swarm optimisation method for grid computation scheduling,” in Proc. IEEE Congr. Evol. Comput., 2014, pp. 483–490.
[13]
H. Chen, C. Chu, and J. M. Proth, “An improvement of the lagrangean relaxation approach for job shop scheduling: A dynamic programming method,” IEEE Trans. Robot. Autom., vol. 14, no. 5, pp. 786–795, Oct. 1998.
[14]
Y.-S. Foo and Y. Takefuji, “Integer linear programming neural networks for job-shop scheduling,” in Proc. Int. Conf. Neural Netw., 1988, pp. 341–348. [Online]. Available: https://doi.org/10.1109/ICNN.1988.23946
[15]
P. J. Van Laarhoven and E. H. Aarts, “Simulated annealing,” in Simulated Annealing: Theory and Applications. Dordrecht, The Netherlands: Springer, 1987, pp. 7–15.
[16]
F. Glover and M. Laguna, “Tabu search,” in Handbook of Combinatorial Optimization. New York, NY, USA: Springer, 1998, pp. 2093–2229.
[17]
K. Chen, B. Xue, M. Zhang, and F. Zhou, “An evolutionary multitasking-based feature selection method for high-dimensional classification,” IEEE Trans. Cybern., early access, Dec. 31, 2020. 10.1109/TCYB.2020.3042243.
[18]
G. V. Conroy, “Handbook of genetic algorithms,” Knowl Eng. Rev., vol. 6, no. 4, pp. 363–365, 1991.
[19]
M. Durasevic and D. Jakobovic, “A survey of dispatching rules for the dynamic unrelated machines environment,” Expert Syst. Appl., vol. 113, pp. 555–569, Dec. 2018.
[20]
F. Zhang, Y. Mei, S. Nguyen, and M. Zhang, “Genetic programming with adaptive search based on the frequency of features for dynamic flexible job shop scheduling,” in Proc. Eur. Conf. Evol. Comput. Comb. Optim., 2020, pp. 214–230.
[21]
S. Nguyen, M. Zhang, M. Johnston, and K. C. Tan, “Learning iterative dispatching rules for job shop scheduling with genetic programming,” Int. J. Adv. Manuf. Technol., vol. 67, nos. 1–4, pp. 85–100, 2013.
[22]
M. Jayamohan and C. Rajendran, “New dispatching rules for shop scheduling: A step forward,” Int. J. Prod. Res., vol. 38, no. 3, pp. 563–586, 2000.
[23]
J. R. Koza, Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems. vol. 34, Dept. Comput. Sci., Stanford Univ., Stanford, CA, USA, 1990.
[24]
F. Zhang, Y. Mei, and M. Zhang, “Can stochastic dispatching rules evolved by genetic programming hyper-heuristics help in dynamic flexible job shop scheduling?” in Proc. IEEE Congr. Evol. Comput., 2019, pp. 41–48.
[25]
S. Nguyen, M. Zhang, and K. C. Tan, “Surrogate-assisted genetic programming with simplified models for automated design of dispatching rules,” IEEE Trans. Cybern., vol. 47, no. 9, pp. 2951–2965, Sep. 2017.
[26]
K. Miyashita, “Job-shop scheduling with genetic programming,” in Proc. Genet. Evol. Comput. Conf., 2000, pp. 505–512.
[27]
S. Nguyen, M. Zhang, M. Johnston, and K. C. Tan, “Genetic programming for evolving due-date assignment models in job shop environments,” Evol. Comput., vol. 22, no. 1, pp. 105–138, 2014.
[28]
F. Zhang, Y. Mei, and M. Zhang, “A two-stage genetic programming hyper-heuristic approach with feature selection for dynamic flexible job shop scheduling,” in Proc. IEEE Genet. Evol. Comput. Conf., 2019, pp. 347–355.
[29]
F. Zhang, Y. Mei, S. Nguyen, and M. Zhang, “Collaborative multi-fidelity based surrogate models for genetic programming in dynamic flexible job shop scheduling,” IEEE Trans. Cybern., early access, Feb. 2, 2021. 10.1109/TCYB.2021.3050141.
[30]
S. Nguyen, D. Thiruvady, M. Zhang, and K. C. Tan, “A genetic programming approach for evolving variable selectors in constraint programming,” IEEE Trans. Evol. Comput., early access, Jan. 11, 2021. 10.1109/TEVC.2021.3050465.
[31]
R. Poli and N. F. McPhee, “General schema theory for genetic programming with subtree-swapping crossover: Part I,” Evol. Comput., vol. 11, no. 1, pp. 53–66, 2003.
[32]
R. Poli and N. F. McPhee, “General schema theory for genetic programming with subtree-swapping crossover: Part II,” Evol Comput., vol. 11, no. 2, pp. 169–206, 2003.
[33]
F. Zhang, Y. Mei, S. Nguyen, and M. Zhang, “Guided subtree selection for genetic operators in genetic programming for dynamic flexible job shop scheduling,” in Proc. Eur. Conf. Genet. Program., 2020, pp. 252–267.
[34]
J. Branke, S. Nguyen, C. W. Pickardt, and M. Zhang, “Automated design of production scheduling heuristics: A review,” IEEE Trans. Evol. Comput., vol. 20, no. 1, pp. 110–124, Feb. 2016.
[35]
E. K. Burke, M. Hyde, G. Kendall, G. Ochoa, E. Özcan, and J. R. Woodward, “A classification of hyper-heuristic approaches,” in Handbook of Metaheuristics. Heidelberg, Germany: Springer, 2010, pp. 449–468.
[36]
E. K. Burke, M. R. Hyde, G. Kendall, G. Ochoa, E. Ozcan, and J. R. Woodward, “Exploring hyper-heuristic methodologies with genetic programming,” in Computational Intelligence. Heidelberg, Germany: Springer, 2009, pp. 177–201.
[37]
E. K. Burke, M. R. Hyde, G. Kendall, and J. R. Woodward, “A genetic programming hyper-heuristic approach for evolving 2-D strip packing heuristics,” IEEE Trans. Evol. Comput., vol. 14, no. 6, pp. 942–958, Dec. 2010.
[38]
M. R. Hyde, “A genetic programming hyper-heuristic approach to automated packing,” Ph.D. dissertation, Dept. Comput. Sci., Univ. Nottingham, Nottingham, U.K., 2010.
[39]
M. B. Bader-El-Den, R. Poli, and S. Fatima, “Evolving timetabling heuristics using a grammar-based genetic programming hyper-heuristic framework,” Memetic Comput., vol. 1, no. 3, pp. 205–219, 2009.
[40]
N. Pillay and W. Banzhaf, “A genetic programming approach to the generation of hyper-heuristics for the uncapacitated examination timetabling problem,” in Proc. Portuguese Conf. Aritf. Intell., 2007, pp. 223–234.
[41]
M. A. Ardeh, Y. Mei, and M. Zhang, “Genetic programming hyper-heuristics with probabilistic prototype tree knowledge transfer for uncertain capacitated arc routing problems,” in Proc. IEEE Congr. Evol. Comput., 2020, pp. 1–8.
[42]
F. Zhang, Y. Mei, and M. Zhang, “A new representation in genetic programming for evolving dispatching rules for dynamic flexible job shop scheduling,” in Proc. Eur. Conf. Evol. Comput. Comb. Optim., 2019, pp. 33–49.
[43]
S. Nguyen, M. Zhang, M. Johnston, and K. C. Tan, “Automatic programming via iterated local search for dynamic job shop scheduling,” IEEE Trans. Cybern., vol. 45, no. 1, pp. 1–14, Jan. 2015.
[44]
F. Zhang, Y. Mei, and M. Zhang, “Evolving dispatching rules for multi-objective dynamic flexible job shop scheduling via genetic programming hyper-heuristics,” in Proc. IEEE Congr. Evol. Comput., 2019, pp. 1366–1373.
[45]
S. Nguyen, M. Zhang, M. Johnston, and K. C. Tan, “Hybrid evolutionary computation methods for quay crane scheduling problems,” Comput. Oper. Res., vol. 40, no. 8, pp. 2083–2093, 2013.
[46]
M. Durasevic and D. Jakobovic, “Evolving dispatching rules for optimising many-objective criteria in the unrelated machines environment,” Genet. Program. Evol. Mach., vol. 19, nos. 1–2, pp. 9–51, 2018.
[47]
F. Zhang, Y. Mei, and M. Zhang, “Surrogate-assisted genetic programming for dynamic flexible job shop scheduling,” in Proc. Aust. Joint Conf. Artif. Intell., 2018, pp. 766–772.
[48]
M. H. Kim, R. I. B. McKay, N. X. Hoai, and K. Kim, “Operator self-adaptation in genetic programming,” in Proc. Eur. Conf. Genet. Program, 2011, pp. 215–226.
[49]
J. Niehaus and W. Banzhaf, “Adaption of operator probabilities in genetic programming,” in Proc. Eur. Conf. Genet. Program., 2001, pp. 325–336.
[50]
H. Assimi, A. Jamali, and N. Nariman-Zadeh, “Multi-objective sizing and topology optimization of truss structures using genetic programming based on a new adaptive mutant operator,” Neural Comput. Appl., vol. 31, no. 10, pp. 5729–5749, 2019.
[51]
H. Xie, M. Zhang, and P. Andreae, “An analysis of depth of crossover points in tree-based genetic programming,” in Proc. IEEE Congr. Evol. Comput., 2007, pp. 4561–4568.
[52]
U.-M. O’Reilly and F. Oppacher, “Program search with a hierarchical variable length representation: Genetic programming, simulated annealing and hill climbing,” in Proc. Int. Conf. Parallel Problem Solving Nat., 1994, pp. 397–406.
[53]
T. Ito, H. Iba, and S. Sato, “A self-tuning mechanism for depth-dependent crossover,” Advances in Genetic Programming, vol. 3 Cambridge, MA, USA: MIT Press, 1999, p. 377.
[54]
Q. Chen, M. Zhang, and B. Xue, “Geometric semantic genetic programming with perpendicular crossover and random segment mutation for symbolic regression,” in Proc. Simulat. Evol. Learn., 2017, pp. 422–434.
[55]
Q. U. Nguyen, T. A. Pham, X. H. Nguyen, and J. McDermott, “Subtree semantic geometric crossover for genetic programming,” Genet. Program. Evol. Mach., vol. 17, no. 1, pp. 25–53, 2016.
[56]
Y. Mei, S. Nguyen, and M. Zhang, “Constrained dimensionally aware genetic programming for evolving interpretable dispatching rules in dynamic job shop scheduling,” in Proc. Simulat. Evol. Learn., 2017, pp. 435–447.
[57]
N. F. McPhee, M. K. Dramdahl, and D. Donatucci, “Impact of crossover bias in genetic programming,” in Proc. Genet. Evol. Comput. Conf., 2015, pp. 1079–1086.
[58]
H. Iba and H. de Garis, “Extending genetic programming with recombinative guidance,” Advances in Genetic Programming, vol. 2. Cambridge, MA, USA: MIT Press, pp. 69–88, 1996.
[59]
M. Zhang, X. Gao, and W. Lou, “A new crossover operator in genetic programming for object classification,” IEEE Trans. Syst. Man, Cybern. B, Cybern., vol. 37, no. 5, pp. 1332–1343, Oct. 2007.
[60]
T. P. Pawlak and K. Krawiec, “Synthesis of constraints for mathematical programming with one-class genetic programming,” IEEE Trans. Evol. Comput., vol. 23, no. 1, pp. 117–129, Feb. 2019.
[61]
W. W. Danielet al., Applied Nonparametric Statistics. Boston, MA, USA: Houghton Mifflin, 1978.
[62]
K. Neshatian and M. Zhang, “Unsupervised elimination of redundant features using genetic programming,” in Proc. Aust. Joint Conf. Artif. Intell., 2009, pp. 432–442.
[63]
T. Hildebrandt and J. Branke, “On using surrogates with genetic programming,” Evol. Comput., vol. 23, no. 3, pp. 343–367, 2015.
[64]
N. Q. Uy, N. X. Hoai, M. O’Neill, R. I. McKay, and E. G. López, “Semantically-based crossover in genetic programming: Application to real-valued symbolic regression,” Genet. Program. Evol. Mach., vol. 12, no. 2, pp. 91–119, 2011.
[65]
J. P. Davis, K. M. Eisenhardt, and C. B. Bingham, “Developing theory through simulation methods,” Acad. Manag. Rev., vol. 32, no. 2, pp. 480–499, 2007.
[66]
T. Hildebrandt, J. Heger, and B. Scholz-Reiter, “Towards improved dispatching rules for complex shop floor scenarios: A genetic programming approach,” in Proc. ACM Annu. Conf. Genet. Evol. Comput., 2010, pp. 257–264.
[67]
S. Nguyen, Y. Mei, B. Xue, and M. Zhang, “A hybrid genetic programming algorithm for automated design of dispatching rules,” Evol. Comput., vol. 27, no. 3, pp. 467–496, 2019.
[68]
S. Nguyen, M. Zhang, M. Johnston, and K. C. Tan, “A computational study of representations in genetic programming to evolve dispatching rules for the job shop scheduling problem,” IEEE Trans. Evol. Comput., vol. 17, no. 5, pp. 621–639, Oct. 2013.
[69]
Y. Mei, M. Zhang, and S. Nguyen, “Feature selection in evolving job shop dispatching rules with genetic programming,” in Proc. Genet. Evol. Comput. Conf., 2016, pp. 365–372.
[70]
L. H. Gilpin, D. Bau, B. Z. Yuan, A. Bajwa, M. Specter, and L. Kagal, “Explaining explanations: An overview of interpretability of machine learning,” in Proc. Int. Conf. Data Sci. Adv. Anal., 2018, pp. 80–89.

Cited By

View all
  • (2024)Survey on Genetic Programming and Machine Learning Techniques for Heuristic Design in Job Shop SchedulingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.325524628:1(147-167)Online publication date: 1-Feb-2024
  • (2024)Genetic Programming With Lexicase Selection for Large-Scale Dynamic Flexible Job Shop SchedulingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.324460728:5(1235-1249)Online publication date: 1-Oct-2024
  • (2023)Sample-Aware Surrogate-Assisted Genetic Programming for Scheduling Heuristics Learning in Dynamic Flexible Job Shop SchedulingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590440(384-392)Online publication date: 15-Jul-2023
  • Show More Cited By

Index Terms

  1. Correlation Coefficient-Based Recombinative Guidance for Genetic Programming Hyperheuristics in Dynamic Flexible Job Shop Scheduling
    Index terms have been assigned to the content through auto-classification.

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image IEEE Transactions on Evolutionary Computation
    IEEE Transactions on Evolutionary Computation  Volume 25, Issue 3
    June 2021
    203 pages

    Publisher

    IEEE Press

    Publication History

    Published: 01 June 2021

    Qualifiers

    • Research-article

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 30 Nov 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Survey on Genetic Programming and Machine Learning Techniques for Heuristic Design in Job Shop SchedulingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.325524628:1(147-167)Online publication date: 1-Feb-2024
    • (2024)Genetic Programming With Lexicase Selection for Large-Scale Dynamic Flexible Job Shop SchedulingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.324460728:5(1235-1249)Online publication date: 1-Oct-2024
    • (2023)Sample-Aware Surrogate-Assisted Genetic Programming for Scheduling Heuristics Learning in Dynamic Flexible Job Shop SchedulingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590440(384-392)Online publication date: 15-Jul-2023
    • (2023)Explaining Genetic Programming-Evolved Routing Policies for Uncertain Capacitated Arc Routing ProblemsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.323874128:4(918-932)Online publication date: 23-Jan-2023
    • (2023)Task Relatedness-Based Multitask Genetic Programming for Dynamic Flexible Job Shop SchedulingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.319978327:6(1705-1719)Online publication date: 1-Dec-2023
    • (2023)Instance-Rotation-Based Surrogate in Genetic Programming With Brood Recombination for Dynamic Job-Shop SchedulingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.318069327:5(1192-1206)Online publication date: 1-Oct-2023
    • (2023)Collaboration methods for ensembles of dispatching rules for the dynamic unrelated machines environmentEngineering Applications of Artificial Intelligence10.1016/j.engappai.2023.106096122:COnline publication date: 1-Jun-2023
    • (2023)Dynamic energy-efficient scheduling of multi-variety and small batch flexible job-shopComputers and Industrial Engineering10.1016/j.cie.2023.109111178:COnline publication date: 26-Apr-2023
    • (2023)The pickup and delivery hybrid-operations of AGV conflict-free scheduling problem with time constraint among multi-FMCsNeural Computing and Applications10.1007/s00521-023-08897-z35:31(23125-23151)Online publication date: 1-Nov-2023
    • (2023)To Bias or Not to Bias: Probabilistic Initialisation for Evolving Dispatching RulesGenetic Programming10.1007/978-3-031-29573-7_20(308-323)Online publication date: 12-Apr-2023
    • Show More Cited By

    View Options

    View options

    Login options

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media