Multiobjective cooperative multi-fitness in workflow scheduling problem

1. Introduction

During the last decade, Cloud computing has become a definitive model for executing compute-intensive distributed applications, attributed to its intrinsic flexibility, scalability, and pay-as-you-go approach. Among its service models, Infrastructure as a Service (IaaS) provides users with the means to dynamically allocate virtual machines (VMs) tailored to their computational needs. This enables researchers to access vast computational resources efficiently and cost-effectively, making it particularly attractive for the execution of scientific workflows (sWF). These workflows, often represented as Directed Acyclic Graphs (DAGs), encompass a wide range of complex interdependent tasks, with data exchange requirements varying from kilobytes to terabytes. It is acknowledged that the scheduling of these workflows within cloud environments poses considerable challenges due to the intricate nature of balancing multiple Quality of Service (QoS) objectives. This problem is recognised as being NP-complete.^1,2 Several surveys have analysed the scheduling of scientific workflows in cloud environments, highlighting its complexity, computational constraints, and relevance for both academia and industry. Comprehensive reviews by Wu et al., ³ Rodriguez and Buyya, ⁴ and Yassir et al. ⁵ provide taxonomies and discuss the evolution of algorithms and evaluation models used to tackle this problem in IaaS contexts.

In the context of scientific workflow scheduling, the makespan is a primary quality of service (QoS) metric. The makespan denotes the time required to complete all tasks in a workflow. It is imperative for researchers to minimise the makespan in order to accelerate the iterative process of experimentation. To accurately capture this objective, the most commonly adopted model for estimating execution time is the Network—Computing (NC) model, which considers computation and data transmission across the network, but typically ignores the impact of local disk I/O operations. While this simplification may suffice for compute-bound scenarios, it introduces significant inaccuracies when applied to data-intensive workflows, where disk access can become a major bottleneck. To address this limitation, the Disk—Network—Computing (DNC) model was introduced in Barredo and Puente. ⁶ This model extends the NC formulation by incorporating disk read/write times, leading to more accurate and realistic makespan estimations in cloud environments. In this study, we adopt the DNC model to ensure consistency with real-world execution behaviours observed in data-centric scientific applications.

Conversely, the exponential growth in energy consumption within cloud infrastructures, exacerbated by the increasing prevalence of artificial intelligence and big data applications, has made energy efficiency another critical objective. By 2025, data centres are expected to account for 4.5% of global energy consumption and contribute to 3.5% of global carbon emissions.^7,8 Consequently, optimising workflows entails addressing the inherent trade-offs between minimising makespan and reducing energy consumption to achieve sustainable and efficient scheduling solutions. Various models have been proposed in the literature to estimate energy consumption in workflow scheduling. Simplified approaches compute energy solely as a function of processing time, ⁹ while more refined models distinguish between active and passive consumption based on task execution and resource idleness.^10–12 In this work, we adopt the latter class of models, as they offer a good compromise between expressiveness and scalability. Although even more sophisticated strategies exist—such as DVFS-based models that account for voltage and frequency scaling^13,14—these often require low-level hardware access and are not supported by most public cloud infrastructures. Furthermore, foundational studies have shown that CPU usage is the primary contributor to energy consumption in data centres, ¹⁵ validating the CPU-centric abstraction we employ in our evaluation framework.

Approximate optimisation techniques, particularly metaheuristics, have gained prominence in addressing the workflow scheduling problem. Heuristic-based methods, such as the Heterogeneous Earliest Finish Time (HEFT) algorithm ¹⁶ and its energy-aware variant Green-HEFT, ¹¹ have demonstrated success in optimising single objectives like makespan or energy. Additionally, multi-objective approaches, such as Gravitational Search Algorithms, ¹⁷ Ant Colony Optimisation, ¹⁸ and hybrid strategies combining heuristics with metaheuristics,^19,20 offer mechanisms to balance conflicting objectives. Furthermore, hyper-heuristic approaches, such as the one proposed by Kabirzadeh et al., ²¹ combine multiple algorithms (i.e. genetic algorithm (GA), particle swarm optimisation (PSO), ant colony optimisation (ACO), and simulated annealing) using a test-and-select strategy to optimise energy consumption, runtime, network usage, and total cost.

Beyond traditional heuristics like HEFT or metaheuristics such as Particle Swarm Optimization (PSO), a wide range of nature-inspired algorithms have been proposed for complex scheduling and optimisation problems. Among these, Harmony Search, ²² Simulated Annealing, ²³ and Water Drop Algorithms^24,25 have shown remarkable performance in various engineering domains due to their exploration—exploitation trade-offs and adaptive mechanisms. Other recent proposals explore hybridisation techniques such as memetic search for energy efficiency, ²⁶ ensemble-based rule selection in multi-objective scheduling, ²⁷ or adaptive swarm intelligence models like enhanced grey wolf optimisation. ²⁸ These approaches, while powerful, typically evaluate candidate solutions through a single fitness pathway.

Scientific workflow scheduling has been widely addressed using multi-objective optimisation techniques. Several approaches leverage Pareto-based selection and problem-specific heuristics to balance conflicting objectives such as makespan, cost, and energy consumption. Representative works include list-based scheduling methods,^29,30 metaheuristic-based techniques for energy-aware planning, ³¹ and reinforcement learning-driven strategies for dynamic workflows.^32,33 Specifically, energy-aware scheduling has become a prominent research focus, as discussed in recent surveys by Verma et al. ³⁴ and Khattar et al., ³⁵ which review heuristic and dynamic power management strategies designed to reduce consumption in cloud-based workflows. These methods provide strong baselines but often rely on a single evaluation strategy or heuristic per solution. In this context, our proposal explores a cooperative approach where multiple expert decoders collaborate to guide the search in multi-objective settings.

A number of evolutionary algorithms have been described in the literature as utilising multi-fitness strategies to enhance solution quality in comparison with that achievable by conventional single-objective methods. These strategies can be categorised into two distinct approaches: the employment of distinct fitness functions at different stages of the algorithm, as observed in Wu et al., ³⁶ or the assessment of diverse aspects of the same solution, as seen in multi-fitness learning approaches, as discussed in Yates et al. ³⁷ However, despite the success of such methods, to the best of our knowledge, no approach has yet integrated multiple decoding functions to optimise the same fitness objective simultaneously.

In order to address these gaps, Cooperative Multi-Fitness (CMF) evolutionary algorithms have emerged as a promising approach. CMF introduces a novel mechanism in which multiple decoding functions collaborate to guide the search process. The fundamental premise of the CMF approach is to leverage the capabilities of existing heuristics to support and enhance the quality of the solution schedules generated by a basic decoding function. This approach ensures the primary function directing the search process remains unbiased with respect to the explored search space, while the supporting heuristic functions contribute by providing alternative solutions that may be of higher quality for the specific optimisation objective. The cooperative effect is reflected in the fact that the support functions recode the solution so that, in subsequent evaluations, the main basic function directly obtains the same improved solution. The effectiveness of CMF in improving scheduling quality for single objectives, such as makespan and total energy, has been demonstrated in previous works (Barredo and Puente ³⁸ and Barredo and Puente ³⁹ ). These algorithms utilise this polymorphic decoding systems and heuristic support functions to explore diverse regions of the solution space, thereby achieving superior results in comparison to standard mono-objective GA when minimising makespan or total energy respectively.

However, these previous efforts focus exclusively on mono-objective scenarios. The integration of multiple CMF schemes in a multi-objective optimisation context—where each heuristic may lead to distinct, potentially conflicting, high-quality solutions—remains unexplored. This raises an important research question: can the CMF paradigm be extended to support multiple objectives simultaneously, without undermining the structural clarity and diversity required by Pareto-based evolutionary algorithms?

