Ant-Based Generation Constructive Hyper-heuristics for the Movie Scene Scheduling Problem | SpringerLink
Skip to main content
Springer Nature Link
Log in

Ant-Based Generation Constructive Hyper-heuristics for the Movie Scene Scheduling Problem

  • Conference paper
  • First Online:
Theory and Practice of Natural Computing (TPNC 2021)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 13082))

Abstract

The task of generation constructive hyper-heuristics concerns itself with generating new heuristics for problem domains via some kind of mechanism that combines low-level heuristic components into new heuristics. The movie scene scheduling problem is a recently developed combinatorial problem for which there are relatively few low-level heuristics. This paper focused on the application of a novel ant-based generation constructive hyper-heuristic to develop new constructive heuristics for the problem. The ant-based generation constructive hyper-heuristic was applied to create components that were themselves produced from existing heuristics and domain knowledge regarding the movie scene scheduling problem. The results of the research demonstrated that the ant-based hyper-heuristic was successful in the domain. It outperformed the existing set of human-derived constructive heuristics across a wide variety of problem classes and over several instances within the movie scene scheduling problem. The success of this research suggests that other hyper-heuristic methods, such as a generation perturbative one, could be applied to the movie scene scheduling problem in the future.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 6291
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7864
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Aarseth, E.: The culture and business of cross-media productions. Pop. Commun. 4(3), 203–211 (2006). https://doi.org/10.1207/s15405710pc0403_4

    Article  Google Scholar 

  2. Garcia de la Banda, M., Stuckey, P., Chu, G.: Solving talent scheduling with dynamic programming. INFORMS J. Comput. 23, 120–137 (2011). https://doi.org/10.1287/ijoc.1090.0378

  3. Cheng, T.C.E., Diamond, J., Lin, B.: Optimal scheduling in film production to minimize talent hold cost. J. Optim. Theory Appl. 79, 479–492 (1993). https://doi.org/10.1007/BF00940554

  4. Gregory, P., Miller, A., Prosser, P.: Solving the rehearsal problem with planning and with model checking. Eur. Conf. Artif. Intell. 16, 157–171 (2004)

    Google Scholar 

  5. Liu, Y., Sun, Q., Zhang, X., Wu, Y.: Research on the scheduling problem of movie scenes. Discret. Dyn. Nat. Soc. 2019, 1–8 (2019). Article ID 3737105

    Google Scholar 

  6. Long, X., Jinxing, Z.: Scheduling problem of movie scenes based on three meta-heuristic algorithms. IEEE Access PP, 59091–59099 (2020)

    Google Scholar 

  7. Mann, H.B., Whitney, D.R.: On a test of whether one of two random variables is stochastically larger than the other. Ann. Math. Stat. 18(1), 50–60 (1947)

    Article  MathSciNet  Google Scholar 

  8. Nordstrom, A., Tufekci, S.: A genetic algorithm for the talent scheduling problem. Comput. Ind. Eng. 21, 927–940 (1994)

    MATH  Google Scholar 

  9. Sakulsom, N., Tharmmaphornphilas, W.: Scheduling a music rehearsal problem with unequal music piece length. Comput. Ind. Eng. 70, 20–30 (2014)

    Google Scholar 

  10. Singh, E., Pillay, N.: A comparison of ant-based pheromone spaces for generation constructive hyper-heuristics. Under Review (2021)

    Google Scholar 

  11. Singh, E., Pillay, N.: Haco: Supplementary material (2021). https://drive.google.com/file/d/1DHtMBkwTfT-h4sEIYsqa7-Nx9rD31sMZ/view?usp=sharing

  12. Singh, E., Pillay, N.: Ant-based hyper-heuristics for the movie scene scheduling problem. In: Proceedings 2021 ICAISC International Conference for Artificial Intelligence and Soft Computing (To appear June 2021)

    Google Scholar 

Download references

Acknowledgments

This work was funded as part of the Multichoice Research Chair in Machine Learning at the University of Pretoria, South Africa. This work is based on the research supported wholly/in part by the National Research Foundation of South Africa (Grant Numbers 46712). Opinions expressed and conclusions arrived at, are those of the author and are not necessarily to be attributed to the NRF.

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Pretoria, Pretoria, South Africa

    Emilio Singh & Nelishia Pillay

Authors
  1. Emilio Singh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nelishia Pillay
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Nelishia Pillay .

Editor information

Editors and Affiliations

  1. Graduate School of Systems and Information Engineering, University of Tsukuba, Tsukuba, Japan

    Claus Aranha

  2. Research Group on Mathematical Linguistics, Rovira i Virgili University, Tarragona, Spain

    Carlos Martín-Vide

  3. School of Technology, University of Extremadura, Cáceres, Spain

    Miguel A. Vega-Rodríguez

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Singh, E., Pillay, N. (2021). Ant-Based Generation Constructive Hyper-heuristics for the Movie Scene Scheduling Problem. In: Aranha, C., Martín-Vide, C., Vega-Rodríguez, M.A. (eds) Theory and Practice of Natural Computing. TPNC 2021. Lecture Notes in Computer Science(), vol 13082. Springer, Cham. https://doi.org/10.1007/978-3-030-90425-8_9

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-90425-8_9

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-90424-1

  • Online ISBN: 978-3-030-90425-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics