Li, Fei2014-09-162014-09-162014-07https://hdl.handle.net/11299/165724University of Minnesota Ph.D. dissertation. July 2014. Major: Industrial and Systems Engineering. Advisor: Diwakar Gupta. 1 computer file (PDF); viii, 141 pages.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.en-USThesis or Dissertation