This paper proposes a novel decoding mechanism for individuals in the context of multi-objective evolutionary algorithms, applied to scientific workflow scheduling in cloud environments. The approach builds on the foundations established in previous studies.^38,39 The proposed approach integrates the CMF paradigm into the NSGA-II ⁴⁰ algorithm to simultaneously optimise both makespan and total energy. Each chromosome is decoded using multiple heuristic strategies—one per objective—resulting in multiple candidate solutions. These are evaluated independently, and their corresponding scheduling structures are used to recode the genotype using a Lamarckian mechanism. Thus, the chromosome becomes capable of regenerating all heuristic-improved solutions without relying on the heuristics in subsequent iterations.

This approach breaks the traditional one-to-one mapping between genotype and phenotype by enabling one-to-many decoding. The offspring pool is effectively multiplied, improving diversity and enriching the approximation of the Pareto front. Moreover, since solutions guided by each heuristic tend to dominate in their respective objective, the cooperative evaluation naturally supports the generation of well-distributed Pareto-optimal solutions.

Following the concepts described in Barredo and Puente, ³⁹ this research put emphasis on exploring the following concepts:

Extending the Cooperative Multi-Fitness approach from mono-objective to multi-objective optimisation in a coherent evolutionary framework.

The remainder of this paper is organised as follows: Section 2 establish the context of the paper as a follow up to previous research. Section 3 describes the novel concept of Multi-Objective Cooperative Multi-Fitness. Section 4 defines the scientific workflow scheduling problem and presents the extended Disk-Network-Computation (DNC) computation and energy model. Section 5 describes the structure of the NSGA-II-based algorithm and the integration of the CMF paradigm. Section 6 describes the inner works of this novel method. Section 7 reports the experimental evaluation and analyses the trade-offs between makespan and energy. Finally, Section 8 summarises the conclusions and future directions.

2. Background: Cooperative multi-fitness strategy

The Cooperative Multi-Fitness (CMF) strategy, originally proposed in Barredo and Puente,^6,38 is designed to enhance the effectiveness of standard genetic algorithms (GAs) in solving complex workflow scheduling problems. Unlike hybrid approaches that define multiple co-evolving populations or competitive decoding schemes, CMF relies on a single population evaluated through multiple support heuristics working cooperatively.

CMF builds upon a conventional GA with a direct decoding flow: chromosome → decoder → phenotype/fitness. In this context, each chromosome encodes a sequence of tasks, where each gene specifies both the task and the virtual machine (VM) to which it is assigned. The decoder interprets the chromosome to generate a scheduling plan, and the fitness function evaluates it.

This direct decoding ensures that the search space remains unbiased, allowing optimal solutions to remain reachable. However, when applied to large-scale workflows involving thousands of tasks and heterogeneous VMs, the basic GA lacks sufficient search efficiency to generate high-quality schedules—whether the objective is makespan or energy consumption.

To address this, CMF introduces a set of support heuristics specialized in optimizing a particular objective (e.g., makespan or energy). These heuristics can produce more efficient schedules, albeit often converging to local optima due to their inherent bias. The novel aspect of CMF is its use of Lamarckism: when a support heuristic discovers a superior schedule, it rewrites the chromosome to reflect this plan (task order and VM assignment). This enables the standard decoder to regenerate the improved solution, potentially improving the GA’s effectiveness without altering its fundamental structure.

3. Multi-objective cooperative multi-fitness strategy (MOCMF)

This work extends the CMF framework into the multi-objective domain through the introduction of the Multi-Objective Cooperative Multi-Fitness strategy. MOCMF integrates cooperative support functions into a multi-objective evolutionary algorithm, such as NSGA-II, to simultaneously optimise conflicting objectives, including makespan and energy consumption.

The key innovation of MOCMF lies in assigning a tailored package of support heuristics to each objective, allowing the evaluation of a chromosome to proceed independently for each optimisation goal. When a heuristic group discovers an improved schedule, it generates a recoded chromosome that encodes the relevant scheduling information. This enables the standard decoder ( S t d F i t ) to later reconstruct the schedule without access to the heuristic. As a result, each chromosome gives rise to multiple decoded solutions—one per objective—which are evaluated separately. This cooperative decoding strategy naturally aligns with dominance-based multi-objective optimisation and expands the exploratory capacity of the algorithm: for N chromosomes and k objectives, the decoding process yields up to k × N evaluated solutions, enhancing both diversity and convergence towards the Pareto front.

This cooperative multi-fitness mechanism is conceptually independent from the underlying multi-objective evolutionary algorithm. It operates exclusively at the genotype-to-phenotype mapping level, incorporating objective-specific heuristics and Lamarckian recoding. As such, MOCMF can be regarded as an orthogonal component that integrates with existing MOEAs to enrich the evaluation process without altering their evolutionary dynamics.

Moreover, by leveraging the JMetal framework, ⁴¹ this approach remains compatible with multiple MOEAs such as NSGA-II, ⁴⁰ SPEA2, ⁴² and IBEA, ⁴³ ensuring scalability and comparability.

While this strategy increases computational cost, the total number of individuals generated per generation is adjusted accordingly. This adjustment is intended to preserve the convergence behaviour of the algorithm and support a fair comparison with configurations that do not use MOCMF—such as S t d F i t alone or CMF applied to a single objective. Further details regarding implementation choices, comparison settings, and computational cost control are provided in the experimental section.

4. Workflow scheduling problem definition

Although the following formulation focuses on scientific workflow scheduling in cloud environments, this problem is used as a representative and practically relevant instance of a broader class of permutation-based, multi-objective scheduling problems under precedence and resource constraints. The proposed Cooperative Multi-Fitness mechanism is intended to be general and applicable beyond this domain, provided that suitable objective-specific heuristics are available.

Scientific workflows are typically represented as directed acyclic graphs (DAGs). The DAG, denoted by G = ( T , A ) , captures the structure of the workflow’s tasks, dependencies, and communication requirements. Nodes in T = { t 1 , t 2 , … , t n } represent individual tasks within the workflow. Each node is annotated with a label indicating its computational workload in terms of Million Floating Point Operations (MFLOPs). Arcs or dependency links A = { ( t i , t j ) | 1 ≤ i ≤ n , 1 ≤ j ≤ n , i ≠ j } represent dependencies between tasks. Each arc is denoted as d a t a ( i , j ) , indicating the size of data (in Megabytes) transferred from task t i to task t j . This representation helps identify critical paths and bottlenecks in the workflow.

The graph includes two dummy nodes: t e n t r y (entry point) and t e n d (exit point). These nodes have no computational or communication requirements but serve as unique entry and exit points for the workflow.

The resource model is based on a cloud service provider offering an Infrastructure-as-a-Service (IaaS) platform with a mix of virtual machines (VMs). Let M = { v m 1 , v m 2 , … , v m m } denote the set of available VMs. Each VM is characterised by a tuple < p c , n b , d s , p p , a p > , where:

p c represents processing capacity (in GFLOPS),

Given a workflow G = ( T , A ) and an IaaS infrastructure represented by the set of VMs M , the Workflow Scheduling Problem can be formulated as finding a feasible solution S = ( H o s t s , O r d e r ) . Here:

H o s t s is a mapping from tasks to VMs,

The objective is twofold: 1. To minimise the makespan ( E F T ( t e x i t ) ), which is the estimated finish time of the exit task t e n d . 2. To minimise the total energy consumption ( T E ( S ) ) incurred in solution S .

Mathematically, these objectives can be expressed as:

m i n i m i z e E F T ( t e x i t )

(1)

m i n i m i z e T E ( S )

(2)

4.1. Workflow schedule evaluation model

The makespan of a workflow schedule is calculated using the DNC model, as described by Barredo and Puente. ⁶ Unlike the traditional Network-Computation (NC) model,^11,44–46 which ignores disk access times and only considers network communications and CPU execution, the DNC model provides a more complete and accurate evaluation by including both disk and network transfer phases. This enhancement is particularly relevant in cloud environments, where I/O operations may significantly impact total execution time, especially in data- or storage-intensive workflows.

In the DNC model, the estimated start time of a task depends not only on the availability of computational resources but also on the location of its predecessor tasks. If predecessor data is available locally, only local disk reading times are incurred. Otherwise, remote disk access combined with network communication is required. Additionally, the DNC model includes local disk write times after task execution to account for output dataset storage.

