The lazy bureaucrat scheduling problem

Esther M. Arkin; Michael A. Bender; Joseph S.B. Mitchell; Steven S. Skiena

doi:10.1007/3-540-48447-7_14

The lazy bureaucrat scheduling problem

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Scopus citations

Abstract

We introduce a new class of scheduling problems in which the optimization is performed by the worker (single “machine”) who performs the tasks. The worker’s objective may be to minimize the amount of work he does (he is “lazy”). He is subject to a constraint that he must be busy when there is work that he can do; we make this notion precise, particularly when preemption is allowed. The resulting class of “perverse” scheduling problems, which we term “Lazy Bureaucrat Problems,” gives rise to a rich set of new questions that explore the distinction between maximization and minimization in computing optimal schedules.

Original language	English
Title of host publication	Algorithms and Data Structures - 6th International Workshop, WADS 1999, Proceedings
Editors	Frank Dehne, Jorg-Rudiger Sack, Arvind Gupta, Roberto Tamassia
Publisher	Springer Verlag
Pages	122-133
Number of pages	12
ISBN (Print)	3540662790, 9783540662792
DOIs	https://doi.org/10.1007/3-540-48447-7_14
State	Published - 1999
Event	6th International Workshop on Algorithms and Data Structures, WADS 1999 - Vancouver, Canada Duration: Aug 11 1999 → Aug 14 1999

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1663
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	6th International Workshop on Algorithms and Data Structures, WADS 1999
Country/Territory	Canada
City	Vancouver
Period	08/11/99 → 08/14/99

Access to Document

10.1007/3-540-48447-7_14

Cite this

Arkin, E. M., Bender, M. A., Mitchell, J. S. B., & Skiena, S. S. (1999). The lazy bureaucrat scheduling problem. In F. Dehne, J.-R. Sack, A. Gupta, & R. Tamassia (Eds.), Algorithms and Data Structures - 6th International Workshop, WADS 1999, Proceedings (pp. 122-133). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1663). Springer Verlag. https://doi.org/10.1007/3-540-48447-7_14

Arkin, Esther M. ; Bender, Michael A. ; Mitchell, Joseph S.B. et al. / The lazy bureaucrat scheduling problem. Algorithms and Data Structures - 6th International Workshop, WADS 1999, Proceedings. editor / Frank Dehne ; Jorg-Rudiger Sack ; Arvind Gupta ; Roberto Tamassia. Springer Verlag, 1999. pp. 122-133 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2b89dff08b304fc5b20b4bbea5ccaf5f,

title = "The lazy bureaucrat scheduling problem",

abstract = "We introduce a new class of scheduling problems in which the optimization is performed by the worker (single “machine”) who performs the tasks. The worker{\textquoteright}s objective may be to minimize the amount of work he does (he is “lazy”). He is subject to a constraint that he must be busy when there is work that he can do; we make this notion precise, particularly when preemption is allowed. The resulting class of “perverse” scheduling problems, which we term “Lazy Bureaucrat Problems,” gives rise to a rich set of new questions that explore the distinction between maximization and minimization in computing optimal schedules.",

author = "Arkin, \{Esther M.\} and Bender, \{Michael A.\} and Mitchell, \{Joseph S.B.\} and Skiena, \{Steven S.\}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1999.; 6th International Workshop on Algorithms and Data Structures, WADS 1999 ; Conference date: 11-08-1999 Through 14-08-1999",

year = "1999",

doi = "10.1007/3-540-48447-7\_14",

language = "English",

isbn = "3540662790",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "122--133",

editor = "Frank Dehne and Jorg-Rudiger Sack and Arvind Gupta and Roberto Tamassia",

booktitle = "Algorithms and Data Structures - 6th International Workshop, WADS 1999, Proceedings",

}

Arkin, EM , Bender, MA , Mitchell, JSB & Skiena, SS 1999, The lazy bureaucrat scheduling problem. in F Dehne, J-R Sack, A Gupta & R Tamassia (eds), Algorithms and Data Structures - 6th International Workshop, WADS 1999, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1663, Springer Verlag, pp. 122-133, 6th International Workshop on Algorithms and Data Structures, WADS 1999, Vancouver, Canada, 08/11/99. https://doi.org/10.1007/3-540-48447-7_14

The lazy bureaucrat scheduling problem. / Arkin, Esther M.; Bender, Michael A.; Mitchell, Joseph S.B. et al.
Algorithms and Data Structures - 6th International Workshop, WADS 1999, Proceedings. ed. / Frank Dehne; Jorg-Rudiger Sack; Arvind Gupta; Roberto Tamassia. Springer Verlag, 1999. p. 122-133 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1663).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - The lazy bureaucrat scheduling problem

AU - Arkin, Esther M.

AU - Bender, Michael A.

AU - Mitchell, Joseph S.B.

AU - Skiena, Steven S.

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1999.

PY - 1999

Y1 - 1999

N2 - We introduce a new class of scheduling problems in which the optimization is performed by the worker (single “machine”) who performs the tasks. The worker’s objective may be to minimize the amount of work he does (he is “lazy”). He is subject to a constraint that he must be busy when there is work that he can do; we make this notion precise, particularly when preemption is allowed. The resulting class of “perverse” scheduling problems, which we term “Lazy Bureaucrat Problems,” gives rise to a rich set of new questions that explore the distinction between maximization and minimization in computing optimal schedules.

AB - We introduce a new class of scheduling problems in which the optimization is performed by the worker (single “machine”) who performs the tasks. The worker’s objective may be to minimize the amount of work he does (he is “lazy”). He is subject to a constraint that he must be busy when there is work that he can do; we make this notion precise, particularly when preemption is allowed. The resulting class of “perverse” scheduling problems, which we term “Lazy Bureaucrat Problems,” gives rise to a rich set of new questions that explore the distinction between maximization and minimization in computing optimal schedules.

UR - https://www.scopus.com/pages/publications/84948992864

U2 - 10.1007/3-540-48447-7_14

DO - 10.1007/3-540-48447-7_14

M3 - Conference contribution

AN - SCOPUS:84948992864

SN - 3540662790

SN - 9783540662792

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 122

EP - 133

BT - Algorithms and Data Structures - 6th International Workshop, WADS 1999, Proceedings

A2 - Dehne, Frank

A2 - Sack, Jorg-Rudiger

A2 - Gupta, Arvind

A2 - Tamassia, Roberto

PB - Springer Verlag

T2 - 6th International Workshop on Algorithms and Data Structures, WADS 1999

Y2 - 11 August 1999 through 14 August 1999

ER -

Arkin EM , Bender MA , Mitchell JSB , Skiena SS. The lazy bureaucrat scheduling problem. In Dehne F, Sack JR, Gupta A, Tamassia R, editors, Algorithms and Data Structures - 6th International Workshop, WADS 1999, Proceedings. Springer Verlag. 1999. p. 122-133. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-48447-7_14

The lazy bureaucrat scheduling problem

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this