The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Kertas kerja ini menyiasat masalah penjadualan tugas selari bebas tanpa preemptif dalam persekitaran dengan berbilang mesin, yang bermotivasi daripada kajian terkini dalam penjadualan tugas dalam persekitaran berbilang mesin. Dalam persekitaran penjadualan ini, setiap mesin mengandungi beberapa pemproses yang sama dan setiap tugas selari secara serentak boleh memerlukan beberapa pemproses untuk pemprosesannya dalam mana-mana mesin tunggal. Setiap kali tugasan diproses secara selari dalam mesin selari, komunikasi mesej antara pemproses selalunya tidak dapat dielakkan. Masalah mencari panjang jadual terpendek untuk menjadualkan tugas selari bebas dengan pertimbangan overhed komunikasi dalam persekitaran berbilang mesin adalah NP-hard. Matlamat kertas kerja ini adalah untuk mencadangkan algoritma heuristik untuk masalah seperti ini dan menganalisis terikat prestasi algoritma heuristik ini.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Salinan
Jiann-Fu LIN, "Scheduling Parallel Tasks with Communication Overhead in an Environment with Multiple Machines" in IEICE TRANSACTIONS on Information,
vol. E91-D, no. 10, pp. 2379-2385, October 2008, doi: 10.1093/ietisy/e91-d.10.2379.
Abstract: This paper investigates the problem of nonpreemptively scheduling independent parallel tasks in an environment with multiple machines, which is motivated from the recent studies in scheduling tasks in a multi-machine environment. In this scheduling environment, each machine contains a number of identical processors and each parallel task can simultaneously require a number of processors for its processing in any single machine. Whenever tasks are processed in parallel in a parallel machine, message communication among processors is often inevitable. The problem of finding a shortest schedule length on scheduling independent parallel tasks with the consideration of communication overhead in a multi-machine environment is NP-hard. The aim of this paper is to propose a heuristic algorithm for this kind of problem and to analyze the performance bound of this heuristic algorithm.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e91-d.10.2379/_p
Salinan
@ARTICLE{e91-d_10_2379,
author={Jiann-Fu LIN, },
journal={IEICE TRANSACTIONS on Information},
title={Scheduling Parallel Tasks with Communication Overhead in an Environment with Multiple Machines},
year={2008},
volume={E91-D},
number={10},
pages={2379-2385},
abstract={This paper investigates the problem of nonpreemptively scheduling independent parallel tasks in an environment with multiple machines, which is motivated from the recent studies in scheduling tasks in a multi-machine environment. In this scheduling environment, each machine contains a number of identical processors and each parallel task can simultaneously require a number of processors for its processing in any single machine. Whenever tasks are processed in parallel in a parallel machine, message communication among processors is often inevitable. The problem of finding a shortest schedule length on scheduling independent parallel tasks with the consideration of communication overhead in a multi-machine environment is NP-hard. The aim of this paper is to propose a heuristic algorithm for this kind of problem and to analyze the performance bound of this heuristic algorithm.},
keywords={},
doi={10.1093/ietisy/e91-d.10.2379},
ISSN={1745-1361},
month={October},}
Salinan
TY - JOUR
TI - Scheduling Parallel Tasks with Communication Overhead in an Environment with Multiple Machines
T2 - IEICE TRANSACTIONS on Information
SP - 2379
EP - 2385
AU - Jiann-Fu LIN
PY - 2008
DO - 10.1093/ietisy/e91-d.10.2379
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E91-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 2008
AB - This paper investigates the problem of nonpreemptively scheduling independent parallel tasks in an environment with multiple machines, which is motivated from the recent studies in scheduling tasks in a multi-machine environment. In this scheduling environment, each machine contains a number of identical processors and each parallel task can simultaneously require a number of processors for its processing in any single machine. Whenever tasks are processed in parallel in a parallel machine, message communication among processors is often inevitable. The problem of finding a shortest schedule length on scheduling independent parallel tasks with the consideration of communication overhead in a multi-machine environment is NP-hard. The aim of this paper is to propose a heuristic algorithm for this kind of problem and to analyze the performance bound of this heuristic algorithm.
ER -