TL;DR
This paper tackles the complex problem of scheduling preventive maintenance (PM) tasks in industrial settings by framing it as a multi-objective optimization problem. Instead of relying on traditional dominance-based Pareto search, the authors introduce a novel approach using evolutionary algorithms guided by user preferences, allowing for more targeted and manager-aligned optimal schedules.
What Problem Does This Paper Address?
Heavy industry maintenance facilities, such as those in aircraft service centers or railroad yards, face a critical challenge in scheduling preventive maintenance (PM) tasks. The core dilemma lies in balancing two conflicting objectives: minimizing worker idle time (which suggests a smaller workforce) and minimizing the overall completion time for all PM tasks (which suggests a larger workforce). A small workforce leads to high idle costs, while a large workforce can be inefficient if tasks are not completed quickly. The PM scheduling problem is NP-hard, making it difficult to find a schedule that optimally balances these objectives. Existing approaches often reduce this to a single objective problem using weighted sums, which requires difficult-to-determine weights, or use dominance-based Pareto searches that treat all non-dominated solutions equally, which may not align with a manager's specific needs.
Methods
The authors propose an evolutionary algorithm (EA) approach to solve this multi-objective PM scheduling problem. The key innovation is the use of preference-based search instead of traditional dominance-based Pareto search.
- Preference-Based Search: This method incorporates user preferences to guide the EA. Instead of simply identifying solutions that are not dominated by others, the algorithm uses pairwise comparisons and linear programming to determine which solutions are preferred by a decision-maker. This allows the EA to target specific subsets of the Pareto front that are more aligned with managerial expectations.
- Incompletely Specified Multiple Attribute Utility Theory (ISMAUT): This theoretical framework is used to handle the imprecise nature of user preferences. It avoids the need for precise weight assignments by using attribute value functions and constraints derived from pairwise comparisons.
- Evolutionary Algorithm Design: The EA employs standard components like random population generation, genetic operators (insertion and inversion for task scheduling), and tournament selection. A key aspect is the representation of solutions, which includes not only the task order but also the number of workers of different skill types. Strategy parameters (like $\sigma$) are adapted during the search to improve exploration.
Datasets
Not discussed in the paper. The authors describe experimental setups using randomly generated PM tasks and worker requirements.
Key Insights and Ideas
- Preferences over Dominance: The core insight is that for practical decision-making, user preferences are often more valuable than simply identifying all non-dominated solutions. A manager might prefer a slightly longer makespan if it significantly reduces the workforce, or vice-versa, and this method allows for that.
- Targeted Pareto Front Exploration: By using preferences, the EA can be directed to explore specific regions of the Pareto front, leading to solutions that are more likely to be accepted by decision-makers, rather than a broad, undifferentiated set of optimal solutions.
- Ranking Initial Solutions Influences Search: The paper highlights that even ranking a small subset of initial individuals can significantly alter the search dynamics and direct the EA towards different regions of the solution space, demonstrating the power of preference-based guidance.
- Trade-off Between Computation and Solution Quality: Preference-based searches, while potentially more computationally intensive due to linear programming steps, can yield solutions that are superior from a decision-maker's perspective, even with similar computation time.
Key Results
- The preference-based searches successfully targeted specific subsets of the Pareto front, as opposed to the dominance-based search which produced a broader front.
- When comparing search strategies with similar computation times, the preference-based searches (both MS-preferred and WN-preferred) yielded solutions that outperformed the dominance-based search from the decision-maker's point of view.
- The MS-preferred search, which favors shorter makespans, was found to be more computationally expensive, partly because calculating makespan for solutions with more workers is inherently more complex.
Limitations and Future Work
- Conflicting Constraints: The preference-based search relies on ranking a small subset of initial individuals, which in large, complex problems might inadvertently lead to conflicting constraints for the LP solver, preventing a valid solution. Future work should focus on developing methods to efficiently detect and handle such conflicting constraints.
- Task Start Policy: The current model assumes a task cannot start until all necessary workers are assigned. Future work will explore a more flexible policy where tasks can start with at least one worker, and additional workers can be assigned during progress, potentially reducing task duration.
- Incorporating Task Priorities: The paper suggests incorporating PM task priorities, allowing for some "slippage" in completion times. This will require modifications to the reproduction operators.
Summary updated