Authors:
Paper:
https://arxiv.org/abs/2408.10040
Introduction
In the realm of manufacturing, generating an optimal production schedule is paramount. It significantly impacts the efficiency and productivity of operations, influencing both the top and bottom lines, as well as on-time delivery dates. However, creating a high-quality schedule for large, complex operations is notoriously challenging. The advent of large-scale automation, which enables the automatic generation of optimal schedules for extended time horizons, opens new avenues for AI applications. These include promising delivery dates based on a more accurate assessment of future resource availability and tactical capacity planning.
Optimizing Manufacturing Schedule: The Problem
At the end of a regular cycle, schedulers in manufacturing companies face a Demand Set of customer work orders (WOs) that need to be scheduled for production over the upcoming time horizon. Each work order specifies a single product, the required quantity, and the expected delivery date. The production process for each product involves multiple tasks that need to be executed in a specific order, requiring specific machines, tools, raw materials, and personnel. Dependencies between work orders further complicate the scheduling process.
The scheduler’s task is to build a schedule at the task level that optimizes an objective function ( Z ), representing a mix of schedule quality goals such as due-date compliance, makespan, total throughput, raw material consumption, and machine utilization. These goals are often consolidated into a weighted ( Z ) score for overall schedule quality. The schedule is graphically represented by a Gantt board, where each tile represents an assignment specifying the production step for a product, its start and end times, and all required resources.
Requirements and Constraints are the Rules of the Game
Scheduling in manufacturing involves adhering to numerous requirements and constraints, which are the rules of the game. These include:
- Technical Rules: For example, a 60” wide roll cannot be cut on a 40” wide machine.
- Resource Availability: Assignments must be within the working hours of all resources.
- Task Sequencing: Tasks must be performed in a specific order, with some tasks allowing partial completion before the next task starts.
- Batching Rules: Some machines can process multiple parts simultaneously, requiring consistent task grouping.
- Workforce Rules: Multiple people can work jointly on tasks, with productivity assumptions based on the number of people involved.
Large-scale operations involve numerous machines, tools, raw materials, and personnel, each with specific skills and qualifications. This necessitates a comprehensive set of requirements and constraints to ensure valid assignments on the Gantt board. Violating these rules renders the schedule invalid, making adherence to these rules a prerequisite for any commercial scheduling software.
Current Practice Algorithms
Various algorithms have been proposed for automatically generating production schedules for complex manufacturing operations. These include:
- Simulated Annealing
- Tabu Search
- Genetic Algorithms
- Grasshopper Algorithms
Heuristic search algorithms based on principles used by human expert schedulers, such as backward scheduling, forward scheduling, and bottleneck-oriented scheduling, are also common. However, algorithms based on exact mathematical models, like Integer Programming, are less applicable due to their inability to handle the complex requirements and constraints of valid schedules.
Most contemporary algorithms follow a hill-climbing strategy, starting from an empty Gantt board and systematically placing tiles to improve schedule quality. When a local peak is reached, the algorithm makes local changes or removes tiles to find a new starting point, aiming for higher peaks. However, these algorithms often explore only a small part of the possible valid schedules and max out at 500-1,000 tasks in fully automatic mode. Additionally, the resulting schedules may not be intuitive for human logic, complicating adjustments during execution.
The New Practimum-Optimum™ Algorithm: An Overview
The limitations of current algorithms drove the development of the Practimum-Optimum (P-O) algorithm, which offers several unique differentiators:
- Scalability: P-O can automatically schedule tens of thousands of jobs for complex manufacturing environments.
- Broader Exploration: It explores broader areas of the universe of valid Gantt boards and high-quality schedules.
- Self-Generating Dataset: P-O includes a self-generating dataset of schedules for reinforced machine learning.
- Multiple High-Quality Schedules: It generates multiple high-quality schedules with various quality metrics and tile arrangements.
- Human-Oriented Schedules: P-O produces schedules that make business sense to humans.
Factory’s Digital Twins
The P-O algorithm’s software infrastructure is based on a complete digital representation of the manufacturing environment, including digital twins for all physical and abstract objects. This allows for the expression of all requirements and constraints in software structures, capturing the intricate details required for decision-making.
Plataine’s Scheduler includes a configuration module that generates all elements required for a full problem statement of a manufacturing scheduling problem. This module integrates with existing ERP/MES systems, accessing and updating data as needed.
The Practimum-Optimum™ Algorithm: Main Components
Virtual Human Experts
Central to P-O is the concept of Virtual Human Expert (VHE) agents, which operate using heuristics and methodologies that human experts use to build optimal schedules. These methods include forward scheduling, backward scheduling, and shifting bottleneck heuristics. Each VHE represents a different school of thought, allowing for a wide spectrum of scheduling approaches.
A Single Schedule Building Iteration of a VHE Algorithm
Each VHE starts with an iteration of applying its scheduling logic to build a full schedule for the given Demand Set. The resulting valid Gantt board schedule is then analyzed by a reinforced machine learning (RL) algorithm to identify strengths and weaknesses, leading to adjustments in the Demand Set for subsequent iterations.
Schedule Metrics
Each VHE calculates a rich set of macro and micro metrics for each schedule it generates. Macro metrics cover the entire Gantt board, while micro metrics focus on specific assignments or resources. These metrics play a key role in the machine-learning processes.
Reinforced Learning (RL) Algorithm
The RL algorithm analyzes the entire schedule at the end of each iteration, identifying inadequacies and making adjustments to the Demand Set. This process allows the VHE algorithms to explore different parts of the scheduling universe, potentially finding higher-quality schedules.
Flow of the Practimum-Optimum™ Algorithm for Building an Optimal Schedule
The P-O algorithm involves multiple independent VHE agents, each representing a different scheduling heuristic. Each VHE performs multiple iterations, building valid schedules and submitting them to the RL algorithm for analysis and adjustment. The resulting schedules are stored in a repository, and the best schedule is presented to the user.
A Real-Life Case in Fully Automatic Mode
CarbTech, a manufacturer of aerospace parts, illustrates the scale and performance of the P-O algorithm. In one scenario, a Demand Set of 395 work orders over a month (7,505 tasks) was scheduled in 1.5 hours. In another scenario, a Demand Set of 600 work orders over three months (33,548 tasks) was scheduled in 2:45 hours. These results demonstrate the algorithm’s efficiency and scalability.
Discussion on Bio-inspired Colonies versus “Human Expert Colonies”
The P-O algorithm, based on the intelligence of a colony of human experts enhanced by reinforced machine learning, offers a powerful alternative to bio-inspired algorithms. Each VHE algorithm represents years of expertise, and the RL algorithm combines their collective wisdom to overcome individual weaknesses. This approach leverages deep domain knowledge and adapts to unique Demand Sets, providing a robust solution for complex manufacturing scheduling.
Summary
The Practimum-Optimum™ (P-O) algorithm represents a paradigm shift in automatic optimization for complex manufacturing scheduling. By leveraging deep business domain expertise and virtual human expert agents, P-O generates high-quality schedules at unprecedented speeds. The reinforced machine learning algorithm further enhances schedule quality by exploring different parts of the scheduling universe. This breakthrough in scale and performance positions the P-O algorithm as a leading solution for fully automatic manufacturing scheduling in complex organizations.