To better illustrate the impact of the DNC model, we consider a simple example workflow shown in Figure 1, consisting of three computational tasks and a dummy initial task to define a single entry point. Each computational task requires 1 time unit (TU) and produces 1 data unit (DU) of output.

OPEN IN VIEWER

Figure 1.

Example workflow with three computational tasks and one fictitious entry task to ensure a single entry and exit point.

Figure 2 compares the resulting schedule under two execution models: the standard Network-Computation (NC) model (a), and the extended Disk-Network-Computation (DNC) model (b). The scenario involves two hosts: Host A, with a disk transfer speed of 1 DU/TU, and Host B, with 0.5 DU/TU. Network transmission speed is assumed to be 1 DU/TU.

OPEN IN VIEWER

Figure 2.

Execution timelines under the NC (a) and DNC (b) evaluation models for the workflow in Figure 1. The DNC model incorporates local/remote disk read and write operations before and after computation.

In the NC model, only network transfer times are considered, and the successor task starts as soon as data from the last completed predecessor is received. This leads to a makespan of 3 TU. In contrast, the DNC model accounts for all disk read and write operations, which must be completed before a successor task can begin. The slower disk on Host B increases data transfer time, and tasks may be forced to wait for local or remote disk operations. As a result, the makespan increases to 8 TU, demonstrating the critical role of disk throughput in realistic cloud environments.

The computational time spent on a specific task i running on host k is determined by dividing the number of operations required by the task (expressed in gigaflops, size ( i ) ) by the processing capability of the host ( pc k , expressed in gigaflops per second). This relationship can be defined as:

c t i k = size ( i ) pc k

(3)

where:

c t i k is the computational time for task i on host k .

size ( i ) is the number of operations required by task i (in gigaflops).

pc k is the processing capability of host k (in gigaflops per second).

Tasks may require reading input data from parent tasks, which can be located either on the same host or a different host. The data transfer time depends on whether the parent and child tasks are executed on the same or different hosts.

If the parent and child tasks are on the same host, the data transfer time is calculated as:

d t i , j k , k = data ( i , j ) ds k

(4)

where:

d t i , j k , k is the data transfer time from parent task j to child task i on the same host.

data ( i , j ) is the amount of data transferred (in megabytes).

ds k is the disk speed of host k .

If the parent and child tasks are on different hosts, the data transfer time involves three components: the disk speed of the parent host ( ds k ), the network bandwidth of the parent host ( nb k ), and the network bandwidth of the child host ( nb l ). The transfer time is then:

d t i , j k , l = data ( i , j ) min ( ds k , nb k , nb l )

(5)

where:

d t i , j k , l is the data transfer time from parent task j on host k to child task i on host l .

min ( ⋅ ) represents the minimum of the three speeds, as this determines the bottleneck for the transfer.

The estimated finish time ( EFT ( i , k ) ) of a task is calculated by summing four components:

The finish times of all parent tasks.

The data transfer times from all parent tasks to the current task.

The computational time of the task.

The data write times of the output files.

The formula for EFT ( i , k ) is:

E F T ( i , k ) = E S T ( i , k ) + i n p u t ( i , k ) + c t i k + o u t p u t ( i , k )

(6)

Where:

EST ( i , k ) is the earliest start time of parent task i on host k .

i n p u t ( i , k ) is the the time spent reading the predecessor tasks.

c t i k The computational time.

o u t p u t ( i , k ) is the time spent writing the successor tasks.

The total time spent reading data from parent tasks can be defined as the summation of all data transfers from task predecessors, where d t j , i l , k represents the data transfer from task j to task i on hosts l and k .

i n p u t ( i , k ) = ∑ t j ∈ p r e d ( t i ) d t j , i l , k

(7)

The total time spent writing information out can be defined as the summation of all data needed by successors divided by the speed of the current host. Therefore, d a t a ( i , j ) denotes the data required by successor task j from task i , and d s k is the disk speed of the k host.

o u t p u t ( i , k ) = ∑ t j ∈ s u c c ( t i ) d a t a ( i , j ) d s k

(8)

The EST for a task ((i,k)) can be mathematically defined as:

E S T ( i , k ) = a v a i l ( i , k , max t j ∈ p r e d ( t i ) ( E F T ( j , l ) ) )

(9)

Provided, a v a i l ( i , k , ⋅ ) represents the availability function on host k for task i , and E F T ( j , l ) denotes the earliest finish time of predecessor task j on host l . This equation ensures that a task is scheduled as early as possible while respecting both dependency constraints and resource availability.

4.2. Total energy model

The total energy consumption in a cloud environment can be broken down into two primary components: active energy and passive energy. Active energy refers to the energy required to execute tasks, which involves the CPU and disk operations. These activities generate specific energy consumption during task execution. On the other hand, passive energy is the energy needed to keep servers operational, even when they are waiting between tasks. Notably, all servers are powered on and off simultaneously, meaning that the makespan (the total time from the start of the first task to the completion of the last task) significantly impacts passive energy consumption. As the execution duration increases, so does the cumulative time the servers remain running.

Passive energy can be mathematically defined as the summation of the product between the passive energy consumption rate of each server and the makespan (or estimated finish time of the last task). This relationship is expressed in Equation 10:

E p ( S ) = ∑ k ∈ M P p ( k ) ⋅ E F T ( t e n d )

(10)

where P p ( k ) represents the passive energy consumption rate of server k , and E F T ( t e n d ) is the estimated finish time of the last task.

For active energy, the energy consumed by a specific task executed on a specific host can be defined as the product of the active energy consumption rate of the virtual machine V M and the total computation time required to complete the task. This is shown in Equation 11:

E a = P a ( i , k ) ( ˙ i n p u t ( i , k ) + c t i k + o u t p u t ( i , k ) )

(11)

where P a ( i , k ) denotes the active energy consumption rate of task i on host k , i n p u t ( i , k ) stands for the time spent in reading input data, c t i k is the computation time of task i when executed on host k , and o u t p u t ( i , k ) the time spent in writing output data.

The total active energy for the entire workflow is then obtained by summing the active energy consumed by all tasks across all hosts, as represented in Equation 12:

E a ( S ) = ∑ i ∈ T , ∈ H o s t s E a ( i , k )

(12)

where T is the set of all tasks and H o s t s represents the set of all hosts.

Finally, the total energy consumption for the workflow is the sum of both active and passive energy components:

E ( S ) = E p ( S ) + E a ( S )

(13)

Evolutionary algorithms span a wide range of strategies, from deterministic single-solution methods ⁴⁷ to population-based stochastic approaches such as the genetic algorithm NSGA-II. ⁴⁰ In this work, we adopt the latter framework, integrating our cooperative multi-fitness decoding mechanism to enhance performance in multi-objective optimisation. This section introduces the standard NSGA-II framework, adapted to the workflow scheduling problem. The algorithm serves as a baseline evolutionary structure, within which CMF is integrated as a genotype—phenotype mapping and cooperative evaluation strategy. A detailed illustrative example is provided later in Section 6, following the complete description of the multi-objective formulation.

The presented optimization metaheuristic is a multiobjective genetic algorithm builds upon previous work detailed in Barredo and Puente. ⁶ In earlier approaches, the concept of using cooperative multiple fitness functions was introduced to address makespan optimisation. ³⁸ Subsequently, this approach was extended to tackle energy consumption. ³⁹ In this work, we aim to address the simultaneous optimisation of both objectives, thereby moving into a multi-objective context. As such, it becomes natural to extend the single-objective genetic algorithm to the standard NSGA-II, as it merely involves replacing our selection and replacement operators. The challenge now lies in how to address the CMF approach within this multi-objective context. The genetic algorithm operates within a multi-objective context and employs the NSGA-II framework.

