Authors: Matijević, Luka 
Stanković, Una 
Davidović, Tatjana 
Affiliations: Computer Science 
Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: General variable neighborhood search for the weighted scheduling problem with deadlines and release times
First page: 207
Last page: 212
Conference: XLVIII International Symposium on Operational Research, SYM-OP-IS 2021, Banja Koviljača, 20-23. septembar 2021.
Issue Date: 2021
Rank: M33
ISBN: 978-86-7589-151-2
URL: http://www.mi.sanu.ac.rs/~tanjad/MSD21-GVNSschedSYMOPIS2021.pdf
http://symopis2021.matf.bg.ac.rs/download/Zbornik-SYM-OP-IS2021.pdf
Abstract: 
We consider a non-preemptive scheduling problem with deadlines and release times, where each task
is associated also a nonnegative weight, representing price to be rewarded when task is scheduled for execution. The problem consists of finding a subset of tasks that are going to be scheduled and ordering them in such a way to maximize the price (sum of weights) of all scheduled tasks. Since the problem is NP-hard, we propose a metaheuristic approach, using the General Variable Neighborhood Search (GVNS). This approach is tested on a set of randomly generated instances, and the results obtained this way suggest that GVNS is able to find a high-quality solutions in a short amount of time.
Keywords: combinatorial optimization | scheduling problem | identical machines | metaheuristics
Publisher: University of Belgrade, Faculty of Mathematics
Project: Advanced artificial intelligence techniques for analysis and design of system components based on trustworthy BlockChain technology - AI4TrustBC 

Show full item record

Page view(s)

43
checked on Sep 15, 2022

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.