A cooperative coevolutionary hyper-heuristic approach to solve lot-sizing and job shop scheduling problems using genetic programming

Abstract

Lot-sizing and scheduling in a job shop environment is a fundamental problem that appears in many industrial settings. The problem is very complex, and solutions are often needed fast. Although many solution methods have been proposed, with increasingly better results, their computational times are not suitable for decision-makers who want solutions instantly. Therefore, we propose a novel greedy heuristic to efficiently generate production plans and schedules of good quality. The main innovation of our approach represents the incorporation of a simulation-based technique, which directly generates schedules while simultaneously determining lot sizes. By utilising priority rules, this unique feature enables us to address the complexity of job shop scheduling environments and ensures the feasibility of the resulting schedules. Using a selection of well-known rules from the literature, experiments on a variety of shop configurations and complexities showed that the proposed heuristic is able to obtain solutions with an average gap to Cplex of 4.12%. To further improve the proposed heuristic, a cooperative coevolutionary genetic programming-based hyper-heuristic has been developed. The average gap to Cplex was reduced up to 1.92%. These solutions are generated in a small fraction of a second, regardless of the size of the instance.

KEYWORDS:

• Lot-sizing
• job shop scheduling
• greedy heuristic
• hyper-heuristic
• genetic programming
• cooperative coevolution

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

The data that support the findings of this study are openly available at https://github.com/YZeit/LSJSS.

Notes

1 The repository of the project including all parameter and instance files can be found at https://github.com/YZeit/LSJSS.

2 User's manual for Cplex, IBM Corporation (2019), https://www.ibm.com/docs/en/icos/12.9.0?topic=cplex-users-manual, Accessed on September 29, 2023.

Additional information

Funding

Yannik Zeiträg acknowledges the support by national funds through Fundação para a Ciância e a Tecnologia (FCT) [reference: BD/05314/2021]. José Rui Figueira acknowledges the support by national funds through Fundação para a Ciância e a Tecnologia [DOME research project PTDC/CCI-COM/31198/2017]. Yannik Zeiträg and José Rui Figueira acknowledge the Portuguese national funds through the Foundation for Science and Technology (FCT) [I.P., project UIDB/00097/2020]. Gonçalo Figueira acknowledges the support from the European Union's Horizon 2020 research and innovation programme [TRUST-AI research project, grant agreement number 952060].

Notes on contributors

Yannik Zeiträg

Yannik Zeiträg is a Ph.D. candidate and researcher at Centre for Management Studies of Instituto Superior Técnico (CEGIST) of the University of Lisbon with a background in Operations Research and Management Science. He completed his M.Sc. in Engineering and Management at the Technical University of Munich (TUM) in 2018 with the focus of production management and logistics. His primary research interests lie in Operations Research and Management Science, particularly in the development of innovative optimisation methods to efficiently solve complex scheduling and lot-sizing problems, making use of evolutionary computation, machine learning, and simulation.

José Rui Figueira

Professor José Rui Figueira is currently a Full Professor at Instituto Superior Técnico -- IST, with previous lecturing experiences at University of Evora, University of Coimbra and Nancy's School of Mines (where he got a Full Professor position). He's a former member of LAMSADE, INESC-Coimbra, and DIMACS (Rutgers and Princeton Universities) research centres. Professor Figueira is the co-editor of the book, “Multiple Criteria Decision Analysis: State of the Art Surveys, Springer Science + Business Media, Inc, 2016 (2nd Edition). He's currently the elected President of the International Society of Multi-Criteria Decision-Making and serves as a Coordinator of the European Working Group on Multiple Criteria Decision Aiding. He's on the Editorial Board and Associate Editor of EJOR (European Journal of Operational Research) and EAIA (Engineering Applications of Artificial Intelligence) and a former Associate Editor (2010–2022) of JMCDA (Journal of Multi-Criteria Decision Analysis), as well as a member of the advisory board of other scientific international journals. He was awarded with the Gold Medal of International Society of Multi-Criteria Decision-Making 1n 2017 in Ottawa, Canada.

Gonçalo Figueira

Gonçalo Figueira is a researcher in the Center for Industrial Engineering and Management from INESC TEC, and a professor in the Department of Industrial Engineering and Management at FEUP. He holds M.Sc. and Ph.D. degrees in Industrial Engineering and Management from FEUP. His research interests include operations management and decision support systems. He has published in international journals such as MSOM, Omega, IJPE, IJPR, COR and DSS. He has also been a researcher/consultant in several R&D projects, funded by national and international agencies and companies, in the areas of production planning, supply chain design, scheduling, inventory replenishment and artificial intelligence.