Scheduling for flow-time with admission control

N. Bansal, A. Blum, S. Chawla, K. Dhamdhere

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    12 Citaten (Scopus)
    1 Downloads (Pure)


    We consider the problem of scheduling jobs on a single machine with preemption, when the server is allowed to reject jobs at some penalty. We consider minimizing two objectives: total flow time and total job-idle time (the idle time of a job is the flow time minus the processing time). We give 2-competitive online algorithms for the two objectives and extend some of our results to the case of weighted flow time and machines with varying speeds. We also give a resource augmentation result for the case of arbitrary penalties achieving a competitive ratio of O(1/epsilon(log W + log C)(2)) using a (1+epsilon) speed processor. Finally, we present a number of lower bounds for both the case of uniform and arbitrary penalties.
    Originele taal-2Engels
    TitelAlgorithms - ESA 2003 (11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003. Proceedings)
    RedacteurenG. Di Battista, U. Zwick
    Plaats van productieBerlin
    ISBN van geprinte versie3-540-20064-9
    StatusGepubliceerd - 2003

    Publicatie series

    NaamLecture Notes in Computer Science
    ISSN van geprinte versie0302-9743


    Duik in de onderzoeksthema's van 'Scheduling for flow-time with admission control'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit