Nowadays, application providers often prefer to execute their workflows on heterogeneous distributed computing resources deployed on cloud infrastructure to achieve a high level of resilience and cost saving. Optimally scheduling workflow on computing resources is a well-known combinatorial optimization problem, where a trend of using evolutionary algorithm (EA) is emerging rapidly. However, conventional EA optimizes only one problem in a single run and suffers from a high computational burden. In practical scenario, cloud platform needs to handle massive amounts of scheduling requests from users, scheduling different workflows simultaneously is highly challenging. Bearing this in mind, we put forward a novel knowledge transfer enabled EA to schedule diverse workflows in tandem, where domain knowledge of scheduling one workflow is extracted to enhance the scheduling efficiency of other related workflows. In our design, the knowledge source selection and the intensity of performing knowledge transfer are adapted in a synergistic way. Furthermore, search operator is enhanced by exploiting both historical experience and heuristic information. Experimental results on real-life workflows and extensive synthetic applications demonstrate the competitiveness of our approach, in comparison to state-of-the-art contenders. Note to Practitioners—Workflow scheduling is an important requirement for users in cloud computing, whose intractability increases exponentially when the size of problem grows, posing stiff challenges to heuristic methods. Using EAs to tackle workflow scheduling has received increasing attention recently. Suppose workflow scheduling is treated as a optimization task, cloud platform typically needs to handle versatile tasks from numerous users. However, traditional EA optimizes only one task in a single run and unable to handle multiple tasks at the same time. To address this issue, we introduce a novel multi-task solver to resolve different tasks jointly via online learning and exploitation of problem-solving experiences across tasks. The results demonstrate that our proposal significantly outperforms the state-of-the-art peers. It is expected to facilitate the practical efficacy of industrial cloud system which faces multiple workflow scheduling tasks submitted from enormous users.

Cloud workflow scheduling (CWS) is critical for meeting user's high performance expectations in large-scale data processing and computing applications. CWS is known to be NP-hard and needs advanced scheduling techniques. Evolutionary algorithm and heuristic-based search techniques have gained massive popularity in addressing CWS, yet they either suffer from expensive computational cost or heavily rely on domain-specific experiences, which limit their practical applications. Bearing this in mind, we develop a novel evolutionary multi-task optimization framework to tackle a group of constrained CWS tasks simultaneously with the aid of adaptive cross-task problem-solving knowledge transfer. In particular, two collaborative knowledge exchange strategies, namely, constraint-free archive strategy and cross-task evolution strategy, are devised to extract useful building blocks from foreign tasks to boost the search efficiency. Further, to leverage the cooperative effects of both strategies, we develop an adaptive switching mechanism such that appropriate knowledge transfer strategies are learned automatically according to the population evolution status. Extensive experiments are conducted on real-world applications under various conditions, the comparison results show that our proposal delivers higher quality schedules than the state-of-the-art competitors in most cases.

When a multiobjective evolutionary algorithm based on decomposition (MOEA/D) is applied to solve problems with discontinuous Pareto front (PF), a set of evenly distributed weight vectors may lead to many solutions assembling in boundaries of the discontinuous PF. To overcome this limitation, this article proposes a mechanism of resetting weight vectors (RWVs) for MOEA/D. When the RWV mechanism is triggered, a classic data clustering algorithm DBSCAN is used to categorize current solutions into several parts. A classic statistical method called principal component analysis (PCA) is used to determine the ideal number of solutions in each part of PF. Thereafter, PCA is used again for each part of PF separately and virtual targeted solutions are generated by linear interpolation methods. Then, the new weight vectors are reset according to the interrelationship between the optimal solutions and the weight vectors under the Tchebycheff decomposition framework. Finally, taking advantage of the current obtained solutions, the new solutions in the decision space are updated via a linear interpolation method. Numerical experiments show that the proposed MOEA/D-RWV can achieve good results for bi-objective and tri-objective optimization problems with discontinuous PF. In addition, the test on a recently proposed MaF benchmark suite demonstrates that MOEA/D-RWV also works for some problems with other complicated characteristics.

Evolutionary algorithms via decomposition, namely, DEAs, decompose the original challenging problem and evolve a number of subproblems/subspaces concurrently in a cooperative fashion. Adaptive computational resource allocation (CRA) strategy is able to identify the efficiency of different subspaces and invest search effort on them accordingly in an online manner. A crucial issue for CRA is to measure the efficiency of subspaces. Unfortunately, existing approaches for efficiency measurement are either fitness improvement oriented or contribution oriented, which struggle to capture the potentials of subspaces accurately. To mitigate such drawback, we present an ensemble method for CRA, based on the recent fitness contribution rates (FCRs) and fitness improvement rates (FIRs) of subspaces simultaneously. In order to dynamically track the potential of each subregion, we adopt two memory matrices to record FIR and FCR for multiple subspaces over recent generations, respectively. Afterward, an aptitude vector indicating the potentials of subspaces is defined by exploiting FCR and FIR with memory and decaying scheme. On the basis of above strategies, an ensemble CRA (ECRA) scheme is designed, which is then embedded into an adaptive objective space partition-based DEA, termed ECRA-DEA, for solving the multi/many-objective optimization. Extensive experimental studies for ECRA-DEA on various types of challenging problems have been carried out and the results confirm that ECRA is effective. Besides, the competence of ECRA-DEA is empirically validated in comparison with state-of-the-art designs. The proposed ECRA paves a new way to leverage the capability of DEAs on handling complex problems.