Language:

Scheduling in the presence of processor networks : complexity and approximation

R.A.I.R.O. Recherche opérationnelle, 2012-01, Vol.46 (1), p.1-22 [Peer Reviewed Journal]

2015 INIST-CNRS ;EDP Sciences, ROADEF, SMAI, 2012 ;ISSN: 0399-0559 ;EISSN: 1290-3868 ;DOI: 10.1051/ro/2012005 ;CODEN: RSROD3

Full text available

Citations Cited by

Actions
1. Add to My Research
2. Remove from My Research
3. E-mail
4. Print
5. Permalink
6. Citation
7. EasyBib
8. EndNote
9. RefWorks
10. Delicious
11. Export RIS
12. Export BibTeX

Title:
Scheduling in the presence of processor networks : complexity and approximation
Author: Boudet, Vincent ; Cohen, Johanne ; Giroudeau, Rodolphe ; König, Jean-Claude
Subjects: 68Q17 ; 68W25 ; 90B35 ; Algorithmics. Computability. Computer arithmetics ; Algorithms ; Applied sciences ; Computer science; control theory; systems ; Computer systems and distributed systems. User interface ; Delay ; Exact sciences and technology ; Graphs ; Inventory control, production control. Distribution ; Mathematical analysis ; Microprocessors ; Multiprocessing ; Networks ; non-approximability ; Operational research and scientific management ; Operational research. Management science ; Operations research ; processor network model ; Schedules ; Scheduling ; Scheduling, sequencing ; Software ; Studies ; Theoretical computing
Is Part Of: R.A.I.R.O. Recherche opérationnelle, 2012-01, Vol.46 (1), p.1-22
Description: In this paper, we study the problem of makespan minimization for the multiprocessor scheduling problem in the presence of communication delays. The communication delay between two tasks i and j depends on the distance between the two processors on which these two tasks are executed. Lahlou shows that a simple polynomial-time algorithm exists when the length of the schedule is at most two (the problem becomes NP-complete when the length of the schedule is at most three). We prove that there is no polynomial-time algorithm with a performance guarantee of less than 4/3 (unless P = NP) to minimize the makespan when the network topology is a chain or ring and the precedence graph is a bipartite graph of depth one. We also develop two polynomial-time approximation algorithms with constant ratio dedicated to cases where the processor network admits a limited or unlimited number of processors. Dans cet article, nous étudions le problème de la minimisation de la longueur de l’ordonnancement pour un système multi-processeur en présence de délais de communication. Le délai de communication entre deux tâches i et j dépend de la distance entre les processeurs exécutant ces deux tâches. Un algorithme simple, de complexité polynomiale quand la longueur de l’ordonnancement est au plus deux (le problème devient NP-complet quand la longueur de l’ordonnancement est au plus trois) existe, voir [C. Lahlou, Ordonnancement dans les réseaux de processeurs : complexité et approximation. Ph.D. thesis, Université Paris VI (1998)]. pour ces deux résultats. Nous démontrons qu’il n’existe pas d’algorithme polynomial ρ-approché avec ρ < 4/3 sous l’hypothèse que P ≠ NP pour la minimisation de la longueur de l’ordonnancement dans le cas où le réseau de processeurs admet pour topologie une chaîne ou un anneau et le graphe de précédence est un graphe biparti de profondeur un. Nous avons également développé deux algorithmes d’approximation avec des garanties de performance constantes pour les versions limitées et non limitées sur le nombre de processeurs.
Publisher: Les Ulis: EDP Sciences
Language: English;French
Identifier: ISSN: 0399-0559
EISSN: 1290-3868
DOI: 10.1051/ro/2012005
CODEN: RSROD3
Source: Alma/SFX Local Collection

Back to results list


INSPIRE LIBRARY - TON DUC THANG UNIVERSITY	(84-028) 37 755 057	Feedback
19 Nguyen Huu Tho St. Dist.7, HCM	thuvien@tdtu.edu.vn	Feedback

Scheduling in the presence of processor networks : complexity and approximation

2015 INIST-CNRS ;EDP Sciences, ROADEF, SMAI, 2012 ;ISSN: 0399-0559 ;EISSN: 1290-3868 ;DOI: 10.1051/ro/2012005 ;CODEN: RSROD3

Searching Remote Databases, Please Wait