The algorithm is defined by several key parameters: p o p s i z e refers to the number of individuals in the initial population; m a x g e n s denotes the maximum number of generations before termination; and p c and p m represent the crossover probability and mutation probability, respectively.

Chromosome Encoding. Each chromosome is represented as a permutation of pairs ( i , k ) , where 1 ≤ i ≤ | T | identifies a task and 1 ≤ k ≤ | M | specifies the host machine. The chromosome must adhere to topological order, ensuring that no task is scheduled before its predecessors or after its successors.

As an illustrative example, consider a workflow with four tasks ( T 1 to T 4 ) and two virtual machines ( V M 1 , V M 2 ). A feasible chromosome could be:

[ ( T 1 , V M 2 ) , ( T 4 , V M 1 ) , ( T 2 , V M 1 ) , ( T 3 , V M 2 ) ]

Crossover Operator. The crossover is based on the works of Zhu et al., ⁴⁶ where using the CrossoverOrder approach guarantees the preservation of the topological order. The operator begins by randomly selecting a crossover point that partitions each parent into two subsequences. The initial segment of each offspring is formed by copying the first subsequence from one parent. The remaining positions are then completed by inserting the missing tasks from the other parent, preserving their original relative order. Because the relative precedence between any pair of tasks is guaranteed to be maintained in at least one parent, the resulting offspring respect all dependency constraints and preserve a valid topological order.

Mutation Operator. The mutation operator first selects a task T i at random from the chromosome. It then identifies all of T i ’s direct predecessors and successors in the workflow’s dependency graph. Next, it determines the maximal contiguous subsequence of genes that does not contain any of these dependent tasks. Within this safe region, T i is relocated to a randomly chosen position, ensuring that the resulting task order remains topologically valid. Additionally, the virtual machine assigned to T i is randomly changed to one of the available VM types, introducing further diversity in the resource allocation dimension.

Initial population. The initial population is generated randomly, with each chromosome constructed to follow topological order while assigning VMs to tasks at random. The size of the population is determined by p o p s i z e .

New Decoding Schema. The primary fitness function, denoted as S t d F i t , employs the DNC evaluation model to compute the time required to complete each task. For each gene ( i , k ) in the chromosome, the start time of task t i on VM v m k is scheduled at the earliest feasible moment, ensuring that all predecessor tasks are completed and the machine is available. The makespan is defined as the completion time of the last task, and the total energy consumption is obtained using the evaluation model previously defined in the equation 13.

The proposed innovation lies in the use of different lists of supporting fitness functions, one for each different objective, denoted by l f i t n e s s o b j , where o b j means the corresponding objective to be optimised, in our case makespan ( M k p ) or total energy ( T E ). This cooperative multi-fitness approach and its extension to a multi-objective context is described in the next subsection.

6. Multi-objective cooperative multi-fitness decoding and evaluation function

Initially introduced for single-objective optimisation in Barredo and Puente, ³⁸ each chromosome is evaluated using multiple functions, i.e. the standard decoding function S t d F i t assisted by a lis t of supporting heuristic fitness functions. As we are now in a multi-objective context, fitness values are a tuple of single objective values ( m k p , t e ) where m k p is the makespan and t e the total energy consumed by the evaluated solution. The cooperative multi-fitness is applied to obtain the actual schedule, fitness, and potentially updated solution, as outlined in Algorithm 1.

OPEN IN VIEWER

In addition to the solution ( s o l ) to be evaluated, it is also necessary to provide the list ( l f i t n e s s o b j ) of all the supporting fitness functions to be executed for the current objective ( o b j ). Each fitness function generates a schedule and its corresponding fitness value. The algorithm uses < o b j ordinal operator to select the minimum of these values for the current objective o b j . To enhance convergence and ensure a genuinely cooperative multi-fitness, the Lamarckian learning method ⁴⁸ is employed as the final stage of the evaluation phase to expedite convergence towards potential optimal solutions, using the recoding procedure formalised in Algorithm 2. Consequently, the gene order of the chromosome and the machine-task mapping are re-coded based on the resulting topological order of the best generated schedule. The rationale behind this is that if the heuristic schedules are indeed the best, their advantageous characteristics are transferred into the chromosomes, enabling the basic fitness function, S t d F i t , to extract them directly by means of simple decoding.

OPEN IN VIEWER

However, in a multi-objective scenario, this approach is insufficient because a solution that minimises one objective may not necessarily minimise another. To address this, it is necessary to duplicate every solution and apply two distinct sets of support fitness functions, l f i t n e s s M k p and l f i t n e s s T E , to evaluate the duplicates. The aim is to optimise makespan or total energy, depending on the applied supporting functions set, and the specified objective, in the multi-fitness algorithm. This results in the number of evaluated solutions being doubled with respect to a mono-objective approach, being a factor that should be given due consideration in the subsequent experiments design. It is important to note that each evaluated solution may generate up to as many candidate solutions as there are objectives, all of which are added to the pool of evaluated individuals. The replacement operator employed by NSGA-II will select solutions based on the ranking and crowding distance.

To clarify how CMF mechanism operates within a multi-objective evolutionary algorithm, we present the following simplified example.

Consider a chromosome that encodes the execution order and resource assignment for three tasks: T 1 , T 2 , and T 3 . The chromosome structure specifies both the task sequence and the host allocation (Host A or Host B). The base chromosome is s 0 : [T1-A, T2-B, T3-A].

This chromosome is evaluated using the S t d F i t function and both lists of heuristics, each specialised in a single objective:

Heuristics for makespan minimisation ( l f i t n e s s M k p ): H 1 M k p and H 2 M k p .

Each heuristic applies its own decoding strategy and produces a distinct schedule, evaluated with respect to both objectives. The results of these evaluations are summarised in Table 1. While the values shown are hypothetical, they are designed to reflect meaningful ranking relationships among the solutions.

In this example, all heuristics evaluate the same chromosome s s t d , but each produces a different schedule. The makespan-oriented heuristic H 1 M k p yields the best performance in terms of makespan, and is therefore selected to recode the chromosome as shown in Figure 3. As a result, the base decoder S t d F i t will later reproduce the schedule corresponding to H 1 M k p , from the re-coded chromosome s m k p . Likewise, H 2 T E generates the schedule with the lowest energy consumption and triggers a second recoding process, producing re-coded chromosome s t e .

OPEN IN VIEWER

Figure 3.

Resulting chromosome after Lamarckian recoding using the schedule obtained through CMF decoding (optimising makespan; analogous for energy).

In the multi-objective context, both s m k p and s t e are retained as distinct offspring in the population. This mechanism illustrates how cooperation between heuristics enhances evolutionary search by preserving solutions that are optimal with respect to different objectives, while maintaining diversity through genotype-to-multiple-phenotype mapping. In the context of Pareto dominance, the solutions generated through this cooperative evaluation process are merged with the rest of the offspring population. In the particular case of NSGA-II, their survival in the next generation is determined by the standard replacement criteria of non-dominated sorting and crowding distance.

In the next subsection, the different lists of supporting functions for each objective, as well as standard fitness function, are introduced.

6.1. Standard and supporting functions

The following functions serve different purposes, since there are several objectives to meet. Each function is designed to address a specific objective. However, it is notable that functions specialised in energy, while addressing the primary objective, incorporate the makespan into their considerations.

S t d F i t :

This is the baseline fitness function, which evaluates the chromosome exactly as it is provided. It does not alter the task order or the task-to-VM mapping. Since this function does not interfere with the chromosome, it serves as a neutral evaluator and allows changes introduced by crossover and mutation operations to be directly reflected in the evaluation.

H 1 T E :

This function targets the minimisation of total energy consumption while preserving the task order specified in the chromosome. It modifies only the task-to-VM mapping. For each task, it attempts to assign it to a VM that does not increase the current makespan. Among the VMs that satisfy this condition, the one with the lowest energy consumption for the task is selected. If no such VM exists—such as in the case of the first task or when dependencies constrain scheduling—the function selects the VM with the minimum energy cost. In cases where multiple VMs offer the same energy efficiency, the tie is broken by choosing the VM that results in the earliest task completion time.

