L-R: Lazy Bureaucrat Researchers "Kicking Back"; Joseph Mitchell, Steven Skiena, Michael Bender, Esther Arkin
How do you develop schedules for workers whose goal is to complete the least amount of work possible?
It’s an age-old problem and the question behind a study by four Stony Brook University professors, which was cited in a recent article of the United Kingdom newspaper The Guardian.
The study by Esther Arkin and Joseph Mitchell of the Department of Applied Mathematics and Statistics and Michael Bender and Steven Skiena of the Computer Science Department was published in 2003 in the journal Information and Computation. The team characterized their study of “The Lazy Bureaucrat Scheduling Problem” as:
“We introduce a new class of scheduling problems in which the optimization is performed by the worker (single “machine”) who performs the tasks. A typical worker’s objective is to minimize the amount of work he does (he is “lazy”), or more generally, to schedule as inefficiently (in some sense) as possible. The worker is subject to the constraint that he must be busy when there is work that he can do; we make this notion precise both in the preemptive and nonpreemptive settings. The resulting class of “perverse” scheduling problems, which we denote “Lazy Bureaucrat Problems,” gives rise to a rich set of new questions that explore the distinction between maximization and minimization in computing optimal schedules.”
Dr. Bender said the aim of the study was to develop a model for a real-life situation in which workers and bureaucrats given work will often attempt to do as little of the work as possible. The bureaucrats must appear busy when there are jobs in the queue, but they can choose what to work on to accomplish as little as possible. A typical scheduling problem would be to develop a schedule that so that you maximize the work that gets done. “We were looking at that from the other perspective,” he said. “The jobs arrive and have to be completed, but the individual workers want to work as inefficiently as possible subject to the constraint that if there’s work to do you have to do it, but if there are multiple tasks you chose the one that allows the least amount of work to be done.”
“It’s actually a very difficult problem,” Prof. Bender said. “If you’re really trying to be optimally lazy, it’s really more mathematically difficult to be optimally lazy than it is to be optimally efficient.”
A real world example of the problem was the “Schindler’s List” situation during World War II, Prof. Bender said, where German businessman Oskar Schindler saved more than a thousand Polish Jewish refugees from the Holocaust by employing them in his factories. The workers had to appear busy at all times in order to keep the factory running, but at the same time they wanted to contribute as little as possible to the German war effort.
“That’s a perfect historical example,” he said. “In real life situations there is work that needs to be done. Management wants certain tasks be completed but workers have a different perspective.”
The Guardian article looked at various studies of the problem of the lazy bureaucrat, and credited the Stony Brook team with being the first to issue a formal report on the problem.
“They had not contacted us about the article so we were not interviewed. We found out about it from Google alerts,” said Dr. Bender. “It was quite a pleasant surprise.”
As for the conclusion of their study, Dr. Bender said, “It opens up an exciting branch of study. If you try to understand how to schedule managers and workers in an organization, understanding that workers and bureaucrats can be lazy often gives you a more accurate description of what life is really like.
“It is exciting trying to formulate these in mathematical terms, and just doing that itself is a contribution. Doing that itself helps you understand the world. What we’re trying to do is model how things actually work.”
To see the Guardian article, go to http://www.guardian.co.uk/education/2010/feb/09/improbable-research-lazy-bureaucrats
To see the published paper on “The Lazy Bureaucrat,” go to http://arxiv.org/abs/cs/0210024
Source: Stony Brook University
