Abstract
Scheduling problems are often tackled independently, and rarely solved by leveraging the commonalities across problems. Lack of awareness of this inter-task similarity could impede the search efficacy. A quantifiable relationship between scheduling problems is to-date rather unclear, how to leverage it in combinatorial optimization remains largely unknown, and its effects on search are also undeterminable. This paper addresses these hard questions by delving into quantifiable useful inter-task relationships and, through leveraging the explicit relationship, presenting a speed-up algorithm. After deriving an analytical inter-task distance metric to quantitatively reveal latent similarity across scheduling problems, an adaptive transfer of multi-modality knowledge is devised to promptly adjust the transfer in forms of explicit and implicit knowledge in response to heterogeneity in the inter-task discrepancy. For faintly related problems with disappearing dependences, a problem transformation function is suggested with a matching-feature-based greedy policy, and the function projects faintly related problems into a latent space where these problems gain similarity in a way that creates search speed-ups. Finally, a multi-task scatter search combinatorial algorithm is formed and a large-scale multi-task benchmark is generated serving the purposes of validation. That the algorithm exhibits dramatic speed-ups of 2~3 orders of magnitude, as compared to direct problem solving in strongly related problems and 3 times faster in weakly related ones, suggests leveraging commonality across problems could be successful.
The Challenge of the "Sisyphean Dilemma"
In combinatorial optimization, particularly in scheduling, algorithms often treat every new task as a "blank slate." Even when a new problem is nearly identical to a previously solved instance, standard meta-heuristics like Scatter Search or Genetic Algorithms typically restart from scratch. This lack of awareness regarding inter-task commonalities leads to a "Sisyphean dilemma," where massive computational effort is wasted on redundant search processes.
The primary obstacle to overcoming this dilemma is the difficulty of measuring similarity between NP-hard problem landscapes. Due to the "curse of dimensionality," quantifying how "far apart" two tasks are is non-trivial. Without a reliable distance metric, attempting to transfer knowledge between tasks is often a blind endeavor that can lead to "search stagnation" or negative transfer, where the search process is actually hindered rather than helped.
Methodology: Quantifying and Leveraging Similarity
The proposed Multi-task Combinatorial Optimization (MTCO) framework addresses these challenges through a three-pillared approach designed to identify and exploit latent similarities between tasks.
1. Analytical Inter-task Distance Metric
By identifying "scale-invariance" and "shift-invariance" within Permutation Flowshop Scheduling Problems (PFSP), the authors derived a symmetrical, normalized distance metric (ranging from 0 to 1). This is formulated as a convex quadratic programming problem with an efficient analytical solution, allowing similarity to be calculated with minimal computational overhead ($O(m \cdot n)$ complexity).
2. Adaptive Multi-modality Knowledge Transfer
Rather than simply sharing the final best solution, the algorithm adaptively transfers three distinct modalities of knowledge based on the calculated distance:
- Complete Solutions: Direct reuse of high-quality results.
- Partial Solutions: Identification of "invariant" job sequences that remain consistent across tasks.
- Solution Evolution: A novel approach that transfers the process of improvement—the sequence of transformations that led to better results—rather than just the static outcome.
3. Problem Transformation in Latent Space
For tasks that appear unrelated (high inter-task distance), the framework employs a greedy matching-feature policy to project them into a joint latent space. This transformation "aligns" the problems, artificially increasing their similarity to make knowledge transfer viable and effective.
Benchmarking and Validation
To validate the framework, the authors utilized two primary datasets:
- Taillard’s Benchmark: A standard set of PFSP instances, though the authors noted that random pairings in this set often result in unrelated tasks (distance $\approx$ 1.0).
- New Multi-task Benchmark: A massive new test bed of 12,000 instances was generated using a "probabilistic element replacement method." This allows for systematic testing across a full spectrum of distances, from identical (0) to completely unrelated (1).
Key Results and Insights
The MTCO algorithm demonstrated significant performance gains across various scenarios:
- Massive Speedups: For strongly related problems, the algorithm achieved speedups of 2 to 3 orders of magnitude compared to Single-task Scatter Search (STSS).
- Robustness: Even in weakly related scenarios, the algorithm remained roughly 3 times faster than independent solving.
- Metric Reliability: The proposed distance metric showed a 0.94 correlation with the Spearman’s Rank Correlation Coefficient, proving its accuracy as a similarity measure.
- Predictive Power: The study proved that if the inter-task distance is $< 0.1$, there is a very high probability that the optimal solution for one task will rank in the top 10 for the other.
Conclusion and Future Directions
This research demonstrates that the "process is the knowledge." By treating the evolution of a solution as a transferable piece of intelligence and using an explicit distance metric as a "safety valve" to prevent negative transfer, MTCO significantly improves search efficacy.
Future work will focus on extending the distance metric to other combinatorial structures beyond permutation-based problems, such as graphs or sets. Additionally, the authors suggest integrating "Boolean learning" with Fourier approximations to build a library of prior problem structures, further accelerating the search for entirely new, unseen tasks.
Summary updated