Publication:
Performance of local search heuristics on scheduling a class of pipelined multiprocessor tasks

dc.contributor.coauthorErcan, MF
dc.contributor.departmentDepartment of Industrial Engineering
dc.contributor.kuauthorOğuz, Ceyda
dc.contributor.schoolcollegeinstituteCollege of Engineering
dc.date.accessioned2024-11-09T23:52:22Z
dc.date.issued2005
dc.description.abstractThis paper presents the evaluation of the solution quality of heuristic algorithms developed for scheduling multiprocessor tasks for a class of multiprocessor architectures designed to exploit temporal and spatial parallelism simultaneously. More specifically, we deal with multi-level or partitionable architectures where MIMD parallelism and multiprogramming support are the two main characteristics of the system. We investigate scheduling a number of pipelined multiprocessor tasks with arbitrary processing times and arbitrary processor requirements in this system. The scheduling problem consists of two interrelated sub-problems, which are finding a sequence of pipelined multiprocessor tasks on a processor and finding a proper mapping of tasks to the processors that are already being sequenced. For the solution of the second problem, various techniques are available. However, the problem remains of generating a feasible sequence for the pipelined operations. We employed three well-known local search heuristic algorithms that are known to be robust methods applicable to various optimization problems. These are Simulated Annealing, Tabu Search, and Genetic Algorithms. We then conduct computational experiments and evaluate the reduction achieved in completion time by each heuristic. We have also compared the results with well-known simple list-based heuristics. (c) 2005 Elsevier Ltd. .
dc.description.indexedbyWOS
dc.description.indexedbyScopus
dc.description.issue8
dc.description.openaccessNO
dc.description.publisherscopeInternational
dc.description.sponsoredbyTubitakEuN/A
dc.description.volume31
dc.identifier.doi10.1016/j.compeleceng.2005.09.004
dc.identifier.issn0045-7906
dc.identifier.quartileQ2
dc.identifier.scopus2-s2.0-32444446745
dc.identifier.urihttps://doi.org/10.1016/j.compeleceng.2005.09.004
dc.identifier.urihttps://hdl.handle.net/20.500.14288/14846
dc.identifier.wos235759300003
dc.keywordsMultiprocessor task scheduling
dc.keywordsMetaheuristics
dc.keywordsParallel computing
dc.keywordsGenetic algorithms
dc.keywordsHybrid flowshop
dc.language.isoeng
dc.publisherPergamon-Elsevier Science Ltd
dc.relation.ispartofComputers & Electrical Engineering
dc.subjectComputer science
dc.subjectEngineering
dc.subjectElectrical and electronic Engineering
dc.titlePerformance of local search heuristics on scheduling a class of pipelined multiprocessor tasks
dc.typeJournal Article
dspace.entity.typePublication
local.contributor.kuauthorOğuz, Ceyda
local.publication.orgunit1College of Engineering
local.publication.orgunit2Department of Industrial Engineering
relation.isOrgUnitOfPublicationd6d00f52-d22d-4653-99e7-863efcd47b4a
relation.isOrgUnitOfPublication.latestForDiscoveryd6d00f52-d22d-4653-99e7-863efcd47b4a
relation.isParentOrgUnitOfPublication8e756b23-2d4a-4ce8-b1b3-62c794a8c164
relation.isParentOrgUnitOfPublication.latestForDiscovery8e756b23-2d4a-4ce8-b1b3-62c794a8c164

Files