zbMATH — the first resource for mathematics

Three, four, five, six, or the complexity of scheduling with communication delays. (English) Zbl 0816.90083
Summary: A set of unit-time tasks has to be processed on identical parallel processors subject to precedence constraints and unit-time communication delays; does there exist a schedule of length at most \(d\)? The problem has two variants, depending on whether the number of processors is restrictively small or not. For the first variant the question can be answered in polynomial time for \(d= 3\) and is NP-complete for \(d= 4\). The second variant is solvable in polynomial time for \(d= 5\) and NP-complete for \(d= 6\). As a consequence, neither of the corresponding optimization problems has a polynomial approximation scheme, unless \(P= \text{NP}\).

90B35 Deterministic scheduling theory in operations research
65Y05 Parallel numerical computation
90C60 Abstract computational complexity for mathematical programming problems
Full Text: DOI
[1] Colin, J.Y.; Chrétienne, P., C.P.M. scheduling with small communication delays and task duplication, Oper. res., 39, 681-684, (1991) · Zbl 0793.68012
[2] Graham, R.L.; Lawler, E.L.; Lenstra, J.K.; Rinnooy Kan, A.H.G., Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. discrete math., 5, 287-326, (1979) · Zbl 0411.90044
[3] Lenstra, J.K.; Rinnooy Kan, A.H.G., Complexity of scheduling under precedence constraints, Oper. res., 26, 22-35, (1978) · Zbl 0371.90060
[4] J.K. Lenstra, M. Veldhorst and B. Veltman, “The complexity of scheduling trees with communication delays”, submitted for publication. · Zbl 0840.68013
[5] Munier, A.; König, J.-C., A heuristic for a scheduling problem with communication delays, () · Zbl 0892.90104
[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] Picouleau, C., Ordonnancement de tâches de durée unitaire avec des délais de communication unitaires sur m processeurs, ()
[8] Picouleau, C., Two new NP-complete scheduling problems with communication delays and unlimited number of processors, ()
[9] Rayward-Smith, V.J., UET scheduling with unit interprocessor communication delays, Discrete appl. math., 18, 55-71, (1987) · Zbl 0634.90031
[10] Schrijver, A., Theory of linear and integer programming, (1986), Wiley Chichester · Zbl 0665.90063
[11] Varvarigou, T.A.; Roychowdhury, V.P.; Kailath, T., Scheduling in and out forests in the presence of communication delays, (1992), Unpublished manuscript
[12] Veltman, B.; Lageweg, B.J.; Lenstra, J.K., Multiprocessor scheduling with communication delays, Parallel comput., 16, 173-182, (1990) · Zbl 0711.68017
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.