A graphical processing unit-based parallel hybrid genetic algorithm for resource-constrained multi-project scheduling problem

Uysal F., SÖNMEZ R., İŞLEYEN S. K.

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE, vol.33, no.16, 2021 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 33 Issue: 16
  • Publication Date: 2021
  • Doi Number: 10.1002/cpe.6266
  • Journal Name: CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Aerospace Database, Applied Science & Technology Source, Communication Abstracts, Compendex, Computer & Applied Sciences, INSPEC, Metadex, zbMATH, Civil Engineering Abstracts
  • Keywords: parallel genetic algorithm, resource constrained multi-project scheduling problem, resource constrained project scheduling problem, resource management
  • Middle East Technical University Affiliated: Yes

Abstract

In this article, we present a parallel graphical processing unit (GPU)-based genetic algorithm (GA) for solving the resource-constrained multi-project scheduling problem (RCMPSP). We assumed that activity pre-emption is not allowed. Problem is modeled in a portfolio of projects where precedence and resource constraints affect the portfolio duration. We also assume that the durations, availability of resources are deterministic and portfolio has a static nature. The objective in this article is to find a start time for each activity of the project so that the portfolio duration is minimized, while satisfying precedence relations and resource availabilities within a reasonable amount of time for small and large problem instances. In order to compare the efficiency of the proposed parallel GPU-based GA, problem is solved together with a CPU and a GPU. The results showed that GPU-based parallel GA has high potential for improving the performance of GAs for the RCMPSP particularly, for large-scale problems.