Abstract
Recurring assignment problems, such as workforce scheduling or software test distribution, often suffer from a lack of diversity over time. This paper introduces a framework for "rotational diversity" that ensures tasks are distributed across all compatible agents across multiple cycles. By balancing profit maximization with a novel "Affinity Pressure" metric, the proposed approach achieves high rotation with less than 4% profit loss in industrial applications.
Introduction
Standard assignment problems, like the General Assignment Problem (GAP), are typically treated as single-instance optimizations where $n$ tasks are assigned to $m$ agents to maximize total profit. However, in many real-world scenarios—including workforce scheduling, aircraft maintenance, and software testing—these problems are solved repeatedly in cycles.
A critical challenge in these multi-cycle environments is "rotational diversity": avoiding the repetitive assignment of the same task to the same agent. Rotation is essential to prevent employee burnout, ensure even machinery wear, and increase coverage in testing. Furthermore, these systems must handle dynamic availability, where agents or machines may become unavailable unexpectedly.
Methodology
The researchers propose a two-tier architecture to manage the trade-off between immediate profit and long-term rotation.
Two-Tier Architecture
- The Inner Problem: A standard GAP model that maximizes a "value" function subject to agent capacity constraints. This is solved using standard optimization tools like MiniZinc and CPLEX.
- The Outer Problem: This layer manages the temporal aspect. It tracks Affinity, which measures the time elapsed since a specific task-agent assignment was last made. To quantify system health, the authors define Affinity Pressure (AP), which compares current assignments to an ideal rotation.
Strategies for Value Calculation
The framework combines profit ($p$) and affinity ($a$) into a single value ($v$) for the inner solver using several strategies, including Objective Switch (OS), which flips priorities based on AP thresholds, and Product Combination (PC), which multiplies profit and affinity ($v = p \times a$) to naturally boost overdue assignments.
Experimental Evaluation
The approach was evaluated on two datasets:
- MCMKP (Multi-Cycle Multiple Knapsack Problem): A synthetic dataset used to test varying levels of task and agent availability (75% vs 100%).
- TCSA (Test Case Selection and Assignment): A real-world industrial dataset involving software testing for robotic systems, featuring 750 to 3,000 test cases and 20–30 machines with actual downtime data.
Results and Discussion
The evaluation focused on the balance between efficiency (profit) and rotational diversity.
In the TCSA case study, the Product Combination (PC) strategy emerged as a top performer. It achieved high rotational diversity while sacrificing less than 4% of the profit compared to a profit-only baseline (FOP). In smaller scenarios, the system achieved full rotations every 23–26 days.
A key insight is the distinction between temporal and solution diversity. While most research seeks multiple solutions to one instance, this work ensures solutions differ across cycles. The model is also "temporally greedy," requiring no knowledge of the future to handle unpredictable agent availability gracefully.
Conclusion
While the proposed framework effectively manages rotational diversity, some limitations remain. The inner GAP problem is NP-hard, which may necessitate heuristic solvers for extremely large-scale applications. Additionally, future work should address task dependencies (precedence constraints) and explore dynamic profit models where assignment values change based on an agent's recent history.
Summary updated