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.


    Access

    Access via TIB

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Priority-based scheduling of scarce resources


    Additional title:

    Prioritäten-Scheduling bei knappen Ressourcen


    Contributors:


    Publication date :

    1991


    Size :

    , 9 Quellen




    Type of media :

    Conference paper


    Type of material :

    Print


    Language :

    English






    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