A note on the complexity of scheduling coupled tasks on a single processor

AUTOR(ES)

Blazewicz, Jacek, Ecker, Klaus, Kis, Tamás, Tanas, Michal

FONTE

Journal of the Brazilian Computer Society

DATA DE PUBLICAÇÃO

2001

RESUMO

This paper considers a problem of coupled task scheduling on one processor, where all processing times are equal to 1, the gap has exact length h, precedence constraints are strict and the criterion is to minimise the schedule length. This problem is introduced e.g. in systems controlling radar operations. We show that the general problem is NP-hard.

Documentos Relacionados

• A note on scheduling on a single processor with variable speed
• A NOTE ON THE CARDIAC OUTPUT OF A SINGLE INDIVIDUAL OBSERVED OVER A PERIOD OF FIVE YEARS
• THE SEX RATIO IN CONVULSIVE DISORDERS WITH A NOTE ON SINGLE-SEX SIBSHIPS
• Escalonamento memetico e neuro-memetico de tarefas
• A NOTE ON THE SPIROCHAETES OF TERMITES