Automated planning tools are programs that combine artificial intelligence and designed algorithms to plan and schedule tasks, resources, and activities. They are used in a variety of industries, including manufacturing, supply chain management, healthcare, and transportation, where they can help improve efficiency and reduce costs by automating repetitive and time-consuming planning tasks.
Work order allocation is a critical task in many of these industries; it is a type of resource allocation problem, where the goal is to schedule a set of work orders on a set of resources (machines, personnel, etc.) in an efficient and effective manner. It involves allocating resources, such as labor, equipment, and materials, to specific tasks in a way that meets various constraints and objectives.
At the 2022 meeting of the Association of European Operational Research Societies (EURO), I presented a paper titled “Automated Planning Tool (APT): A mixed integer non-linear programming problem solver for workorder scheduling”, which describes a new approach to solving work-order-allocation problems.
My method, called the Automated Planning Tool (APT), uses a mixed-integer nonlinear-programming (MINLP) solver to handle the complex and nonlinear nature of work-order-allocation problems. MINLP is an optimization technique that combines variables constrained to integer values with continuous nonlinear functions.
The APT algorithm is based on the branch-and-bound method, which divides an optimization problem into smaller subproblems and then uses a bounding function to estimate the solution for each subproblem. The bounding function provides an upper or lower bound on the optimal solution, which can be used to prune the search space by eliminating subproblems that are known not to contain the optimal solution.
Because it involves a large number of constraints (such as task dependencies, deadlines, and resource constraints), work order allocation is an NP-complete problem, meaning that for even a reasonable numbers of variables, it can become impractically time consuming. It becomes even more complex and challenging when it involves nonlinear constraints, such as resource utilization and maintenance costs.
Automated planning tools must thus find approximate solutions to optimization problems or exploit problem structure in order to reduce the computational complexity. Some techniques used in automated planning tools include
- PERT (program evaluation and review technique)
- critical-path method (CPM) for Gantt charts
- linear programming (LP)
- integer programming (IP)
- constraint programming (CP)
- artificial-intelligence planning (AIP).
However, traditional optimization techniques, such as linear programming, are not very well suited to solving these types of problems.
Complexity
APT’s complexity is closely tied to the constraints that must be taken into account when creating a schedule. These might include the time window within which a task must be completed, the availability and qualifications of technicians, or the physical layout of a facility.
Such constraints can make the problem more difficult to solve, as they may limit the number of possible solutions or make it harder to find an optimal schedule. The complexity of the problem also depends on the number of work orders, the number of resources available, and the need to satisfy the integrality constraint for binary decision variables. It's important to consider these constraints both while formulating the problem as an MINLP problem and while designing the optimization algorithm to solve the problem.
APT
In the case of APT, the algorithm is implemented as a tree search, where the root node represents the original problem, and the children of each node represent the subproblems generated by branching. The search continues until all nodes have been explored or a feasible solution has been found.
We have used the Xpress solver to solve this problem with multiple constraints and a mix of integer/continuous decision variables. Our studies show that APT is able to find optimal solutions for work-order-allocation problems with nonlinear objective functions in a relatively short amount of time.
AWS-powered implementation
APT is written using Python and uses Amazon Web Services (AWS) infrastructure for data storage as well as computation. AWS’s ECS Fargate allowed us to scale APT in an affordable way with no upper cap on the number of users. ECS Fargate is a technology provided by AWS for running Docker containers on the AWS Elastic Container Service (ECS) without the need for managing the underlying infrastructure. Fargate eliminates the need for users to provision and manage the EC2 instances that their containers run on, allowing them to focus on developing and deploying their applications. It also enables automatic scaling of containerized applications and integrates with other AWS services, such as load balancers and security groups.
The Automated Planning Tool (APT) is a powerful and efficient method for solving work-order-allocation problems. Its ability to handle nonlinear objectives and its use of a branch-and-bound method make it a valuable tool for scheduling and resource allocation.
