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 preblems, 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.
Recently Hepner and Stein @cite_5 published a pseudo-polynomial-time algorithm for minimizing the makespan subject to preemption constraint II, thus resolving an open problem from an earlier version of this paper @cite_3 . They also extend the LBP to the parallel setting, in which there are multiple bureaucrats.
@cite_5 @cite_3
1565331571 2568731922
We study the problem of minimizing makespan for the Lazy Bureaucrat Scheduling Problem. We give a pseudopolynomial time algorithm for a preemptive scheduling problem, resolving an open problem by We also extend the definition of Lazy Bureaucrat scheduling to the multiple-bureaucrat (parallel) setting, and provide pseudopolynomial-time algorithms for problems in that model. 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.