Recursos

Whitepaper

Using a constraint solver to automate planning and scheduling

EXECUTIVE SUMMARY 

All businesses work with a constrained set of resources. The employees, assets, time, and money available to provide products and services are valuable—and limited. As businesses grow, the ability to quickly solve resource scheduling challenges becomes vital for success and future growth. However, as a business gains resources, scheduling complexity often grows to the extent where human processes for optimization cannot keep up. 

That is where automated constraint solving can help. Constraint solvers are automated, algorithmic systems that help businesses rapidly optimize resource utilization. Constraint solvers allow software programmers to work in his or her preferred programming language to solve optimization problems. By applying known constraints and choosing from a variety of sophisticated optimization heuristics and metaheuristics, these tools tackle problems that are beyond human calculation with precision and speed. With automated constraint solving, businesses can rapidly solve problems related to: 

  • Employee rostering for enhanced employee satisfaction. 
  • Vehicle routing for expedited service and lower environmental impact. 
  • Task assignment for fair and balanced scheduling. 
  • Experimental modeling to drive innovation into your business. 

THE UNIVERSAL CHALLENGES OF PLANNING 

Business planning—whether for resources, time, staff, or abstract ideas—is incredibly complex. There are many models and processes that use algorithms to attempt to solve planning problems. Planning can help alleviate the pressure on staff, reduce costs, refine better processes, and make employees and customers happier. 

THE TRAVELING SALESMAN: A CLASSIC PLANNING PROBLEM

 Classic problems, like that of the traveling salesman, provide an illustrative platform that data scientists use to improve the efficiency and outcome of actual business challenges. The traveling salesman problem seeks to find the most efficient route a person can take while traveling between any given number of cities. The result should produce the shortest distance, while ensuring that the traveler does not visit any city more than once and that they end in the origin city.

There is no known solution for this problem in which possible combinations do not grow exponentially with each additional city, yet the scenario is familiar to many different businesses. Companies that provide courier services, field repairs, or in-home medical care deal with these types of routing scenarios daily. Individuals in charge of planning understand the complexity of this type of problem as the number of stops increases. 

THE ADDED COMPLEXITY OF CONSTRAINT SOLVING 

In the traveling salesman example, you typically factor for one resource—a salesman—and several destination cities. These constraints are simplistic, and yet they result in highly complex data sets. Once you add more factors, like adding people to the route scheduling, assessing the skills of each employee, dealing with a truck breaking down, or a customer canceling, you complicate the situation further. 

With each added constraint, your planning complexity skyrockets, as does the cost of your analysis—if you are gathering results by hand. To find the most efficient solution in a constraint-solving scenario, you must quickly cycle through scenarios until you achieve your desired results. 

TRANSCEND HUMAN CAPABILITIES

With any increase in your business resources, many factors result in massive permutations that are beyond human calculations. Even with moderately large data sets, your constraint planning exercises can stress conventional computer-based algorithms. Constraint solvers are different. They use advanced heuristics and metaheuristics, including tabu search, simulated annealing, and late acceptance to accelerate how quickly you get results. 

The algorithms available through a constraint solver are customizable and helps software developers and business owners solve problems in minutes or hours instead of weeks or months with conventional algorithms. 

FIGURING FAIR AND EQUITABLE SOLUTIONS 

If you have a handful of employees, determining a fair schedule is straightforward. However, large companies such as fulfillment warehouses or call centers employ thousands of people with varying skill sets. Determining who should work when, where, and for how long presents a significant challenge. A constraint solver provides powerful problem-solving tools that consider time, resources, and business rules to determine best-case scenarios for achieving business goals. 

HITTING A MOVING TARGET 

Very rarely are business planning problems static. Resource counts change—sometimes on the fly—and your carefully considered schedule, route, or plan suddenly has gaps that need to be filled. 

Constraint solvers allow you to find an optimal solution to your challenges more quickly, even when the conditions change. With the unique ability to manage and modify conditions before, during, and after processing, you will be able to rapidly adjust and remain agile with negligible changes in system performance. Since these solutions are typically embedded and customized, adapting to new constraints is as easy as changing your input data.
 

CONSTRAINT SOLVING FOR EMPLOYEE SHIFT ROSTERS 

Employees are happier when scheduling is fair and equitable. However, as your team grows, ensuring a balanced schedule with traditional planning methods can be increasingly difficult. Additionally, you must consider constraints such as skill requirements (e.g., languages spoken, specializations), the number of hours employees can work in a day, and the total number of employees needed for each shift. You will also need to keep in mind requested days off and desired time slots or locations. 

Traditionally, shift rostering is delegated to management teams who are responsible for sets of people. Each of those managers then spends time and energy planning shifts and working up schedules by hand or using traditional algorithm-based tools. If employees call in sick or leave the job, a manager must go back and revisit that schedule to ensure proper coverage. This shift rostering method takes away from each manager’s potential to perform more important tasks. 

BUSINESSES THAT BENEFIT FROM AUTOMATED SHIFT ROSTERING

  • Hospitals
  • Assembly lines
  • Call centers
  • Police and fire departments
  • Distribution and fulfillment centers

 

TABLE 1. OPTAPLANNER BENCHMARK: NURSE ROSTERING

