article

A hyper-heuristic ensemble method for static job-shop scheduling

Authors:

Kevin SimAuthors Info & Claims

Evolutionary Computation, Volume 24, Issue 4

Pages 609 - 635

https://doi.org/10.1162/EVCO_a_00183

Published: 01 December 2016 Publication History

Abstract

We describe a new hyper-heuristic method NELLI-GP for solving job-shop scheduling problems JSSP that evolves an ensemble of heuristics. The ensemble adopts a divide-and-conquer approach in which each heuristic solves a unique subset of the instance set considered. NELLI-GP extends an existing ensemble method called NELLI by introducing a novel heuristic generator that evolves heuristics composed of linear sequences of dispatching rules: each rule is represented using a tree structure and is itself evolved. Following a training period, the ensemble is shown to outperform both existing dispatching rules and a standard genetic programming algorithm on a large set of new test instances. In addition, it obtains superior results on a set of 210 benchmark problems from the literature when compared to two state-of-the-art hyper-heuristic approaches. Further analysis of the relationship between heuristics in the evolved ensemble and the instances each solves provides new insights into features that might describe similar instances.

References

[1]

Applegate, D., and Cook, W. (1991). A computational study of the job-shop scheduling problem. ORSA Journal on Computing, 3(2): 149-156.

[2]

Baker, K. R. (1984). Sequencing rules and due-date assignments in a job shop. Management Science, 30(9): 1093-1104.

[3]

Bhowan, U., Johnston, M., Zhang, M., and Yao, X. (2013). Evolving diverse ensembles using genetic programming for classification with unbalanced data. IEEE Transactions on Evolutionary Computation, 17(3): 368-386.

[4]

Bhowan, U., Johnston, M., Zhang, M., and Yao, X. (2014). Reusing genetic programming for ensemble selection in classification of unbalanced data. IEEE Transactions on Evolutionary Computation, 18(6): 893-908.

[5]

Blackstone, J. H., Phillips, D. T., and Hogg, G. L. (1982). A state-of-the-art survey of dispatching rules for manufacturing job shop operations. International Journal of Production Research, 20(1): 27-45.

[6]

Branke, J., Hildebrandt, T., and Scholz-Reiter, B. (2014). Hyper-heuristic evolution of dispatching rules: A comparison of rule representations. Evolutionary Computation, 23(2).

[7]

Branke, J., Nguyen, S., Pickardt, C., and Zhang, M. (2015). Automated design of production scheduling heuristics: A review. IEEE Transactions on Evolutionary Computation, 20(1): 110-124.

[8]

Breiman, L. (1996). Bagging predictors. Machine Learning, 24(2): 123-140.

[9]

Downey, C., Zhang, M., and Liu, J. (2012). Parallel linear genetic programming for multi-class classification. Genetic Programming and Evolvable Machines, 13(3): 275-304.

[10]

Geiger, C. D., Uzsoy, R., and Aytug, H. (2006). Rapid modeling and discovery of priority dispatching rules: An autonomous learning approach. Journal of Scheduling, 9(1): 7-34.

[11]

Giffler, B., and Thompson, G. L. (1960). Algorithms for solving production-scheduling problems. Operations Research, 8(4): 487-503.

[12]

Graham, R. L., Lawler, E. L., Lenstra, J. K., and Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5(2): 287-326.

[13]

Hart, E., and Ross, P. (1998). A heuristic combination method for solving job-shop scheduling problems. In A. Eiben, T. Bäck, M. Schoenauer, and H.-P. Schwefel (Eds.), Parallel problem solving from nature, PPSN V, pp. 845-854. Lecture Notes in Computer Science, Vol. 1498. Berlin/Heidelberg: Springer.

[14]

Hart, E., and Sim, K. (2014). On the life-long learning capabilities of a nelli*: A hyper-heuristic optimisation system. In T. Bartz-Beielstein, J. Branke, B. Filipi?c, and J. Smith (Eds.), Parallel problem solving from nature, PPSN XIII, pp. 282-291. Lecture Notes in Computer Science, Vol. 8672. Berlin: Springer International Publishing.

[15]

Haupt, R. (1989). A survey of priority rule-based scheduling. Operations-Research-Spektrum, 11(1): 3-16.

[16]

Hildebrandt, T., Heger, J., and Scholz-Reiter, B. (2010). Towards improved dispatching rules for complex shop floor scenarios: A genetic programming approach. In Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, GECCO'10, pp. 257-264.

[17]

Hunt, R., Johnston, M., and Zhang, M. (2014). Evolving "less-myopic" scheduling rules for dynamic job shop scheduling with genetic programming. In Proceedings of the 2014 Conference on Genetic and Evolutionary Computation, GECCO'14, pp. 927-934.

[18]

Ingimundardottir, H., and Runarsson, T. P. (2012). Determining the characteristic of difficult job shop scheduling instances for a heuristic solution method. In Learning and Intelligent Optimization, pp. 408-412.

[19]

