| Titre : | Complexity of scheduling of coupled tasks with chains precedence constraints and any constant length of gap (2012) |
| Auteurs : | K. Ecker, Auteur ; M. Tanas, Auteur |
| Type de document : | Article : texte imprimé |
| Dans : | Journal of the operational research society (JORS) (Vol. 63 N° 4, Avril 2012) |
| Article en page(s) : | pp. 524–529 |
| Note générale : | Recherche opérationnelle |
| Langues : | Anglais |
| Index. décimale : | 001.424 |
| Tags : | Coupled tasks Scheduling Complexity theory |
| 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 |