A nurse rostering benchmark, run on the OptaPlanner constraint solver, demonstrates how a planning engine can optimize a shift roster for a sizeable data set in minutes. 

During this benchmark, employees were defined as proficient in zero to many skills, and only those employees who were eligible for shifts were considered in the results. Shifts were defined as having a starting date and time, ending date and time, and an assigned unit. Each unit could require a certain skill set for an employee to qualify for assignment. 

 

GOAL CONSTRAINTS CONSTRAINTS

Assign employees to shifts in a manner that is fair and equitable. 

 

Hard: 

• Employees can be assigned to, at most, one shift per day

• Skill requirements

Soft: 

• Employees must have a break of at least 10 hours between shifts

• Employees may have day-off requests

 

• 26 data sets 

• 752 assignments 

• 50 employees

RESULTS 
Using the tabu search, OptaPlanner was able to optimize the nurse rostering schedule in five minutes with a 53 percent average increase in employee well-being. Additionally, once the schedule was complete, the addition or removal of variables from the model (e.g., a nurse taking a sick day) produced a result in seconds that ensures minimal impact on the overall schedule.

Download the benchmark code

RAPID OPTIMIZATION OF VEHICLE ROUTING 

Vehicle routing applies to the traditional traveling salesman problem. From local delivery services to global freight carriers, the ability to optimize vehicle routing results in lower fuel costs, reduced environmental impact, increased customer satisfaction, and happier drivers and operators. Because these businesses are highly complex, planning vehicle routing can come with a long list of constraints, including time windows, employee skills, job locations, and employee location. 

A constraint solver can produce an optimized vehicle routing plan in seconds or minutes. With flexible, adaptable designs, you can easily change your input constraints or goals to test scenarios and find the best routes for your business. Whether you need to deliver during time windows, optimize fuel use, or schedule as many deliveries as possible each day, your constraint solver can help you ensure driver success and customer satisfaction.

BUSINESSES THAT BENEFIT FROM OPTIMIZED VEHICLE ROUTING 

  • Shipping companies
  • Courier services 
  • Package and mail delivery 
  • Car sharing and taxi services
  • Public transportation 

 

TABLE 2. OPTAPLANNER SIMULATION: VEHICLE ROUTING WITH TIME WINDOWS

For the vehicle routing examples, vehicles are required to deliver packages to customers within time windows. Customers are expecting their packages during their assigned time window with no leniency for late or early arrivals.

GOAL CONSTRAINTS DATA SETS

• Deliver packages from the warehouse to customers within predefined time windows 

• Schedule as many jobs in a single day as possible

• Optimize for time and fuel usage.

• Each customer needs a specific number of items delivered 

• Each vehicle must be able to carry all items for any given stop on its route

• Every customer has a time window during which the vehicle can arrive 

• Travel time between points

• Service time during each stop 

Varying scenarios from 10 to 400 stops

RESULTS 

OptaPlanner was employed to test various data sets and find a variety of routing solutions based on shifting goals and constraints. By varying delivery windows, OptaPlanner was able to provide substantial fuel savings while adhering to all time constraints.

Watch the simulation

RED HAT BUSINESS OPTIMIZER: CONSTRAINT SOLVING FOR THE ENTERPRISE 

Using Red Hat® Business Optimizer is like having a team of mathematicians, data scientists, and analytics experts on your team. Yet, all you need are the Java™ developers you already have on staff. Using this lightweight, embeddable, open source planning engine, your Java programmers can solve optimization problems easily and efficiently using a variety of out-of-the-box-provided algorithms, and your team can experiment and choose the right algorithm to achieve optimal results. 

SUPPORTED AND ENTERPRISE-READY

Red Hat Business Optimizer is a fully supported, enterprise-ready business constraint solver. Using the open source OptaPlanner project, Business Optimizer is a validated solution, delivering the best of OptaPlanner’s functionality along with Red Hat support.

SCALABLE AND COMPATIBLE 

Because Business Optimizer is written in pure Java, it runs on Linux®, Mac, and Windows platform Java virtual machine (JVM). Additionally, the engine is compatible with enterprise Java applications like Red Hat JBoss® Enterprise Application Platform (EAP) and with JVM languages such as Kotlin and Scala. You can embed Business Optimizer into your existing codebase to enhance your in-house planning solutions, or you can start from scratch. You can also run your solution on-premise or on any cloud with Red Hat OpenShift®. Wherever you use Business Optimizer, you can scale your planning tools to meet your growing needs. 

OPTIMIZED AND FLEXIBLE 

To solve your unique business problems, you need a tool that can adapt to your exact data sets, criteria, and constraints. Red Hat Business Optimizer provides you with the foundation to:

MODEL YOUR CODE APPLY CONSTRAINTS VARY YOUR SCORING

• Reuse your existing classes 

• Use object-oriented class hierarchies, including polymorphism

• Any constraint can be applied, without linear or quadratic restrictions

• Reuse your existing code 

• Positive/negative

LEARN MORE 

Request a discovery session with Red Hat, and we will show you how to accelerate business decision making with Red Hat Business Optimizer. 

RESOURCES 

For more information, and to run OptaPlanner benchmarks yourself, visit https://www.optaplanner.org/code/benchmarks.html