General variable neighborhood search for the weighted scheduling problem with deadlines and release times

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.