Koza, J. R. (1992). Genetic programming: On the programming of computers by means of natural selection. Cambridge, MA: MIT Press.

[20]

Lawrence, S. (1984). Resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques. Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh.

[21]

Leyton-Brown, K., Nudelman, E., Andrew, G., McFadden, J., and Shoham, Y. (2003). A portfolio approach to algorithm select. In Proceedings of the 18th International Joint Conference on Artificial Intelligence, pp. 1542-1543.

[22]

Miyashita, K. (2000). Job-shop scheduling with gp. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2000), pp. 505-512.

[23]

Nguyen, S., Zhang, M., Johnston, M., and Tan, K. C. (2013a). A computational study of representations in genetic programming to evolve dispatching rules for the job shop scheduling problem. IEEE Transactions on Evolutionary Computation, 17(5): 621-639.

[24]

Nguyen, S., Zhang, M., Johnston, M., and Tan, K. C. (2013b). Learning iterative dispatching rules for job shop scheduling with genetic programming. The International Journal of Advanced Manufacturing Technology, 67(1-4): 85-100.

[25]

Nguyen, S., Zhang, M., Johnston, M., and Tan, K. C. (2014a). Automatic design of scheduling policies for dynamic multi-objective job shop scheduling via cooperative coevolution genetic programming. IEEE Transactions on Evolutionary Computation, 18(2): 193-208.

[26]

Nguyen, S., Zhang, M., Johnston, M., and Tan, K. C. (2014b). Selection schemes in surrogate-assisted genetic programming for job shop scheduling. In Simulated Evolution and Learning, pp. 656-667.

[27]

Nguyen, S., Zhang, M., Johnston, M., and Tan, K. C. (2015). Automatic programming via iterated local search for dynamic job shop scheduling. IEEE Transactions on Cybernetics, 45(1): 1-14.

[28]

Panwalkar, S. S., and Iskander, W. (1977). A survey of scheduling rules. Operations Research, 25(1): 45-61.

[29]

Park, J., Nguyen, S., Zhang, M., and Johnston, M. (2013). Genetic programming for order acceptance and scheduling. In 2013 IEEE Congress on Evolutionary Computation (CEC), pp. 1005-1012.

[30]

Park, J., Nguyen, S., Zhang, M., and Johnston, M. (2015). Evolving ensembles of dispatching rules using genetic programming for job shop scheduling. In Genetic Programming (18th European Conference, Euro-GP, LNCS 9025), pp. 92-104.

[31]

Pickardt, C., Hildebrandt, T., Branke, J., Heger, J., and Scholz-Reiter, B. (2013). Evolutionary generation of dispatching rule sets for complex dynamic scheduling problems. International Journal of Production Economics, 145(1): 6777.

[32]

Potter, M. A., and De Jong, K. A. (2000). Cooperative coevolution: An architecture for evolving coadapted subcomponents. Evolutionary Computation, 8:1-29.

[33]

Sim, K., and Hart, E. (2014). An improved immune inspired hyper-heuristic for combinatorial optimisation problems. In GECCO'14: Proceedings of the Sixteenth Annual Conference on Genetic and Evolutionary Computation Conference, pp. 121-128.

[34]

Sim, K., and Hart, E. (2015a). A novel heuristic generator for jssp using a tree-based representation of dispatching rules. In GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation Conference, pp. 1485-1486.

[35]

Sim, K., and Hart, E. (2015b). Roll project job shop scheduling benchmark problems. Retrieved from

[36]

Sim, K., Hart, E., and Paechter, B. (2013). Learning to solve bin packing problems with an immune inspired hyper-heuristic. In Advances in Artificial Life, ECAL 2013: Proceedings of the Twelfth European Conference on the Synthesis and Simulation of Living Systems, pp. 856-863.

[37]

Sim, K., Hart, E., and Paechter, B. (2015). A lifelong learning hyper-heuristic method for bin packing. Evolutionary Computation, 23(1): 37-67.

[38]

Singer, M., and Pinedo, M. (1998). A computational study of branch and bound techniques for minimizing the total weighted tardiness in job shops. IIE Transactions, 30(2): 109-118.

[39]

Smith-Miles, K., Baatar, D., Wreford, B., and Lewis, R. (2014). Towards objective measures of algorithm performance across instance space. Computers and Operations Research, 45: 12-24.

[40]

Smith-Miles, K. A., James, R. J. W., Giffin, J. W., and Tu, Y. (2009). A knowledge discovery approach to understanding relationships between scheduling problem structure and heuristic performance. In Learning and Intelligent Optimization: Third International Conference, LION 3, Trento, Italy, January 14-18, 2009. Selected Papers, pp. 89-103.

[41]

Streeter, M. J., and Smith, S. F. (2006). How the landscape of random job shop scheduling instances depends on the ratio of jobs to machines. Journal of Artificial Intelligence Research, 26: 247-287.

[42]

Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2): 278-285.

[43]

Tay, J. C., and Ho, N. B. (2008). Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems. Computers and Industrial Engineering, 54(3): 453-473.

