American Journal of Operations Research

Volume 6, Issue 1 (January 2016)

ISSN Print: 2160-8830   ISSN Online: 2160-8849

Google-based Impact Factor: 0.84  Citations  

An O(n) Time Algorithm for Scheduling UET-UCT of Bipartite Digraphs of Depth One on Two Processors

HTML  XML Download Download as PDF (Size: 320KB)  PP. 75-80  
DOI: 10.4236/ajor.2016.61010    3,667 Downloads   4,422 Views  Citations
Author(s)

ABSTRACT

Given n unit execution time (UET) tasks whose precedence constraints form a directed acyclic graph, the arcs are associated with unit communication time (UCT) delays. The problem is to schedule the tasks on two identical processors in order to minimize the makespan. Several polynomial algorithms in the literature are proposed for special classes of digraphs, but the complexity of solving this problem in general case is still a challenging open question. We present in this paper an O(n) time algorithm to compute an optimal schedule for the class of bipartite digraphs of depth one.

Share and Cite:

Quaddoura, R. (2016) An O(n) Time Algorithm for Scheduling UET-UCT of Bipartite Digraphs of Depth One on Two Processors. American Journal of Operations Research, 6, 75-80. doi: 10.4236/ajor.2016.61010.

Cited by

[1] Scheduling UET-UCT DAGs of Depth Two on Two Processors
2021 22nd International Arab …, 2021

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.