H 2 T E :

Also focused on reducing energy consumption, this function incorporates task runtime as a guiding criterion. It preserves the task order defined by the chromosome but adjusts the task-to-VM mapping. For each task, the function evaluates its estimated total runtime—which includes both CPU execution and communication delays—and compares it to the average runtime of all tasks. If the task’s runtime is below the average, it is assigned to the VM with the lowest energy consumption. Conversely, if the runtime exceeds the average, the task is mapped to the VM that provides the shortest execution time for that task.

H 1 M K P :

This function is designed to reduce the makespan by applying the first stage of the HEFT (Heterogeneous Earliest Finish Time) algorithm. Unlike previous functions, it ignores the task order defined in the chromosome. Instead, it computes a new order based on upward ranks, prioritizing tasks expected to finish earlier according to averaged CPU and communication times. However, the task-to-VM mapping from the original chromosome is preserved.

H 2 M K P :

Focusing also on makespan reduction, this function applies the second phase of the HEFT algorithm. It keeps the task order as specified in the chromosome but adjusts the VM assignments. Each task is scheduled on the VM that allows it to complete at the earliest possible time, accounting for both VM availability and communication overheads.

The combination of these functions constitutes the basis of the two mono-objective CMF approaches. Specifically, C M F M k p integrates S t d F i t alongside the two makespan-focused heuristics, H 1 M k p and H 2 M k p . Conversely, C M F T E integrates S t d F i t with the energy-oriented support functions, H 1 T E and H 2 T E . These configurations enable each CMF variant to leverage the strengths of its supporting heuristics while maintaining the neutrality of S t d F i t as a reference decoding function. Building upon these mono-objective strategies, the Multi-Objective Cooperative Multi-Fitness approach is introduced to simultaneously optimise makespan and total energy.

7. Experimental study

Previous studies using the CMF approach have employed a mono-objective genetic algorithm to optimise workflow scheduling in a set of virtual machines. In particular, in Barredo and Puente, ³⁸ the CMF approach proved to be more effective in optimising makespan than both the direct chromosome decoding function ( S t d F i t ) and the individual heuristic functions ( H 1 M k p and H 2 M k p ).

Furthermore, in Barredo and Puente, ³⁹ a correlation analysis between makespan and total energy revealed that optimising total energy also led to an improvement in makespan. This is due to the fact that the heuristics H 1 T E and H 3 T E implicitly incorporated the concept of makespan into their definitions.

The aim of this study is to assess the effectiveness of applying the Cooperative Multi-Fitness strategy in a Multi-Objective context (MOCMF). To this end, the NSGA-II algorithm has been adopted to simultaneously optimise makespan and total energy. The experimental evaluation will focus on the following key aspects:

Assessing the performance of the mono-objective CMF functions (proposed in Barredo and Puente ³⁸ and Barredo and Puente ³⁹ ) within a multi-objective framework, comparing them against their individual component fitness functions.

whether the combined use of both CMF functions (for makespan and total energy) in the MOCMF approach yields significantly better results than their respective mono-objective versions.

7.1. Benchmark instances

Workflows can vary in size and shape, thus having an accurate notion of how the different fitness functions work, is critical. Therefore we need to have different workflows. WFCommon ⁴⁹ repository is a public repository containing multiple executions of seven different workflows ⁵⁰ , each family have multiple instances. For each of the families we have selected four, with different tasks sizes, having a range from extra-small(50-100) to large number of tasks (500-1000), with two more sizes in between, small (100-200) and medium (200-500). The instance sizes can be seen in the Table 2.

1000Genome: The 1000 Genomes Project serves as a reference for human genetic variation. The Workflow uses this data to analyze mutational overlaps, enabling robust statistical evaluation of mutations potentially linked to diseases.

Cycles: Cycles is a model that simulates daily crop production and nutrient cycles while accounting for various agronomic practices and allowing custom crop specifications.

Epigenomics: The Epigenomics workflow processes genome sequencing data, mapping it to a reference genome and supporting DNA methylation and histone modification analysis.

Montage: Montage is a workflow for assembling FITS images into custom mosaics by re-projecting, background correcting, and combining astronomical images.

Seismology: The Seismology workflow preprocesses and cross-correlates acceleration measurements from multiple seismic stations, supporting data-intensive seismic analysis.

SoyKB: The SoyKB workflow re-sequences soybean germplasm to identify SNPs and indels using GATK and a reference genome.

SRASearch: SRA workflow aligns data from the INSDC Sequence Read Archives using tools like Samtools and Bowtie2.

OPEN IN VIEWER

Table 2.

Every instance grouped by problem.

Problem	Type	Instance	Tasks
Seismology	data
		seismology-chameleon-100p-001	101
		seismology-chameleon-500p-001	501
		seismology-chameleon-700p-001	701
		seismology-chameleon-1000p-001	1001
Cycles	compute
		cycles-chameleon-1l-1c-9p-001	67
		cycles-chameleon-2l-1c-12p-001	437
		cycles-chameleon-2l-1c-9p-001	133
		cycles-chameleon-5l-1c-12p-001	1091
Epigenomics	data
		epigenomics-chameleon-hep-1seq-100k-001	41
		epigenomics-chameleon-ilmn-1seq-100k-001	125
		epigenomics-chameleon-hep-6seq-100k-001	507
		epigenomics-chameleon-ilmn-6seq-100k-001	863
SRASearch	data
		srasearch-chameleon-10a-005	22
		srasearch-chameleon-20a-003	42
		srasearch-chameleon-40a-003	84
		srasearch-chameleon-50a-003	104
Montage	compute
		montage-chameleon-2mass-005d-001	58
		montage-chameleon-2mass-01d-001	103
		montage-chameleon-dss-10d-001	472
		montage-chameleon-dss-125d-001	1066
SoyKB	data
		soykb-chameleon-10fastq-10ch-001	96
		soykb-chameleon-10fastq-20ch-001	156
		soykb-chameleon-30fastq-10ch-001	256
		soykb-chameleon-40fastq-20ch-001	546
1000genome	data
		1000genome-chameleon-2ch-250k-001	82
		1000genome-chameleon-4ch-250k-001	164
		1000genome-chameleon-12ch-250k-001	492
		1000genome-chameleon-18ch-250k-001	738

The families not only vary in shape and sizes, also there are families with a huge amount of communications with will impact greatly in the disk and network usage. This can help better understand how these two can impact the final makespan of total energy.

7.2. Benchmark platform

To analyse the trade-off between execution time and energy consumption, we define a heterogeneous computing platform composed of two types of hosts, whose characteristics are summarised in Table 3. Each host type differs in computational throughput and power consumption.

OPEN IN VIEWER

Table 3.

Host characteristics on the benchmarking platform. Units: Throughput (GFLOPS), active power, and passive power (watts). Based on the SPECpower benchmark. ⁵¹

		Active	Passive
Processor	Throughput	Power	Power
AMD EPYC 4584PX	67.2	68.5	43.5
Intel Xeon Platinum 8471N	93.6	330.8	88.2

Two power modes are considered (both expressed in Watts): passive power refers to the energy consumed when a host is powered on but idle, while active power refers to energy consumption during task execution. We assume that each task utilises 100% of the CPU during its execution.

Throughput is expressed in GFLOPS, representing the number of floating-point operations the CPU can execute per second. The AMD EPYC 4584PX offers lower throughput but is energy-efficient, while the Intel Xeon Platinum 8471N provides higher performance at the cost of significantly greater energy consumption. As a result, neither host type is universally optimal: the AMD processor yields longer execution times with lower energy usage, while the Intel processor achieves shorter runtimes at a higher energy cost.

Both host types share the same disk and network configuration: a solid-state drive (SSD) with 540 MB/s I/O speed and a 1 Gbps network interface.

Each benchmark instance is tested under four different host configurations, using 2, 4, 8, and 16 hosts with an even distribution between the two host types.

