Multiprocessor Task Scheduling in Multistage Hybrid Flow-Shops: A Parallel Greedy Algorithm Approach
Yükleniyor...
Dosyalar
Tarih
2010
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
ELSEVIER
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
Hybrid flow shop scheduling problems have a special structure combining some elements of both the flow shop and the parallel machine scheduling problems. Multiprocessor task scheduling problem can be stated as finding a schedule for a general task graph to execute on a multiprocessor system so that the schedule length can be minimized. Hybrid Flow Shop Scheduling with Multiprocessor Task (HFSMT) problem is known to be NP-hard. In this study we present an effective parallel greedy algorithm to solve HFSMT problem. Parallel greedy algorithm (PGA) is applied by two phases iteratively, called destruction and construction. Four constructive heuristic methods are proposed to solve HFSMT problems. A preliminary test is performed to set the best values of control parameters, namely population size, subgroups number, and iteration number. The best values of control parameters and operators are determined by a full factorial experimental design using our PGA program. Computational results are compared with the earlier works of Oguz et al. [1,3], and Oguz [2]. The results indicate that the proposed parallel greedy algorithm approach is very effective in terms of reduced total completion time or makespan (C-max) for the attempted problems.
Açıklama
Anahtar Kelimeler
Hybrid Flow Shop, Multiprocessor Tasks Scheduling Problems, Parallel Greedy Algorithm
Kaynak
Applied Soft Computing
WoS Q Değeri
Q1
Scopus Q Değeri
Q1
Cilt
10
Sayı
4
Künye
Kahraman, C., Engin, O., Kaya, İ., Öztürk, R. E., (2010). Multiprocessor Task Scheduling in Multistage Hybrid Flow-Shops: A Parallel Greedy Algorithm Approach. Applied Soft Computing, 10(4), 1293-1300.
DOI: 10.1016/j.asoc.2010.03.008
