PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Complexity of scheduling of coupled tasks with chains precedence constraints and constant even length of the gap

Autorzy
Identyfikatory
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
The coupled tasks scheduling was originally introduced for modelling complex radar devices. It is still used for controlling such devices and applied in similar applications. This paper considers a problem of coupled tasks scheduling on one processor, under the assumptions that all processing times are equal to 1, the gap has an exact even length and the precedence constraints are strict. Although it is proven that the problem stated above is NP-hard in the strong sense if the precedence constraints have a form of a general graph, it is possible to solve some of its relaxed versions in polynomial time. This paper containts a solution for the problem of coupled tasks scheduling with assumption that the precedence constraints graph has a form of chains and it presents an algorithm which can solve the problem with such assumption in time O(n log n).
Słowa kluczowe
Rocznik
Strony
199--212
Opis fizyczny
Bibliogr. 10 poz.
Twórcy
autor
autor
  • Michał Tanaś - Applied Computer Science Division, Physics Faculty, Adam Mickiewicz University, Poznań, Poland, mail: Os. Zwycięstwa 3/30 61-643 Poznań, Poland, phone: +48668181768, Michal.Tanas@cs.put.poznan.pl
Bibliografia
  • [1] J.Błażewicz, V. Cellary. R. Słowiński, and J. Węglarz. Scheduling under Resource Constraints: Deterministic Models. J. C. Baltzer. Basel. 1986.
  • [2] K. Baker. Introduction to Sequencing and Scheduling. J. Wiley, New York, 1974.
  • [3| J. X. D. Gupta. Single facility scheduling with two operations per job and time-lags, preprint. 1994.
  • [4] E. L. Lawler, J. K. Lenstra. A. H. G. Rinnoy Kan, and D. B. Shmoys. Sequencing and scheduling: algorithms and complexity. Handbooks in Operations Research and Management Science. 4. 1993.
  • [5] A. J. Omian and G. N. Potts. On the complexity of coupled tasks scheduling. Discrete Applied Mathematics, 72:141-154. 1997.
  • [6] A. J. Orman. C. N. Potts. A. K. Shahani. and A. R. Moore. Scheduling for the control of a multifunctional radar system. European Journal of Operational Research, 90:13-25, 1996.
  • [7] A. J. Orman. A. K. Shahani. and A. R. Moore. Modelling for the control of a complex radar system. Computers Ops Res.. 25:239-249. 1998.
  • [8] A. H. G. Rinnooy-Kan. Machine Scheduling Problems: Classification, Complexity and Computations. Martinus Nijhoff. The Hague, 1976.
  • [9] R. D. Shapiro. Scheduling coupled tasks. Naval. Res. Logist. Quart, 27:477-481, 1980.
  • [10] W. Yu. The Two-machine Flow Shop Problem with Delays and the One-machine Total Tardiness Problem. Teehiiische Universiteit Eindhoven. 1996.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BPP1-0079-0067
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.