A Parallel Greedy Randomized Adaptive Search Procedure Metaheuristic for the Resource-Constrained Task Scheduling Problem

Abstract

The Task Scheduling Problem (TSP) consists, basically, of a group of tasks that should be executed respecting precedence constraints and minimizing the execution time of all tasks. For every task, processing units must be chosen to execute a particular task and at what moment that will happen. This work presents a parallel implementation, through multicore architectures, to solve Resource-Constrained TSP, based on a known model called dynamic resource constrained task scheduling problem (DRCTSP) and using a Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic. In this approach, the moment a task is activated until the last considered time period, an amount of resources (called pro t), associated with each activated task, is provided for each period. Thus, the amount of resources available in a given period will depend on what tasks have been activated by then and when this occurred. Based on the OpenMP standard, this work shows the bene ts of using parallel methods to speed-up the overall time spent to  nd a feasible solution without compromising the its quality. Also, a comparative analysis is done based on the empirical probability distributions of the random variable time to target solutions.