All experiments are repeated 10 times. Each algorithm is allowed a total budget of 100,000 solution evaluations. For standard configurations, this corresponds to a population of 100 individuals and 100 offspring generated per generation, over 1000 generations. Mutation and crossover probabilities are set to 0.1 and 1.0, respectively, following the configurations validated in previous mono-objective studies.^38,39

In the case of MOCMF, each offspring produces one decoded solution per objective (i.e., two evaluations per offspring in a bi-objective setting). To ensure a fair comparison in terms of computational effort, the number of offspring generated per generation is reduced to 50, resulting in the same total number of evaluations per generation. The population size remains unchanged.

The experiments are implemented using the open-source Java framework JMetal. ⁴¹ Experiments are executed on a Linux server equipped with a 12th Gen Intel ® Core TM i9-12900 processor (2.40 GHz) and 32 GB of RAM. All results are publicly available at the website: https://github.com/iScOp-uniovi/Paper_ICAE_Barredo_2025.

7.3. Efficiency of the mono-objective Cooperative Multi-Fitness Approach in the Multi-objective Scenario

We evaluate the efficiency of fitness functions designed for single-objective optimisation in a multi-objective setting. Specifically, we analyse the impact of fitness functions tailored to optimise makespan and total energy independently, comparing their performance within NSGA-II across all instances. The primary performance metric used is the Hypervolume (HV).

To assess statistical significance, we conduct a Friedman test followed by a Holm post hoc test to compare the ranking of different approaches. This procedure follows the recommendations for non-parametric statistical analysis of algorithm performance across multiple problem instances. ⁵² The results are summarised in Table 4.

OPEN IN VIEWER

Table 4.

Average ranking of evaluated fitness strategies across six performance metrics: Hypervolume (HV), inverted generational distance (IGD), inverted generational distance plus (IGD+), generational distance (GD), epsilon indicator (EP), and spread. Lower values indicate better performance.

	Rankings
Fitness Strategy	HV	IGD	IGD+	GD	EP	Spread
M O C M F	2.607	2.607	2.241	1.786	2.687	6.955
C M F M k p	3.147	3.125	2.812	2.268	3.013	6.884
H 2 M k p	3.460	3.321	3.670	4.357	3.353	3.813
C M F T E	3.558	3.665	3.665	2.661	3.290	6.393
H 2 T E	4.500	4.701	4.942	5.179	4.692	3.786
H 1 T E	5.196	5.161	5.339	5.768	5.268	3.482
H 1 M k p	6.621	6.384	6.330	6.875	6.634	1.723
S t d F i t	6.911	7.036	7.000	7.107	7.062	2.964

Although the revised table omits statistical test columns for clarity, we note that the rankings presented are fully supported by statistical significance tests. In particular, the top-performing strategy ( M O C M F ) achieved the lowest average ranking (2.607), and all pairwise comparisons with alternative strategies yielded p-values below 0.05, with the null hypothesis of equal performance rejected in every case. These results confirm that the observed ranking differences are not only consistent but also statistically significant.

When incorporating additional performance metrics—namely Inverted Generational Distance (IGD), Inverted Generational Distance Plus (IGD+), Generational Distance (GD), Epsilon Indicator (EP), and Spread—a consistent pattern emerges: M O C M F maintains top-ranking positions across all convergence-related metrics (HV, IGD, IGD+, GD, EP), confirming its ability to consistently generate high-quality approximations of the Pareto front. Its lower ranking in Spread can be attributed to its strong convergence bias, which may lead to less evenly distributed solutions.

The hybrid strategies C M F M k p and C M F T E closely follow M O C M F in most indicators, particularly in GD and IGD+, indicating they benefit from heuristic guidance even in isolation. In contrast, heuristic-only strategies such as H 1 M k p and S t d F i t show significantly weaker performance in convergence-oriented metrics (especially GD and IGD), despite achieving better rankings in Spread. This suggests that while they contribute to diversity, they lack the adaptability and convergence efficiency of the cooperative models.

These results reinforce the effectiveness and robustness of the cooperative multi-fitness architecture, particularly when evaluated across a comprehensive set of Pareto front quality indicators that capture both convergence and diversity dimensions.

OPEN IN VIEWER

Table 5.

Median hypervolume obtained for makespan-based fitness functions across different problem families. In bold the best result for each problem.

Problem	S t d F i t	H 1 M k p	H 2 M k p	C M F M k p
1000genome	1%	2%	26%	31%
cycles	0.01%	2%	5%	8%
epigenomics	0.60%	0.44%	36%	35%
montage	0.26%	0.43%	24%	28%
seismology	2%	2%	33%	31%
soykb	0.35%	2%	8%	10%
srasearch	5%	7%	45%	42%

While six performance metrics are included in the ranking to provide a comprehensive multi-objective evaluation, we focus the detailed analysis on the Hypervolume (HV) indicator. HV is widely recognised for simultaneously capturing convergence and diversity properties of Pareto front approximations, and is therefore particularly suitable for evaluating the overall quality of multi-objective solutions. ⁵³ Other metrics are used to support the robustness of the findings, but their individual analysis is omitted here for the sake of clarity and conciseness.

7.3.1. Evaluation of makespan-oriented fitness functions

The first experiment compares four fitness functions designed to optimise makespan:

S t d F i t : a baseline direct chromosome decoding function.

H 1 M k p and H 2 M k p : heuristic-based functions incorporating domain knowledge for makespan optimisation.

C M F M k p : a cooperative multi-fitness approach combining the three previous functions.

From Table 4, we observe that:

C M F M k p achieves a ranking of 3.147, outperforming the individual heuristic functions ( H 1 M k p : 6.621, H 2 M k p : 3.460).

The Holm test confirms that C M F M k p significantly outperforms all individual makespan-based functions (p-value < 10 − 25 in all cases).

The worst-performing function is H 1 M k p (ranking: 6.621), indicating that its contribution to multi-objective optimisation is weaker compared to other approaches.

These results indicate that integrating multiple heuristics into a cooperative fitness function enhances performance when optimising makespan in a multi-objective context.

Performance Analysis Across Problem Families: To further understand the behaviour of each fitness function across different problem families, we summarise the HV (median value) obtained by each method in Table 5.

The C M F M k p approach shows consistently strong and competitive performance across all problem families, often achieving the highest hypervolume values (in 4 out of 7 workflow problems) or remaining close to the best-performing heuristic ( H 2 M k p ) in the remaining 3 problems. Even in cases where it does not achieve the optimal result, the performance gap is marginal. The most notable deviation occurs in the srasearch problem, where C M F M k p falls 3.1% short of H 2 M k p , suggesting that while the cooperative integration of heuristics enhances robustness, certain workflow problem structures may still favour specific individual strategies.

Nevertheless, C M F M k p significantly outperforms both S t d F i t and H 1 M k p in all problems, reinforcing the notion that cooperative multi-fitness strategies have a distinct advantage over single-objective heuristics in multi-objective optimisation.

These results reinforce the earlier statistical findings, demonstrating that cooperative multi-fitness functions enhance makespan optimisation in multi-objective scheduling scenarios.

7.3.2. Evaluation of energy-oriented fitness functions

A similar experiment is conducted for fitness functions designed to optimise total energy:

S t d F i t (baseline).

H 1 T E and H 2 T E (heuristic functions for total energy optimisation).

C M F T E (a cooperative approach combining the previous three).

Key observations from Table 4:

C M F T E achieves a ranking of 3.558, outperforming both H 2 T E (4.5) and H 1 T E (5.196).

The Holm test rejects the null hypothesis for all individual heuristics, confirming that C M F T E significantly outperforms them ( p-value < 10 − 125 ).

S t d F i t performs the worst (ranking: 6.911), suggesting that although direct decoding allows for high genetic diversity without biasing the search, it lacks the adaptability needed for effective multi-objective optimisation, mainly due to the huge dimension of the search space.

These results confirm that, as with makespan, integrating multiple heuristics into a cooperative approach enhances performance in total energy optimisation as well, even in a multi-objective context.

