The Lazy Bureaucrat Problem

A casual look at a complex problem
compiled by Ernest Ersatz, Improbable Research staff

(Image credit: Flickr user Ari Moore)

The Lazy Bureaucrat Scheduling Problem is of recent vintage. Here are some of the earliest reports.

A Lazy Bureaucrat Problem
“The Lazy Bureaucrat Scheduling Problem,” Esther M. Arkin, Michael A. Bender, Joseph S.B. Mitchell, and Steven S. Skiena, Algorithms and Data Structures, vol. 1663, 1999, pp. 773–85. The authors, at State Universityof New York, Stony Brook, report:

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.

Another Lazy Bureaucrat Problem
“New Results for Lazy Bureaucrat Scheduling Problem,” Arash Farzan and Mohammad Ghodsi, 7th CSI Computer Conference (CSICC 2002), Iran Telecommunication Research Center, March 3–5, 2002, pp. 66–71. The authors, at Sharif University of Technology in Tehran, Iran, report:

In this paper we studies several versions of the lazy bureaucrat scheduling problems. In this new class of scheduling problems there is a lazy worker whose main objective is to be as inefficient as possible, in contrast to traditional scheduling problems in which the main objective is to be as efficient as possible.

And Another Lazy Bureaucrat Problem
“Common-Deadline Lazy Bureaucrat Scheduling Problems,” Behdad Esfahbod, Mohammad Ghodsi,    and Ali Sharifi, 7th Workshop on Algorithms and Data Structures (WADS 2003), vol. 2748, 2003, pp. 59-66.  The authors, at Sharif University of Technology in Tehran, Iran, report:

In this paper, we studied a new class of the Lazy Bureaucrat Scheduling Problems (LBSP), called common-deadline LBSP, where the deadlines of all jobs are the same.

(Image credit: Flickr user Roger H. Goun)

One More Lazy Bureaucrat Problem
“On Lazy Bureaucrat Scheduling with Common Deadlines,” L. Gai and G. Zhang, Journal of Combinatorial Optimization, vol. 15, no. 2, February 2008, pp. 191–9.  (Thanks to Matthias Ehrgott for bringing this to our attention.) The authors, at Zhejiang University in Hangzhou, China, say that:

“In this problem, the bureaucrat wants to do things as little (or easy) as possible… Of course there is… the busy requirement, that the bureaucrat must keep working as long as there are some executable jobs, otherwise… the optimal strategy for the bureaucrat would be just stay idle without doing anything.”

[Ed. note: pictures of Zora and Owen were used for illustrative purposes because cats are not as offended by the term "lazy" as human bureaucrats would be.]

_____________________

This article is republished with permission from the September-October 2009 issue of the Annals of Improbable Research. You can download or purchase back issues of the magazine, or subscribe to receive future issues. Or get a subscription for someone as a gift!

Visit their website for more research that makes people LAUGH and then THINK.