Essays on scheduling models in service systems
2014-07
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Essays on scheduling models in service systems
Authors
Published Date
2014-07
Publisher
Type
Thesis or Dissertation
Abstract
Scheduling has been a fundamental area in Operations Research and is receiving increasing attention. Growing scale of operations and increasing availability of data in different industries drive the need for efficient and practical solutions for scheduling resources under customized circumstances. In this thesis, we address three different scheduling problems that come from transit industry and healthcare industry respectively. According to the special features encountered in each industry, we build fixed job scheduling models for the reserve driver scheduling and work assignment problems for transit industry, and resource-constrained bin packing models for the surgery reschedul- ing problems in healthcare. Three separate but related chapters constitute the main body of the thesis.Among the three models, two models are deterministic and are proved to be NP- hard. The other model is an online version of the reserve driver work assignment problem. Our target is to provide algorithms that run in polynomial or pseudo-polynomial time and can beat the best-known algorithm in terms of worst-case performance guarantee. For the offline reserve driver scheduling and work assignment problem, we provide an algorithm with approximation ratio between [1 − 1/e, 19/27]; and for the online reserve driver work assignment problem, we build a randomized algorithm with O(log(Delta)) competitive ratio, where is the ratio of the longest to the shortest job in duration. For the surgery rescheduling problem the model is not widely studied and we are the first to provide an algorithm and a lower bound with performance guarantee--the worst-case performance guarantee is 3/2 for the approximation algorithm, and 2/3 for the lower bound. We not only are interested in theoretical results but also care about practical use of our algorithms. All algorithms are experimented with real data and we benchmark with either the current industry performance or a greedy algorithm/policy.
Keywords
Description
University of Minnesota Ph.D. dissertation. July 2014. Major: Industrial and Systems Engineering. Advisor: Diwakar Gupta. 1 computer file (PDF); viii, 141 pages.
Related to
Replaces
License
Collections
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Li, Fei. (2014). Essays on scheduling models in service systems. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/165724.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.