<  Back to the Polytechnique Montréal portal

An efficient implementation of a VNS heuristic for the weighted fair sequences problem

Caroline Cocha, Bruno P. S. Pessoa, Daniel Aloise and Lucidio A. Cabral

Article (2024)

[img] Restricted to: Repository staff only until 9 August 2024
Accepted Version
Terms of Use: All rights reserved
Request a copy
Show abstract
Hide abstract

Abstract

In the weighted fair sequences problem (WFSP), one aims to schedule a set of tasks or activities sthat the maximum product between the largest temporal distance between two consecutive executions of a task and its priority is minimized. The WFSP covers a large number of applications in different areas, ranging from automobile production on a mixed-model assembly line to the sequencing of interactive applications to be aired in a digital TV environment. This paper proposes an iterative heuristic method for the WFSP centered on an efficient implementation of a variable neighborhood search heuristic. Computational experiments on benchmark instances show that the proposed metaheuristic outperforms the state-of-the-art method proposed to the problem, obtaining comparable solution values in much less computational time.

Uncontrolled Keywords

scheduling; fair sequences; heuristics; metaheuristics

Subjects: 2700 Information technology > 2700 Information technology
2700 Information technology > 2706 Software engineering
Department: Department of Computer Engineering and Software Engineering
Research Center: GERAD - Research Group in Decision Analysis
IVADO - Institute for Data Valorization
Funders: CRSNG/NSERC, Paraíba State Research Foundation (FAPESQ)
Grant number: 2017-05617, 2021/3222
PolyPublie URL: https://publications.polymtl.ca/57360/
Journal Title: International Transactions in Operational Research (vol. 31, no. 3)
Publisher: Blackwell Publishing
DOI: 10.1111/itor.13197
Official URL: https://doi.org/10.1111/itor.13197
Date Deposited: 28 Feb 2024 15:11
Last Modified: 11 Apr 2024 16:13
Cite in APA 7: Cocha, C., Pessoa, B. P. S., Aloise, D., & Cabral, L. A. (2024). An efficient implementation of a VNS heuristic for the weighted fair sequences problem. International Transactions in Operational Research, 31(3), 1720-1735. https://doi.org/10.1111/itor.13197

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Dimensions

Repository Staff Only

View Item View Item