Optimization methods for scheduling in industrial applications

Scheduling optimization has always been a challenging topic in different industries especially over a long planning horizon. Decisions with a consideration of various operational factors subject to limited resources often need to be made to reduce overall costs, maximize utilization and balance resources. To this end, many researchers have developed various models and solution methodologies for deterministic scheduling problems with a consideration of a set of limited resources. As the scheduling system in different industries becomes more complex and sophisticated, additional resources should be incorporated and contradictory goals need to be more carefully evaluated to create a more practical and flexible plan. A robust plan that deals with uncertainties in scheduling has also received a lot of attention in recent years in case of unanticipated events. What’s more, extra information or requests can arise and should also be taken into account during the planning horizon, therefore a more dynamic method is preferred to update the scheduling plan, especially in multi-period problems. This work focuses on scheduling optimization problems in three different industries with a consideration of extra resources, more operational goals or uncertainties in a more dynamic environment. We also proposed multi-step methods or preprocessing procedures to solve the industrial-sized problems efficiently and obtain exact or near-optimal solutions. Chapter 1 presents an overall introduction to this dissertation and its chapters, along with the organization of it. Chapter 2 introduces a two-stage approach for minimizing the impact of daily disruptions on an airline’s published flight schedule. The problem is characterized by uncertainty in the duration of the disruption and the point in time when its length becomes known. Both a single-commodity network model and multi-commodity network model with side constraints are developed to first determine the flights that are most likely to be affected, and then to adjust their schedules to achieve system-wide optimality. The overall objective is to minimize the weighted sum of total passenger delay costs, cancellation costs, curfew violation costs, and variation from the original schedule. The two types of uncertainty are addressed by examining a range of scenarios that reflect the most likely outcomes. The results provide guidance and a measure of robustness for the flight director as the disruption unfolds. A rolling horizon approach that closely mimics current procedures used by several airlines is also presented to provide a benchmark for comparisons with the two-stage solutions. In Chapter 3, a discrete-time mixed-integer linear programming (MILP) model for a generalized flexible job-shop scheduling problem as represented by a state-task network in batch processing facilities in presented. The problem is characterized by reentrant flow, sequence-dependent changeover time, machine downtime, and skilled labor requirements. Two preprocessing procedures are proposed to reduce the size of the MILP model, and represent a major contribution of the research. The procedures reduce the number of assignment variables by exploiting job precedence and workforce qualifications. Machine availability for each task is determined as a function of possible start and end times, given duration, and maintenance schedule. The overall objective is to maximize the number of scheduled tasks while minimizing their total finish time. Computational experiments are conducted with real and randomly generated instances. The results show that optimal solutions can be obtained for medium-size problems within a reasonable amount of time, primarily due to the use of the preprocessing procedures. Chapter 4 presents a two-step approach for efficiently solving a weekly home health-care scheduling and routing problem. Two new mixed-integer programming (MIP) models are proposed, where the is first used for making patient-therapist assignments over the week, and the second for deriving daily routes. In both MIPs, the objective function contains a hierarchically weighted set of goals. The major components of the full problem are continuity of care, downgrading, workload balance, time windows, overtime, and mileage costs. A new preprocessing procedure is developed to limit the service area of each therapist to a single group of overlapping patients. Once the groups are formed, weekly schedules are constructed with the MIPs. The overall objective is to minimize the number of unscheduled visits and total travel and service costs subject to the operational and physical constraints mentioned above. Computational experiments are conducted with real data sets provided by a national home health agency. The results show that optimal solutions can be obtained quickly for large-size instances, and that they compare favorably with results obtained with a proposed integrated model as well as the actual schedules. Lastly, Chapter 5 concludes the dissertation by summarizing research contributions, key research findings, and indicating future research directions.