[44]

Ulrich, D., and Erwin, P. (1995). Evolution based learning in a job shop scheduling environment. Computer Operations Research, 22(1): 25-40. 197887.

[45]

Valentini, G., and Masulli, F. (2002). Ensembles of learning machines. In M. Marinaro and R. Tagliaferri (Eds.), Neural nets, pp. 3-20. Lecture Notes in Computer Science, Vol. 2486. Berlin Heidelberg: Springer.

[46]

Vepsalainen, A. P. J., and Morton, T. E. (1987). Priority rules for job shops with weighted tardiness costs. Management Science, 33(8): 1035-1047.

[47]

Zhou, H., Cheung, W., and Leung, L. C. (2009). Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm. European Journal of Operational Research, 194(3): 637-649.

Cited By

Zhang FMei YNguyen SZhang M(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
https://dl.acm.org/doi/10.1109/TEVC.2023.3255246
\DJurasević MGil-Gala FJakobović D(2023)Constructing ensembles of dispatching rules for multi-objective tasks in the unrelated machines environmentIntegrated Computer-Aided Engineering10.3233/ICA-23070430:3(275-292)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.3233/ICA-230704
Zhang FMei YNguyen STan KZhang M(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
https://dl.acm.org/doi/10.1109/TEVC.2022.3180693
Show More Cited By

A hyper-heuristic ensemble method for static job-shop scheduling
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Online algorithms
      1. Online learning algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Iterated local search using an add and delete hyper-heuristic for university course timetabling

Graphical abstractDisplay Omitted HighlightsAdd and delete operations are encoded as a list/string of integers (ADL).An effective hyper-heuristic approach operating with ADLs is proposed.Low level heuristics perform search over the space of feasible ...
Improved EDA-Based Hyper-heuristic for Flexible Job Shop Scheduling Problem with Sequence-Independent Setup Times and Resource Constraints
Advanced Intelligent Computing Technology and Applications
Abstract
In this paper, an improved estimation of distribution algorithm-based hyper heuristic (IEDA-HH) algorithm is proposed for the flexible job shop scheduling problem with sequence-independent setup times and resource constraints (FJSP_SISTs_RCs) with ...
A tensor-based selection hyper-heuristic for cross-domain heuristic search

Presented a novel method to improve the performance of a hyper-heuristic approach.Represented the trail of a hyper-heuristic mixing heuristics as a 3rd-order tensor.Analyzed tensors to discover the links between heuristics and the hyper-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Evolutionary Computation

Evolutionary Computation Volume 24, Issue 4

Winter 2016

169 pages

ISSN:1063-6560

EISSN:1530-9304

Issue’s Table of Contents

Publisher

MIT Press

Cambridge, MA, United States

Publication History

Published: 01 December 2016

Published in EVOL Volume 24, Issue 4

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
84
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang FMei YNguyen SZhang M(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
https://dl.acm.org/doi/10.1109/TEVC.2023.3255246
\DJurasević MGil-Gala FJakobović D(2023)Constructing ensembles of dispatching rules for multi-objective tasks in the unrelated machines environmentIntegrated Computer-Aided Engineering10.3233/ICA-23070430:3(275-292)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.3233/ICA-230704
Zhang FMei YNguyen STan KZhang M(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
https://dl.acm.org/doi/10.1109/TEVC.2022.3180693
Đurasević MGil-Gala FPlaninić LJakobović D(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
https://dl.acm.org/doi/10.1016/j.engappai.2023.106096
Gil-Gala FDurasević MSierra MVarela R(2023)Evolving ensembles of heuristics for the travelling salesman problemNatural Computing: an international journal10.1007/s11047-023-09968-922:4(671-684)Online publication date: 25-Oct-2023
https://dl.acm.org/doi/10.1007/s11047-023-09968-9
Đurasević MPlaninić LGala FJakobović DWagner M(2022)Novel ensemble collaboration method for dynamic scheduling problemsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528807(893-901)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528807
Xiong HShi SRen DHu J(2022)A survey of job shop scheduling problemComputers and Operations Research10.1016/j.cor.2022.105731142:COnline publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1016/j.cor.2022.105731
Strassl SMusliu N(2022)Instance space analysis and algorithm selection for the job shop scheduling problemComputers and Operations Research10.1016/j.cor.2021.105661141:COnline publication date: 1-May-2022
https://dl.acm.org/doi/10.1016/j.cor.2021.105661
Gil-Gala FSierra MMencía CVarela R(2022)Combining hyper-heuristics to evolve ensembles of priority rules for on-line schedulingNatural Computing: an international journal10.1007/s11047-020-09793-421:4(553-563)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s11047-020-09793-4
Zhang FMei YNguyen SZhang M(2022)Importance-Aware Genetic Programming for Automated Scheduling Heuristics Learning in Dynamic Flexible Job Shop SchedulingParallel Problem Solving from Nature – PPSN XVII10.1007/978-3-031-14721-0_4(48-62)Online publication date: 10-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-14721-0_4
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents