Three parallel task assignment problems with shared resources. (2nd April 2020)

• Record Type: Journal Article
• Authors: Diabat, Ali; Dolgui, Alexandre; Janiak, Władysław; Kovalyov, Mikhail Y.
• Is Part Of: IISE transactions. Volume 52:Number 4(2020)
• Page Start: 478
• Page End: 485
• Publication Date: 2020-04-02
• Subjects: Resource allocation -- computational complexity -- polynomial algorithms -- cellular manufacturing -- parallel task computing; Industrial engineering -- Periodicals; Systems engineering -- Periodicals; Industrial engineering; Systems engineering; Electronic journals; Periodicals; 670.285
• DOI: 10.1080/24725854.2019.1680907
• Languages: English
• ISSNs: 2472-5854

Abstract

Abstract: We study three optimization problems in which non-renewable resources are used to execute tasks in parallel. Problems differentiate by the assumptions of whether a resource can be shared between several tasks or not, or whether resource sharing between the tasks is limited. We present very efficient solution procedures for two of these problems and prove that the third problem is NP-hard in the strong sense and that it can be solved efficiently for special cases. Applications include optimal resource allocation problems in labor-intensive cellular manufacturing and in parallel task computing.