Performance Analysis Across Problem Families: To provide further insight into the behaviour of each fitness function across different problem families, we summarise the hypervolume (median value) for each method in Table 6.

OPEN IN VIEWER

Table 6.

Median hypervolume obtained for energy-based fitness functions across different problem families. In bold the best result for each problem.

Problem	S t d F i t	H 1 T E	H 2 T E	C M F T E
1000genome	1%	22%	0%	19%
cycles	0.01%	2%	32%	27%
epigenomics	1%	7%	0%	7%
montage	0.26%	25%	24%	31%
seismology	2%	21%	20%	23%
soykb	0.35%	0%	37%	36%
srasearch	5%	38%	28%	38%

The C M F T E approach demonstrates strong and competitive performance across all problem families. In fact, it achieves the highest hypervolume value in 4 out of the 7 problems. Even in the problems where it does not obtain the maximum HV, the performance gap is marginal. The largest deviation occurs in the cycles problem, where C M F T E is only 5% behind H 2 T E , and in the 1000genome problem, where the gap is 3.1%.

Unlike makespan optimisation, where the performance of individual heuristics was relatively consistent, here we see that H 1 T E and H 2 T E tend to dominate specific problem domains. In particular, H 1 T E performs well on 1000genome, epigenomics, and soykb, while H 2 T E is the dominant heuristic in problems like cycles and srasearch. This suggests that these heuristics are more specialised and better suited to particular problem families, whereas C M F T E , with its cooperative multi-fitness approach, manages to perform competitively across the board.

In contrast, the S t d F i t function consistently underperforms in all problem families, highlighting the limitation of using a single fitness function for multi-objective optimisation in energy scheduling tasks. The cooperative multi-fitness strategy in C M F T E allows for a more nuanced exploration of the solution space, leading to superior performance in most cases.

These results again reinforce the earlier findings that combining multiple heuristics within a cooperative framework significantly improves performance, even when focusing solely on total energy optimisation.

Overall, the experiments demonstrate that CMF approaches outperform individual heuristic functions when optimising either makespan or total energy. The Friedman test rankings consistently place C M F M k p and C M F T E above their individual components, with statistically significant improvements confirmed by the Holm post hoc test.

This suggests that leveraging multiple heuristics in a cooperative manner enhances the search process in NSGA-II, leading to superior hypervolume values compared to using single-objective heuristics in isolation.

OPEN IN VIEWER

Figure 4.

Median hypervolume obtained for M O C M F and mono-objective C M F approaches across different problem families. The blue bar chart represents M O C M F performance, while the horizontal box plots correspond to S t d F i t (white), C M F M k p (orange), and C M F T E (green).

In the next section, we will evaluate whether combining both CMF approaches into a single multi-objective function (MOCMF) results in additional performance improvements, further boosting the quality of solutions across both objectives.

7.4. Efficiency of the multi-objective cooperative multi-fitness approach

Following the evaluation of the mono-objective CMF functions within the multi-objective context, the focus now shifts to the results obtained by the multi-objective MOCMF approach. In this configuration, each pair of heuristics — H 1 M k p and H 2 M k p , as well as H 1 T E and H 2 T E — collaborates with the S t d F i t function to generate two distinct schedules, with each focusing on optimising the specific objective for which the respective heuristic was designed. Consequently, the MOCMF approach has the potential to leverage the benefits of both makespan and total energy optimisations within a single cooperative framework.

The results of the statistical test are summarised in Table 4, which highlights the performance of MOCMF relative to other fitness functions, both simple and composite. As demonstrated in the table, MOCMF achieves the highest ranking (2.607), surpassing all other evaluated functions. For the sake of comparison, the mono-objective CMF functions achieved the following rankings: C M F M k p (3.147) and C M F T E (3.558). The statistical significance of these rankings is further validated by the Holm post hoc test, which rejects the null hypothesis for all individual heuristics, confirming that MOCMF significantly outperforms them ( p-value < 10 − 125 ). These results emphasise the capacity of MOCMF to effectively balance and optimise multiple objectives within the multi-objective scheduling context.

Performance Analysis Across Problem Families: Figure 4 presents the median hypervolume (HV) values obtained for MOCMF, in comparison with S t d F i t , CMF M k p , and CMF T E .

MOCMF achieves the highest HV in four out of the seven problem families: epigenomics, montage, and srasearch. In instances where MOCMF does not attain the maximum HV, the performance disparity remains marginal. Specifically, in the 1000genome problem, the HV of MOCMF (30%) is only 1 percentage point lower than the best result of C M F M k p . A similar outcome is observed in the seismology problem, where MOCMF is within 2 percentage points of the HV achieved by C M F M k p . In the soykb problem, MOCMF reaches 32%, which is 4 percentage points below the highest HV from C M F T E , yet it significantly outperforms C M F M k p by 22 percentage points.

These results highlight the ability of MOCMF to closely approximate the highest HV achieved by the most efficient mono-objective CMF approach for each problem. Even when it does not attain the absolute maximum, MOCMF consistently delivers competitive results, maintaining a minimal performance gap relative to the best-performing CMF variant. This demonstrates its robustness in effectively balancing both objectives across different problem families.

In order to provide a more comprehensive evaluation of the robustness and effectiveness of the MOCMF approach, a focus is directed towards the instances of each workflow family that present the greatest challenges. These instances are characterised by the highest number of tasks and scheduled on the maximum number of virtual machines scenario. The results, summarised in Figure 5, demonstrate the performance of MOCMF in comparison to the baseline S t d F i t and the mono-objective CMF approaches, C M F M k p and C M F T E .

OPEN IN VIEWER

Figure 5.

Median hypervolume results for the challenging instances of each workflow family using 16 hosts infrastructure. The blue bar chart represents M O C M F performance, while the horizontal box plots correspond to S t d F i t (white), C M F M k p (orange), and C M F T E (green).

Although MOCMF achieves the maximum HV in only two problems (1000genome and epigenomics), it demonstrates a strong capacity to remain close to the maximum HV in the other cases, with small gaps. In all but one of the remaining problems, the HV obtained by MOCMF is within a few percentage points of the highest value. This suggests that MOCMF is not only competitive but also exhibits significant robustness in the multi-objective optimisation process, making it a viable solution for various problem families.

7.5. Generalisation of MOCMF across other MOEAs

To evaluate the robustness and generality of the proposed MOCMF approach, we extended the experimental assessment to include four additional multi-objective evolutionary algorithms: SPEA2 and IBEA, both different genetic approaches, and multi-objective ant colony optimization algorithm (MOACO), and a particle swarm optimization algorithm (MOPSO). All algorithms were implemented using the JMetal v6 framework and configured with identical parameters (for SPEA2 and IBEA), the same evaluation model (DNC), and the cooperative decoding strategy employed in the NSGA-II experiments. The MOACO and MOPSO both use the parameters present in each original works. MOACO is based on ACO-HEFT, ¹⁹ with the exception that the construction of the ranking is performed randomly instead of using HEFT ranking. Nevertheless, the HEFT ranking remains relevant due to their inclusion in the makespan support functions. The MOPSO version used is the Speed-constrained Multi-objective PSO (SMPSO). ⁵⁴ Since the original algorithm operates exclusively on real-valued representations, an adaptation was necessary to support permutation-based encoding. To address this, we employed a Random-Key encoding, ⁵⁵ modelling the permutation mechanism following the approach described in MOPSO approach. ⁵⁶

The ranking results obtained for SPEA2, IBEA, MOACO, and SMPSO are presented in Tables 7 to 10, respectively. As in the NSGA-II case, each configuration includes the baseline decoding function ( S t d F i t ), the objective-specific heuristics, the mono-objective CMF variants, and the full MOCMF approach. Although the revised table omits statistical test columns for clarity, we note that the rankings presented are fully supported by statistical significance tests.

