In the priority scheduling problem limited resources must be assigned to prioritized jobs of fixed duration. The optimal solution to an instance of the priority scheduling problem assigns resources to as many top priority jobs as possible. The priority scheduling problem is formalized, and it is proved that it is computationally difficult, or NP-hard. An exponential though efficient algorithm which obtains optimal solutions is also proposed. The algorithm is demonstrated on several vexing problems. Finally, modifications to the algorithm which would allow it to obtain 'near optimal' solutions in polynomial time are suggested.


    Zugriff

    Zugriff über TIB

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Priority-based scheduling of scarce resources


    Weitere Titelangaben:

    Prioritäten-Scheduling bei knappen Ressourcen


    Beteiligte:
    McDowell, M.E. (Autor:in)


    Erscheinungsdatum :

    1991


    Format / Umfang :

    , 9 Quellen




    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Print


    Sprache :

    Englisch





    Autonomous construction using scarce resources in unknown environments

    Magnenat, S. p. | British Library Online Contents | 2012



    MAV strives to make the most of scarce resources

    British Library Online Contents | 1996


    Erratum to: Autonomous construction using scarce resources in unknown environments

    Magnenat, S. p. / Philippsen, R. / Mondada, F. | British Library Online Contents | 2012