This paper revisits the problem of on-line scheduling of sequential jobs with hard deadlines in a preemptive, multiprocessor setting. An on-line scheduling algorithm is said to be optimal if it can schedule any set of jobs to meet their deadlines whenever it is feasible in the off-line sense. It is known that the earliest-deadline-first strategy (EDF) is optimal in a one-processor setting, and there is no optimal on-line algorithm in an m-processor setting where m≥2. Recent work however reveals that if the on-line algorithm is given faster processors, EDF is actually optimal for all m (e.g., when m = 2, it suffices to use processors 1.5 times as fast). This paper initiates the study of the trade-off between increasing the speed and using more processors in deriving optimal on-line scheduling algorithms. Several upper bound and lower bound results are presented. For example, the speed requirement of EDF can be reduced to 2-1+p/m+p when it is given p≥0 extra processors. The main result is a new on-line algorithm which demands less speedy processors so as to attain optimality (e.g., when m = 2, the speed requirement is 1 1/3) and admits a better speed-processor trade-off than EDF (e.g., when m = 2 and p = 1, the speed requirement is 1.2). In general, no optimal algorithm exists when the speed factor is less than 1/(2√2+p/m-2). ; published_or_final_version


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Trade-offs between speed and processor in hard-deadline scheduling


    Beteiligte:
    Lam, Tak Wah (Autor:in) / To, Kar Keung (Autor:in)

    Erscheinungsdatum :

    1999-01-01


    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch


    Schlagwörter :

    Klassifikation :

    DDC:    629





    Trade-Offs between Security and Inspection Capacity

    Villegas, Hilma / Gurian, Patrick L. / Heyman, Josiah M. et al. | Transportation Research Record | 2006


    Measuring Trade-Offs Between Risk and Travel Time Based on Experimental Speed Data

    Intini, Paolo / Colonna, Pasquale / Berloco, Nicola et al. | Springer Verlag | 2016


    MMW system trade-offs

    Currie, N.C. / Parker, S.W. / Efurd, R.B. | IEEE | 1988