{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T22:43:41Z","timestamp":1757630621876,"version":"3.44.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,6,16]],"date-time":"2025-06-16T00:00:00Z","timestamp":1750032000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,6,16]],"date-time":"2025-06-16T00:00:00Z","timestamp":1750032000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004488","name":"Hrvatska Zaklada za Znanost","doi-asserted-by":"publisher","award":["IP-2022-10-5398"],"award-info":[{"award-number":["IP-2022-10-5398"]}],"id":[{"id":"10.13039\/501100004488","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100011033","name":"Agencia Estatal de Investigaci\u00f3n","doi-asserted-by":"publisher","award":["MCINN-23-PID2022"],"award-info":[{"award-number":["MCINN-23-PID2022"]}],"id":[{"id":"10.13039\/501100011033","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006382","name":"Universidad de Oviedo","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006382","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The Bin Packing Problem (BPP) is a well-known NP-hard problem with numerous real-world applications. This study focuses on minimizing waste and maximum lateness in a one-dimensional version of the BPP, which is particularly relevant in industrial contexts. The goal is to develop a constructive heuristic algorithm that can be adapted to various situations. We model the BPP as a Deterministic Markov Decision Process with discrete state and action spaces, where policies are represented by arithmetic expressions involving state variables. This approach allows for a clearer explanation of the decision process, in contrast to other methods like neural networks. To evolve these policies, we use Genetic Programming (GP). Trained on a set of BPP instances, the resulting policies are effective for solving new, unseen instances. In the experimental study, we explore different GP settings, including varying sets of symbols. The results reveal valuable insights about the importance of state variables, indicating that a smaller selection of them may yield the best results. The evolved policies are compared with an exact method from the literature, achieving similar outcomes but with significantly less computational time.<\/jats:p>","DOI":"10.1007\/s11047-025-10028-7","type":"journal-article","created":{"date-parts":[[2025,6,16]],"date-time":"2025-06-16T11:58:55Z","timestamp":1750075135000},"page":"603-617","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Genetic programming policies for bin packing in the framework of deterministic Markov decision process"],"prefix":"10.1007","volume":"24","author":[{"given":"Jes\u00fas","family":"Quesada","sequence":"first","affiliation":[]},{"given":"Francisco J.","family":"Gil-Gala","sequence":"additional","affiliation":[]},{"given":"Marko","family":"Durasevi\u0107","sequence":"additional","affiliation":[]},{"given":"Mar\u00eda R.","family":"Sierra","sequence":"additional","affiliation":[]},{"given":"Ramiro","family":"Varela","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,6,16]]},"reference":[{"key":"10028_CR1","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.omega.2016.06.003","volume":"68","author":"C Arbib","year":"2017","unstructured":"Arbib C, Marinelli F (2017) Maximum lateness minimization in one-dimensional bin packing. Omega 68:76\u201384","journal-title":"Omega"},{"issue":"4","key":"10028_CR2","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1007\/s11047-023-09951-4","volume":"22","author":"\u00c1 Beade","year":"2023","unstructured":"Beade \u00c1, Rodr\u00edguez M, Santos J (2023) Evolutionary feature selection approaches for insolvency business prediction with genetic programming. Nat Comput 22(4):705\u2013722","journal-title":"Nat Comput"},{"issue":"1","key":"10028_CR3","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1287\/ijoc.1050.0132","volume":"19","author":"G Belov","year":"2007","unstructured":"Belov G, Scheithauer G (2007) Setup and open-stacks minimization in one-dimensional stock cutting. Informs J Comput 19(1):27\u201335","journal-title":"Informs J Comput"},{"key":"10028_CR4","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1162\/EVCO_a_00131","volume":"23","author":"J Branke","year":"2014","unstructured":"Branke J, Hildebrandt T, Scholz-Reiter B (2014) Hyper-heuristic evolution of dispatching rules: a comparison of rule representations. Evolutionary Comput 23:249\u2013277","journal-title":"Evolutionary Comput"},{"issue":"1","key":"10028_CR5","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1162\/EVCO_a_00044","volume":"20","author":"EK Burke","year":"2012","unstructured":"Burke EK, Hyde MR, Kendall G, Woodward J (2012) Automating the packing heuristic design process with genetic programming. Evol Comput 20(1):63\u201389","journal-title":"Evol Comput"},{"key":"10028_CR6","doi-asserted-by":"crossref","unstructured":"Coffman E-G, Galambos G, Martello S, and Vigo D (1999) Bin packing approximation algorithms: combinatorial analysis, pp. 151\u2013207. Springer US, Boston, MA","DOI":"10.1007\/978-1-4757-3023-4_3"},{"key":"10028_CR7","doi-asserted-by":"crossref","unstructured":"Durasevi\u0107 M, Jakobovi\u0107 D, Knezevi\u0107 K (2016) Adaptive scheduling on unrelated machines with genetic programming. Applied Soft Comput 48:419\u2013430","DOI":"10.1016\/j.asoc.2016.07.025"},{"key":"10028_CR8","unstructured":"Garey MR, Johnson DS (1990) Computers and intractability; a guide to the theory of np-completeness. W. H. Freeman & Co., USA"},{"issue":"4","key":"10028_CR9","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1007\/s11047-023-09968-9","volume":"22","author":"FJ Gil-Gala","year":"2023","unstructured":"Gil-Gala FJ, Durasevi\u0107 M, Sierra MR, Varela R (2023) Evolving ensembles of heuristics for the travelling salesman problem. Nat Comput 22(4):671\u2013684","journal-title":"Nat Comput"},{"key":"10028_CR10","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2019.105782","volume":"85","author":"FJ Gil-Gala","year":"2019","unstructured":"Gil-Gala FJ, Menc\u00eda C, Sierra MR, Varela R (2019) Evolving priority rules for on-line scheduling of jobs on a single machine with variable capacity over time. Appl Soft Comput 85:105782","journal-title":"Appl Soft Comput"},{"issue":"4","key":"10028_CR11","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1007\/s11047-020-09793-4","volume":"21","author":"FJ Gil-Gala","year":"2022","unstructured":"Gil-Gala FJ, Sierra MR, Menc\u00eda C, Varela R (2022) Combining hyper-heuristics to evolve ensembles of priority rules for on-line scheduling. Nat Comput 21(4):553\u2013563","journal-title":"Nat Comput"},{"issue":"1","key":"10028_CR12","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.ejor.2023.06.028","volume":"312","author":"M Haouari","year":"2024","unstructured":"Haouari M, Mhiri M (2024) Lower and upper bounding procedures for the bin packing problem with concave loading cost. Eur J Oper Res 312(1):56\u201369","journal-title":"Eur J Oper Res"},{"issue":"3","key":"10028_CR13","doi-asserted-by":"publisher","first-page":"1463","DOI":"10.1109\/TSMC.2020.3020732","volume":"52","author":"Y He","year":"2022","unstructured":"He Y, Xing L, Chen Y, Pedrycz W, Wang L, Wu G (2022) A generic markov decision process model and reinforcement learning method for scheduling agile earth observation satellites. IEEE Trans Syst, Man, Cybernet: Syst 52(3):1463\u20131474","journal-title":"IEEE Trans Syst, Man, Cybernet: Syst"},{"key":"10028_CR14","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1016\/j.engappai.2018.09.007","volume":"76","author":"D Hein","year":"2018","unstructured":"Hein D, Udluft S, Runkler TA (2018) Interpretable policies for reinforcement learning by genetic programming. Eng Appl Artif Intell 76:158\u2013169","journal-title":"Eng Appl Artif Intell"},{"issue":"5","key":"10028_CR15","first-page":"5235","volume":"59","author":"A Herrmann","year":"2023","unstructured":"Herrmann A, Schaub H (2023) Reinforcement learning for the agile earth-observing satellite scheduling problem. IEEE Trans Aerosp Electron Syst 59(5):5235\u20135247","journal-title":"IEEE Trans Aerosp Electron Syst"},{"key":"10028_CR16","doi-asserted-by":"crossref","unstructured":"Jakobovic D, Durasevi\u0107 M, Picek S, and Ga\u0161perov B (2024) ECF: A C++ framework for evolutionary computation. SoftwareX 27","DOI":"10.1016\/j.softx.2024.101640"},{"issue":"5","key":"10028_CR17","doi-asserted-by":"publisher","first-page":"3205","DOI":"10.1109\/TCYB.2022.3169210","volume":"53","author":"Y-H Jia","year":"2023","unstructured":"Jia Y-H, Mei Y, Zhang M (2023) Learning heuristics with different representations for stochastic routing. IEEE Trans Cybernet 53(5):3205\u20133219","journal-title":"IEEE Trans Cybernet"},{"issue":"1","key":"10028_CR18","first-page":"636","volume":"30","author":"C Munien","year":"2021","unstructured":"Munien C, Ezugwu AE (2021) Metaheuristic algorithms for one-dimensional bin-packing problems: a survey of recent advances and applications. J Intell Syst 30(1):636\u2013663","journal-title":"J Intell Syst"},{"issue":"1","key":"10028_CR19","first-page":"31","volume":"48","author":"N Pillay","year":"2012","unstructured":"Pillay N (2012) A study of evolutionary algorithm selection hyper-heuristics for the one-dimensional bin-packing problem. South African Comput J 48(1):31\u201340","journal-title":"South African Comput J"},{"key":"10028_CR20","doi-asserted-by":"crossref","unstructured":"Quesada J, Gil-Gala F-J, Durasevic M, Sierra M, and Varela R (2023) An analysis of heuristic templates in genetic programming for one-dimensional cutting and packing problems. In proceedings of the companion conference on genetic and evolutionary computation, GECCO \u201923 Companion, pp. 623-626, New York, NY, USA. Association for computing machinery","DOI":"10.1145\/3583133.3590674"},{"key":"10028_CR21","doi-asserted-by":"crossref","unstructured":"Quesada J, Gil-Gala FJ, Durasevi\u0107 M, Sierra MR, Varela R (2024) Evolutionary algorithms for bin packing problem with maximum lateness and waste minimization. In: Ferr\u00e1ndez Vicente JM, Val Calvo M, Adeli H (eds) Bioinspired systems for translational applications: from robotics to social engineering. Cham. Springer Nature Switzerland, pp 140\u2013149","DOI":"10.1007\/978-3-031-61137-7_14"},{"issue":"7","key":"10028_CR22","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1057\/jors.1992.101","volume":"43","author":"PE Sweeney","year":"1992","unstructured":"Sweeney PE, Paternoster ER (1992) Cutting and packing problems: a categorized, application-orientated research bibliography. J Operat Res Soc 43(7):691\u2013706","journal-title":"J Operat Res Soc"},{"key":"10028_CR23","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1213\/01.ane.0000277492.90805.0f","volume":"105","author":"M van Houdenhoven","year":"2007","unstructured":"van Houdenhoven M, Oostrum J, Hans E, Wullink G, Kazemier G (2007) Improving operating room efficiency by applying bin-packing and portfolio techniques to surgical case scheduling. Anesth Analg 105:707\u201314","journal-title":"Anesth Analg"},{"key":"10028_CR24","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s10479-008-0407-1","volume":"166","author":"R Varela","year":"2009","unstructured":"Varela R, Vela RC, Puente J, Sierra M, Gonzalez-Rodriguez I (2009) An effective solution for a real cutting stock problem in manufacturing plastic rolls. Ann Oper Res 166:125\u2013146","journal-title":"Ann Oper Res"},{"key":"10028_CR25","doi-asserted-by":"crossref","unstructured":"Videau M, Leite A, Teytaud O, Schoenauer M (2022) Multi-objective genetic programming for explainable reinforcement learning. In: Medvet E, Pappa G, Xue B (eds) Genetic programming. Cham. Springer International Publishing, pp 278\u2013293","DOI":"10.1007\/978-3-031-02056-8_18"},{"key":"10028_CR26","doi-asserted-by":"crossref","unstructured":"Vos D and Verwer S (2023) Optimal decision tree policies for markov decision processes. In proceedings of the thirty-second international joint conference on artificial intelligence, IJCAI-2023, pp 5457\u20135465. International joint conferences on artificial intelligence organization","DOI":"10.24963\/ijcai.2023\/606"},{"issue":"9","key":"10028_CR27","doi-asserted-by":"crossref","DOI":"10.1080\/09544828.2013.825103","volume":"2023","author":"J Wang","year":"2023","unstructured":"Wang J, Xiao C, Wang S, Ruan Y (2023) Reinforcement learning for the traveling salesman problem: performance comparison of three algorithms. J Eng 2023(9):e12303","journal-title":"J Eng"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-025-10028-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11047-025-10028-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-025-10028-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T19:19:51Z","timestamp":1757531991000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11047-025-10028-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,16]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["10028"],"URL":"https:\/\/doi.org\/10.1007\/s11047-025-10028-7","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"type":"print","value":"1567-7818"},{"type":"electronic","value":"1572-9796"}],"subject":[],"published":{"date-parts":[[2025,6,16]]},"assertion":[{"value":"25 May 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 June 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}}]}}