Skip to main content
SpringerLink
Log in

Randomized online algorithms for maximizing busy time interval scheduling

Randomisierte Online-Algorithmen zur Maximierung der Arbeitszeitintervalle

  • Published:
Computing Aims and scope Submit manuscript

Abstract

We consider the problem of scheduling tasks requiring certain processing times on one machine so that the busy time of the machine is maximized. The problem is to find a probabilistic online algorithm with reasonable worst case performance ratio. We answer an open problem of Lipton and Tompkins concerning the best possible ratio that can be achieved. Furthermore, we extend their results to anm-machine analogue. Finally, a variant of the problem is analyzed, in which the machine is provided with a buffer to store one job.

Zusammenfassung

Wir betrachten das Problem der Zuteilung von Aufgaben bestimmter Rechenzeit auf einem Rechner, um so seine Auslastung zu maximieren. Die Aufgabe besteht darin, einen probabilistischen Online-Algorithmus mit vernünftigem worst-case Performance-Verhältnis zu finden. Wir geben die Antwort auf ein offenes Problem von Lipton und Tompkins, das das bestmögliche Verhältnis betrifft. Weiter verallgemeinern wir ihre Ergebnisse auf einm-Maschinen-Analogon. Schließlich wird eine Variante des Problems analysiert, in dem der Rechner mit einem Zwischenspeicher für einen Job versehen ist.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Faigle, U., Nawijn, W. M.: Note on scheduling intervals online. Discrete Appl. Math.58, 13–18 (1995).

    MathSciNet  Google Scholar 

  2. Govindan, R., Anderson, D.: Scheduling an IPC mechanisms for continuous media. Technical report, UCB/CSD 91/622 Berkeley, 1992.

  3. Lipton, R. J., Tomkins, A: Online interval scheduling. To appear in: Proceedings symposium on Discrete Algorithms, January 23–25 1995. Arlington, VA.

Download references

Author information

Authors and Affiliations

  1. Faculty of Applied Mathematics, University of Twente, P.O. Box 217, NL-7500 AE, Enschede, The Netherlands

    U. Faigle, R. Garbe & W. Kern

Authors
  1. U. Faigle
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. R. Garbe
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. W. Kern
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Faigle, U., Garbe, R. & Kern, W. Randomized online algorithms for maximizing busy time interval scheduling. Computing 56, 95–104 (1996). https://doi.org/10.1007/BF02309339

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02309339

AMS Subject Classification

Key words

Search

Navigation