Scheduling UET-UCT tasks: Branch-and-bound search in the priority space.

*(English)*Zbl 1239.90055Summary: The paper is concerned with the problem of scheduling partially ordered unit execution time tasks on parallel processors with unit communication delays and release times. Two criteria are considered, the maximum lateness and its particular case, the makespan. This problem plays an important role in scheduling theory and was originally inspired by the applications to multi-processor computer systems. It is well known that for both criteria the problem is NP-hard in the strong sense. The paper presents an implementation of the branch-and-bound method which does not partition the feasible region explicitly. The theoretical results are complemented by computational experiments.

##### Keywords:

scheduling; parallel processors; partially ordered tasks; unit communication delay; maximum lateness; release times
PDF
BibTeX
XML
Cite

\textit{Y. Zinder} et al., Optim. Eng. 11, No. 4, 627--646 (2010; Zbl 1239.90055)

Full Text:
DOI

##### References:

[1] | Brucker P (2004) Scheduling algorithms, 4th edn. Springer, Berlin · Zbl 1060.90034 |

[2] | ChrĂ©tienne P, Picouleau C (1995) Scheduling with communication delays: a survey. In: Scheduling theory and its applications. Wiley, New York, pp 65–90 |

[3] | Finke G, Gordon V, Proth J (2004) Scheduling with due dates (annotated bibliography of complexity and algorithms). Tech Rep 42, Laboratoire Leibniz-IMAG |

[4] | Garey M, Johnson D (1976) Scheduling tasks with nonuniform deadlines on two processors. J Assoc Comput Mach 23(3):461–467 · Zbl 0338.68048 |

[5] | Graham R, Lawler E, Lenstra J, Kan AR (1979) Optimization and approximation in deterministic machine scheduling: a survey. Ann Discrete Math 5:287–326 · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X |

[6] | Kowk Y, Ahmad I (1997) Efficient scheduling of arbitrary task graphs to multiprocessors using a parallel genetic algorithm. J Parallel Distrib Comput 47:58–77 · Zbl 05470847 · doi:10.1006/jpdc.1997.1395 |

[7] | Pinedo M (2002) Scheduling: theory, algorithms, and systems. Prentice Hall, New York · Zbl 1145.90394 |

[8] | Rayward-Smith V (1987) UET scheduling with unit interprocessor communication delays. Discrete Appl Math 18:55–71 · Zbl 0634.90031 · doi:10.1016/0166-218X(87)90042-4 |

[9] | Zinder Y (2003) An iterative algorithm for scheduling uet tasks with due dates and release times. Eur J Oper Res 149:404–416 · Zbl 1059.90078 · doi:10.1016/S0377-2217(02)00770-1 |

[10] | Zinder Y, Roper D (1998) An iterative algorithm for scheduling unit-time tasks with precedence constraints to minimise the maximum lateness. Ann Oper Res 81:321–340 · Zbl 0908.90178 · doi:10.1023/A:1018917426360 |

[11] | Zinder Y, Singh G, Weiskircher R (2006) A new method of scheduling unit time tasks on parallel machines. In: Lecture notes in engineering and computer science. Springer, Berlin, pp 796–801 |

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.