TL;DR
This paper tackles the challenge of scheduling business process instances when resources have fluctuating availability, a common real-world scenario often overlooked by existing methods. They propose and evaluate three heuristic-based strategies (DM, BL, BG) and a genetic algorithm (GA) to maximize the number of successfully scheduled instances, considering resource availability, task dependencies, and deadlines. The GA approach demonstrates near-optimal results, while BG offers a good balance of efficiency and accuracy for dynamic scheduling, and DM proves practical in resource-scarce environments.
What Problem Does This Paper Address?
In enterprise resource management, efficiently scheduling tasks within business processes is crucial. However, many existing approaches focus on optimizing resource utilization without accounting for the fact that resources (like machines or staff) aren't always available due to factors like work shifts or maintenance. This paper addresses the gap of scheduling business process instances when resource availability is dynamic and follows specific patterns. The challenge lies in finding a scheduling strategy that can effectively balance resource availability constraints, task dependencies, and instance deadlines to maximize the number of successfully completed processes, especially when dealing with a large number of instances and limited resources.
Methods
The authors propose four strategies for scheduling business process instances under resource availability constraints:
- DM (Depth-First/Min Gap): A greedy approach that prioritizes instances with the smallest time gap between their optimistic completion time and deadline. It operates in a depth-first manner, scheduling one instance at a time and adjusting other allocations to maintain conflict-free resource usage.
- BL (Breadth-First/Dynamic Local Optimisation): A holistic approach that considers all instances but uses local optimization rules to select the most urgent task for allocation. It aims for a more balanced scheduling of instances.
- BG (Breadth-First/Dynamic Global Optimisation): Another holistic approach that prioritizes tasks based on a global penalty metric, considering the impact on all instances. This strategy aims for a more balanced global optimization.
- GA (Genetic Algorithm): A metaheuristic approach that uses evolutionary principles (selection, crossover, mutation) to find near-optimal solutions. It leverages the DM, BL, and BG strategies to generate an initial population, aiming to overcome the limitations of purely heuristic methods.
Datasets
The paper does not explicitly mention using pre-existing datasets for training or evaluation. Instead, they generated synthetic test cases for their experiments. These synthetic scenarios were created based on parameters defined in Table III, which include the number of process instances, tasks per instance, resources, time slots per resource, and the time required for a task by a resource. They also generated 30 synthetic test cases with known optimal assignments for comparison.
Key Insights and Ideas
- Resource availability is a critical, often overlooked, constraint: The paper strongly emphasizes that ignoring dynamic resource availability leads to suboptimal scheduling and potential failures, especially in real-world enterprise scenarios.
- Heuristics offer efficiency, but with trade-offs: The DM, BL, and BG strategies provide efficient scheduling solutions, but their performance varies depending on resource availability and the nature of the problem (local vs. global optimization).
- GA for near-optimality: The Genetic Algorithm approach demonstrates superior accuracy, achieving near-optimal results, but at the cost of significantly higher computational time, making it suitable for build-time planning rather than real-time applications.
- BG for balanced scheduling: The BG strategy, with its global optimization focus, performs well when resources are abundant and instances tend to succeed or fail together.
- DM for resource scarcity: The DM strategy, despite its local optimization, proves practical and effective when resources are scarce, as it prioritizes saving at-risk instances.
- Adjustment plays a crucial role: Allocation adjustment mechanisms significantly improve the success rate, particularly for DM and BL, by rescuing instances that might otherwise be unscheduled.
Key Results
- Accuracy: The GA-based algorithm consistently achieved the best accuracy, scheduling all instances when the number of instances was below 600 (with Nresource = 300).
- Heuristic Performance: Among the heuristics, BG generally performed best in terms of success rate when resources were sufficient. DM was the most efficient but had the worst performance. BL and BG showed stable performance when Ninstance reached 600.
- Resource Scarcity: The GA maintained robust performance across varying resource scarcity levels. BG performed well with abundant resources but struggled when scarcity increased. DM outperformed BL and BG when resource scarcity was high.
- Efficiency: DM was the most efficient heuristic strategy. GA was significantly more time-consuming, requiring several minutes. BG was more costly than DM and BL due to its global optimization nature.
- Adjustment Impact: Allocation adjustment increased the success rate by 10%-30% in usual cases, with a more significant impact on DM and BL.
Limitations and Future Work
- Simplified Resource Model: The authors acknowledge using a simplified resource model and suggest that considering conflict-of-interest constraints would require modifications to their operations.
- Inter-play of Constraints: Future work includes exploring the interplay between resource-level constraints and process-instance-level constraints, such as inter-task temporal constraints.
- More Optimization Criteria: The authors plan to explore more optimization criteria to better capture the impact of workflow structure on individual instances.
- Build-time vs. Run-time: The GA strategy is deemed suitable for build-time applications due to its computational cost, while BG is recommended for run-time scheduling where efficiency is key. The paper suggests that for very limited resources, BL might outperform BG in both efficiency and accuracy.
Summary updated