Journal
COMPUTERS & INDUSTRIAL ENGINEERING
Volume 168, Issue -, Pages -Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cie.2022.108128
Keywords
Production scheduling; Open shop; Makespan; Mathheuristic
Funding
- Coordination for the Improvement of Higher Education Personnel (CAPES) [88882.379108/2019-01]
- National Council for Scientific and Technological Development (CNPq) [306075/ 2017-2, 430137/2018-4, 312585/2021-7]
- Sao Paulo Research Foundation (FAPESP) [2020/16341-5]
Ask authors/readers for more resources
This paper presents a new hybrid approach combining adaptive large neighborhood search (ALNS) and constraint programming (CP) for solving scheduling problems with setup times and costs. The proposed method outperforms other exact methods and shows promise for solving large-sized instances.
In recent years, researchers have been paying special attention to scheduling problems with setup times and costs, aiming to adopt more realistic assumptions. This paper aims at presenting a new hybridization of an adaptive large neighborhood search (ALNS) with constraint programming (CP) as a local search phase for open shop scheduling with non-anticipatory sequence-dependent setup time. An integer linear programming model is presented based on the classic open shop model, and a new CP model is proposed with non-anticipatory setup times. The proposed CP model has not been addressed in the revised literature and outperforms all other exact methods. The objective function adopted is makespan minimization, and we use the relative deviation as performance criteria. Since the problem under study is NP-hard, we test many approximations and exact algorithms to obtain high-quality solutions in acceptable computational times. The extensive computational experience shows that the proposed hybridization of metaheuristic and constraint programming is promising for solving large-sized instances.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available