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
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
checked on Feb 5, 2023
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.