Optimization Models And Algorithms For Three Complex Scheduling Problems In Operations Management

Scheduling studies how to allocate scarce resources to a set of tasks over time to optimize one or more performance criteria.Traditional scheduling models are largely motivated by the practices of manufacturing operations.In recent years,with the development of healthcare service and supply chain management,new scheduling problems arising from these areas have been attracting wide attention.Such new models motivated by new applications in healthcare service and supply chain management typically possess unique modelling elements and have different or more complicated constraint and objective function structures.In this thesis,we aim to study three important complex scheduling problems in healthcare service and supply chain management,which are operating room planning and scheduling with various constraints,fulfilment scheduling in omni-channel retailing,and supply-production coordination in supply chains:First,motivated by common practices in hospital operations,we study integrated planning and scheduling of operating rooms(ORs)for elective surgeries.The decisions include determining a subset of ORs to open each day,assigning available surgeries into specific days and rooms and scheduling the assigned surgeries in each room on each day,in the presence of eligibility constraints between ORs and surgeries,surgery ready dates and deadlines,and surgery intraday time window requirements.The objective is to minimize the sum of the total setup cost of opening ORs and the total overtime cost of the opened ORs.We consider four specific problems with deterministic surgery times.For the two problems where there are a fixed number of planning days and a fixed number of surgery types,we develop polynomial time algorithms to find optimal solutions.For the problem with an arbitrary number of planning days and an arbitrary number of surgery types,we propose an exact branch-and-price algorithm when the surgery time windows are agreeable,and propose an efficient column generation based heuristic when the surgery time windows are non-agreeable.Second,we study fulfillment scheduling decisions of buy-online-pickup-instore(BOPS)orders arising from omni-channel retailing destined for a single store of a retailer.There are two fulfillment options for BOPS orders: they can be either processed at a fulfillment center(FC)and delivered to the store,or processed at the store without needing delivery.There are two types of trucks available to deliver the BOPS orders fulfilled at the FC: prescheduled trucks that are already committed to replenishing store inventory and have some spare capacity that can be utilized,and additional trucks that can be hired from 3PL providers.There is a fixed cost for using each truck;the cost for using a prescheduled truck is lower than that for using an additional truck.If an order is fulfilled at the store,it incurs a processing cost and a processing time,whereas the processing cost and time are negligible if an order is fulfilled at the FC.The problem is to determine where to fulfill each order(FC versus the store),how to assign the orders fulfilled at the FC to trucks for delivery,and how to schedule the orders fulfilled at the store for store processing,so as to minimize the total fulfillment cost,including the delivery cost from the FC to the store incurred by the orders processed at the FC,and the processing cost for fulfilling the rest of the orders at the store,subject to the constraint that each order is ready for pickup at the store by its promised pickup ready time.We consider various cases of the problem by clarifying their computational complexity,proposing optimal polynomial-time or pseudo-polynomial time algorithms,developing fast heuristics for intractable cases of the problem,and analyzing theoretical performance of the heuristics.Finally,we consider an inbound logistics scheduling model where the supply of materials that are necessary for the processing of a given set of jobs are delivered at regular(fixed-interval)points in time.These points in time serve as potential release(ready)dates for the jobs that have to be processed on a single machine.We assume that the idle cost of the involved machine is very large such that once it starts processing a job,it must process the remaining jobs consecutively.Based on this,the problem is to select for each job a release date and schedule all the jobs on the machine without preemption such that the total weighted completion time of all jobs is minimized subject to the constraint that there is no idle time in the schedule.We first show that the problem is NP-hard in the strong sense,and then propose an exact branch-and-price algorithm to solve it.Our computational experiments demonstrate that the proposed branchand-price algorithm can solve the problem within reasonable time.