New complexity results on scheduling with small communication delays.

*(English)*Zbl 0837.68009Summary: Although most of the scheduling problems with interprocessor communication delays have been shown to be NP-complete, some important special cases were still unsolved. This paper deals with the problem where communication times are smaller than processing times and task duplication is not allowed. We prove that this problem is NP-complete and we give an efficient approximate algorithm with performance guarantee.

##### MSC:

68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |

68R10 | Graph theory (including graph drawing) in computer science |

68Q25 | Analysis of algorithms and problem complexity |

PDF
BibTeX
XML
Cite

\textit{C. Picouleau}, Discrete Appl. Math. 60, No. 1--3, 331--342 (1995; Zbl 0837.68009)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Chrétienne, P., Task scheduling with interprocessor communication delays, European J. oper. res., 57, 348-354, (1992) · Zbl 0761.90057 |

[2] | Chrétienne, P., Tree scheduling with communication delays, Discrete appl. math., 49, 129-141, (1994) · Zbl 0799.90062 |

[3] | Chrétienne, P.; Picouleau, C., The basic scheduling problem with interprocessor communication delays, MASI report 91.6, (1991) |

[4] | Colin, J.Y.; Chrétienne, P., C.P.M. scheduling with small interprocessor communication delays, Oper. res., 39, 680-684, (1991) · Zbl 0793.68012 |

[5] | Garey, M.R.; Johnson, D.S., Computers and intractability, a guide to the theory of NP-completeness, (1979), Freeman San Francisco, CA · Zbl 0411.68039 |

[6] | Papadimitriou, C.H.; Yannakakis, M., Towards an architecture-independent analysis of parallel algorithms, SIAM J. comput., 19, 322-328, (1990) · Zbl 0692.68032 |

[7] | Rayward-Smith, V.J., UET scheduling with unit interprocessor communication delays, Discrete appl. math., 18, 55-71, (1987) · Zbl 0634.90031 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.