Complexity of scheduling of coupled tasks with chains precedence constraints and any constant length of gap / K. Ecker in Journal of the operational research society (JORS), Vol. 63 N° 4 (Avril 2012)  

Public ISBD [article]  inJournal of the operational research society (JORS) > Vol. 63 N° 4 (Avril 2012) . - pp. 524–529 Titre : Complexity of scheduling of coupled tasks with chains precedence constraints and any constant length of gap Type de document : texte imprimé Auteurs : K. Ecker, Auteur ; M. Tanas, Auteur Année de publication : 2012 Article en page(s) : pp. 524–529 Note générale : Recherche opérationnelle Langues : Anglais (eng) Mots-clés : Coupled tasks Scheduling Complexity theory Index. décimale : 001.424 Résumé : 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 a constant exact 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 contains a solution for the problem of coupled tasks scheduling with an assumption that the precedence constraints graph has a form of chains and it presents an algorithm that can solve the problem with such assumption in time O(n log n). DEWEY : 001.424 ISSN : 0160-5682 En ligne : http://www.palgrave-journals.com/jors/journal/v63/n4/abs/jors201132a.html [article] Complexity of scheduling of coupled tasks with chains precedence constraints and any constant length of gap [texte imprimé] / K. Ecker, Auteur ; M. Tanas, Auteur . - 2012 . - pp. 524–529. Recherche opérationnelle Langues : Anglais (eng) in Journal of the operational research society (JORS) > Vol. 63 N° 4 (Avril 2012) . - pp. 524–529 Mots-clés : Coupled tasks Scheduling Complexity theory Index. décimale : 001.424 Résumé : 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 a constant exact 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 contains a solution for the problem of coupled tasks scheduling with an assumption that the precedence constraints graph has a form of chains and it presents an algorithm that can solve the problem with such assumption in time O(n log n). DEWEY : 001.424 ISSN : 0160-5682 En ligne : http://www.palgrave-journals.com/jors/journal/v63/n4/abs/jors201132a.html

Exemplaires

Code-barres	Cote	Support	Localisation	Section	Disponibilité
aucun exemplaire