Scheduling has for decades been a prime process to optimize. Recently at Princeton Consultants, we are seeing an increasing number of highly complex scheduling problems across industries, perhaps because costs are rising and critical resources are becoming more limited. Executives are looking to maximize efficient utilization of their workforce, equipment, vehicles, and other high-value assets.
At many organizations, the legacy scheduling systems consist of interrelated spreadsheets manually managed by different groups. There may be planning exercises to create a master schedule, as well as “operational scheduling” that modifies a planned schedule as the tasks are executed, because tasks may take longer or shorter than anticipated, or resources become unavailable. Other complexities we have encountered include the following:
- The organization is scheduling tasks of different lengths of time over a long time horizon. For example, tasks are scheduled to start on different days, durations are days, and the horizon is at least several months. Another example is where tasks are scheduled to start every 5 minutes, durations are multiples of 5-minute intervals, with scheduling for many hours or days.
- Each task requires resources (people, machines, devices, etc.). The tasks share different resources. At each unit of time (days, 5-minute intervals, etc.), the capacity of each resource is limited.
- Tasks may or may not have precedence constraints.
- There could be different goals. For example, with a given number of resources, and a finite amount of time, how many tasks can be completed? With a given number of resources, and a given number of tasks, what is the shortest possible schedule? With a given number of tasks, and a finite amount of time, how many resources are required to complete the schedule? This is illustrated in the following diagram showing how the 3 aspects of scheduling problems (time, tasks, resources) can each be goals, with the other 2 aspects constrained:
Replacing a spreadsheet-based system with an optimization solution can be very challenging technically—“NP-hard” to an optimizer. The difficulty for traditional Mixed Integer Programming (MIP) formulations arises from several factors:
- Exponential Increase: The complexity of the solution space increases exponentially with the number of tasks and resources.
- Symmetry: Many schedules are equivalent, causing redundancy.
- Degeneracy: Many solutions have the same objective value, complicating the solver's task.
- Weak Linear Programming (LP) Relaxation: The LP relaxation of these problems is generally weak, making it hard for branch and bound methods to effectively improve bounds.
Three Advanced Techniques
One of the strengths of optimization is that it allows flexibility. For complex scheduling applications, we have developed alternatives to MIP modeling to achieve high-quality performance.
1. Schedule Generation
This approach shifts complexity from the solver to a rules engine, generating many feasible schedules for each asset. The schedules are then evaluated to ensure each asset and resource is used optimally. In practice, the schedule generation process involves two phases:
- Generation: For each asset, we generate a set of feasible schedules using a recursive technique and rules-based approach.
- Optimization: Solve a simplified MIP to ensure each asset is used only once and each resource appears in one schedule.
At Princeton we applied schedule generation successfully for a fractional airline that faced issues with inaccurate maintenance data, which affected trip assignments. By creating "strings" of flights that were feasible for a crew, we helped the airline improve scheduling accuracy. The model allowed for altering flight start times to optimize schedules, and additional capacity for subcontracted flights was integrated to handle aircraft availability issues. This solution involved creating fake "tails" for flights and adding slack costs to manage capacity effectively.
For a bulk chemical trucking carrier, we developed a scheduling solution for active orders, tankers, and drivers over a rolling horizon. The solution process involved generating trailer routes, solving combined trailer-driver models, and optimizing tank wash options. This approach resulted in a highly efficient scheduling system that was a finalist for the INFORMS Daniel H. Wagner Prize for Excellence. (See https://pubsonline.informs.org/doi/10.1287/inte.2018.0956.)
2. Reciprocating Integer Programming (RIP)
This technique addresses problems by generating patterns as needed using a "price-and-branch" approach. RIP involves solving a master problem with all possible patterns, generating patterns as needed, and addressing the problem via column generation techniques. The RIP process uses dual values from the master problem to generate new patterns, ensuring high-quality solutions. We created RIP to solve subscription box configuration for Birchbox, the trailblazing e-commerce company, and the solution was also a finalist for the INFORMS Daniel H. Wagner Prize for Excellence. (See https://pubsonline.informs.org/doi/10.1287/inte.2021.1081.)
We believed the RIP approach could work well for scheduling problems, and accessed a test bank of healthcare clinic problems. We applied RIP to two nurse scheduling problem sets and generated new best solutions, indicating great promise.
3. Constraint Programming (CP)
Originating from AI research in the 1960’s, CP uses a more expressive language to define constraints and specialized algorithms to find good (though not necessarily provably optimal) solutions quickly. CP is particularly effective for scheduling problems with weak linear relaxations, because it avoids the pitfalls of poor lower bounds.
Using CP, we built a custom scheduling solution for a healthcare provider with more than 3,000 clinics, helping optimally schedule patients and staff in advance. For another client that required annually scheduling 1300 tasks that covered a year’s worth of activities, with limited resources, we used CP to compute schedules that ensured all the tasks could be completed within the year.
Is Optimality Always Necessary?
The short answer is no. While traditional methods aim for provably optimal solutions, practical constraints often necessitate a balance between solution quality and computational efficiency. Schedule Generation, RIP and CP provide high-quality solutions within reasonable timeframes and deliver significant value. By leveraging these advanced methodologies to develop custom solutions, executives can transform scheduling processes, improve operational efficiency, and achieve significant savings.
If you’d like to discuss complex scheduling with Rob and Irv, email us to set up a call.