Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Minimizing Makespan for the Lazy Bureaucrat Problem

Clint HepnerContact Information and Cliff SteinContact Information

(6)  Department of Computer Science, Dartmouth College, Hanover, NH, 03755
(7)  Department of Industrial Engineering and Operations Research, Columbia University, New York NY, 10027
Abstract
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 Arkin et al. 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.
Research partially supported by NSF Grant EIA-98-02068, NSF Grant DMI-9970063 and an Alfred P. Sloan Foundation Fellowship

Contact Information Clint Hepner
Email: chepner@cs.dartmouth.edu

Contact Information Cliff Stein
Email: cliff@ieor.columbia.edu
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Referenced by
2 newer articles

  1. Bender, Michael A. (2008) Scheduling algorithms for procrastinators. Journal of Scheduling 11(2)
    [CrossRef]
  2. Gai, Ling (2008) On lazy bureaucrat scheduling with common deadlines. Journal of Combinatorial Optimization 15(2)
    [CrossRef]
Remote Address: 38.107.191.105 • Server: mpweb01
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)