The results show that the relative performance ordering among fitness strategies remains consistent across all three algorithms. In both all algorithms, the MOCMF strategy consistently achieves the top average rankings across convergence-focused metrics (HV, IGD(+), GD, EP), followed by the mono-objective CMF variants. The baseline S t d F i t and individual heuristics rank significantly lower, as in the NSGA-II setting. These findings confirm that the advantages of cooperative multi-fitness evaluation extend beyond a specific MOEA implementation, reinforcing the portability and general applicability of the proposed method.

7.6. Scalability and computational load

This section analyses the computational demands of the proposed MOCMF approach and assesses its scalability in large-scale workflow scheduling scenarios. We begin by describing the procedural cost of MOCMF in terms of its decoding and evaluation mechanism, which differs from standard evolutionary algorithms due to the cooperative use of multiple heuristic decoders. Then, we present an empirical evaluation using the Cycles workflow family, demonstrating how execution time evolves as the number of tasks increases across several orders of magnitude.

OPEN IN VIEWER

Table 7.

Average ranking of evaluated fitness strategies using the SPEA2 algorithm across six performance metrics: Hypervolume (HV), inverted generational distance (IGD), inverted generational distance plus (IGD+), generational distance (GD), epsilon indicator (EP), and spread. Lower values indicate better performance.

	Rankings
Fitness Strategy	HV	IGD	IGD+	GD	EP	Spread
M O C M F	2.286	2.429	2.286	1.857	2.214	7.571
C M F T E	2.857	3.000	2.857	2.286	3.000	6.714
C M F M k p	3.571	3.714	3.000	2.714	3.786	6.714
H 1 T E	4.071	4.000	4.286	5.286	4.286	3.857
H 2 T E	4.571	5.000	5.000	5.429	4.571	2.571
H 2 M k p	4.786	4.000	4.714	4.714	3.857	3.143
H 1 M k p	6.857	6.571	6.571	6.571	6.857	1.714
S t d F i t	7.000	7.286	7.286	7.143	7.429	3.714

OPEN IN VIEWER

Table 8.

Average ranking of evaluated fitness strategies using the IBEA algorithm across six performance metrics: Hypervolume (HV), inverted generational distance (IGD), inverted generational distance plus (IGD+), generational distance (GD), epsilon indicator (EP), and spread. Lower values indicate better performance.

	Rankings
Fitness Strategy	HV	IGD	IGD+	GD	EP	Spread
M O C M F	2.161	2.321	2.179	2.571	1.857	2.5
C M F M k p	3.339	3.339	3.054	3.929	3.339	3.179
C M F T E	3.339	3.357	3.286	3.321	3.232	3.643
H 2 M k p	4.196	3.804	4.196	3.536	3.607	5.000
H 2 T E	4.482	4.464	4.393	4.357	4.679	5.250
H 1 T E	5.000	5.000	5.179	5.107	5.464	4.679
H 1 M k p	6.393	6.464	6.429	5.857	6.500	5.571
S t d F i t	7.089	7.250	7.286	7.321	7.321	6.179

OPEN IN VIEWER

Table 9.

Average ranking of evaluated fitness strategies using the MOACO algorithm across six performance metrics: Hypervolume (HV), inverted generational distance (IGD), inverted generational distance plus (IGD+), generational distance (GD), epsilon indicator (EP), and spread. Lower values indicate better performance.

	Rankings
Fitness Strategy	HV	IGD	IGD+	GD	EP	Spread
M O C M F	2.667	2.667	2.593	2.704	2.556	2.963
C M F M k p	3.222	3.259	3.148	3.481	3.204	3.519
C M F T E	3.407	2.926	2.926	2.926	2.926	2.926
H 2 M k p	3.593	3.111	3.593	3.333	3.389	3.444
H 2 T E	4.704	4.852	4.889	4.556	4.889	4.667
H 1 T E	4.852	4.926	4.593	4.704	4.815	4.481
H 1 M k p	6.778	6.926	6.926	6.889	6.852	6.296
S t d F i t	6.778	7.333	7.333	7.407	7.370	7.704

OPEN IN VIEWER

Table 10.

Average ranking of evaluated fitness strategies using the MOPSO algorithm across six performance metrics: Hypervolume (HV), inverted generational distance (IGD), inverted generational distance plus (IGD+), generational distance (GD), epsilon indicator (EP), and spread. Lower values indicate better performance.

	Rankings
Fitness Strategy	HV	IGD	IGD+	GD	EP	Spread
M O C M F	2.339	2.000	2.321	2.250	2.250	2.607
C M F T E	3.054	2.821	2.714	2.857	2.750	3.536
C M F M k p	3.661	3.250	3.500	3.250	3.429	3.036
H 2 M k p	4.143	3.786	3.786	3.643	3.857	3.286
H 2 T E	4.281	4.714	4.643	4.929	4.607	4.821
H 1 T E	4.750	5.286	4.857	4.786	4.964	5.107
S t d F i t	6.500	7.250	7.250	7.143	7.286	7.821
H 1 M k p	6.732	6.893	6.929	7.143	6.857	5.786

7.6.1. Procedural cost analysis of MOCMF

Unlike traditional multi-objective evolutionary algorithms that apply a single decoding strategy per chromosome, MOCMF introduces a cooperative decoding mechanism that invokes multiple heuristics—one standard decoder and a set of support heuristics associated with each objective.

Given a population of N offspring chromosomes and k optimisation objectives, each chromosome is decoded once using the standard decoder ( S t d F i t ), and additionally with every support heuristic associated with each objective. Let H i denote the number of support heuristics defined for objective i . The best resulting schedule for each objective is selected and used to recode the chromosome via Lamarckian inheritance. Since both the decoded plans and their fitness values are obtained during this process, no further evaluation is required after recoding.

Therefore, the total number of decoding and evaluation operations per generation is:

N ⋅ ( 1 + ∑ i = 1 k H i )

(14)

This cost grows linearly with the population size and with the total number of heuristic decoders used. In our implementation, all heuristics are lightweight and rule-based, ensuring that the added cost remains tractable and predictable. This section is followed by an empirical evaluation to confirm that the model maintains scalable execution across a wide range of workflow sizes.

7.6.2. Empirical scalability evaluation

To validate the practical scalability of the full MOCMF model, we conducted a dedicated experiment using workflow instances from the Cycles family available in the wfcommons ⁴⁹ repository. These workflows share structural characteristics but vary significantly in size, ranging from 67 to 6,543 tasks. Each instance was executed using the most demanding infrastructure setting in our study: a 16-host heterogeneous cloud configuration with two distinct VM types.

We applied the complete MOCMF-enhanced NSGA-II algorithm to each instance, incorporating both makespan-oriented and energy-oriented cooperative decoding mechanisms. The goal was to observe how total execution time evolves as the problem size increases.

Table 11 presents the results, including the number of tasks, total runtime, and average computation time per task. The latter metric provides a normalized view of computational cost per unit of workflow size.

OPEN IN VIEWER

Table 11.

Scalability of MOCMF evaluated on the cycles workflow family, under a 16-host heterogeneous configuration. The table reports the number of tasks per workflow, total execution time, and average time per task.

Instance size	Execution Time (s)	Seconds per Task
67	10.62	0.16
133	20.49	0.15
266	44.63	0.17
437	79.39	0.18
662	140.83	0.21
1091	242.17	0.22
1322	282.92	0.21
1983	461.74	0.23
2182	509.98	0.23
3273	770.54	0.24
4362	1051.01	0.24
6543	1799.26	0.27

These results confirm that the total execution time increases with workflow size, as expected, but the computation time per task remains remarkably stable. Across a two-order-of-magnitude increase in problem size, the per-task evaluation time grows modestly from 0.16 to 0.27 seconds.

This near-linear growth indicates that the evaluation strategy employed in MOCMF supports efficient scaling across a wide range of problem sizes. Furthermore, because each heuristic decoding is self-contained and independent, the approach lends itself naturally to parallelisation. A multicore implementation could distribute evaluation workloads across processing units, substantially reducing actual runtime and further reinforcing the model’s applicability to large-scale workflow scheduling.