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

• Autorzy: Ecker K. , Tanaś M.
• 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

EN

scheduling; complexity theory

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2007
• Tom: Vol. 32, No. 3
• Strony: 199--212
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Ecker K.

autor

Tanaś M.

• Michał Tanaś - Applied Computer Science Division, Physics Faculty, Adam Mickiewicz University, Poznań, Poland, mail: Os. Zwycięstwa 3/30 61-643 Poznań, Poland, phone: [phone],

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.