💻 computer science

Dynamic Multi-Objective Optimization for Batch-wise Task Assignment and Resource Allocation in Mobile Edge Computing

This paper proposes the Location-Resource Coupled Dynamic NSGA-II (LRC-DNSGA-II), an algorithm featuring a specialized variation operator and a task-feature-matched response mechanism to effectively solve the dynamic bi-objective optimization problem of batch-wise task assignment and resource allocation in mobile edge computing.

Original authors: Yingying Sun, Zhiming Dong, Gongshu Wang

Published 2026-10-14

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Yingying Sun, Zhiming Dong, Gongshu Wang

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the modern world, our devices—from smartphones to factory sensors—are constantly generating a flood of data that needs immediate processing. Sending all this information to a distant cloud server is often too slow and consumes too much energy, creating a bottleneck for applications that require instant responses, like autonomous driving or real-time industrial monitoring. To solve this, engineers have turned to "mobile edge computing," a strategy that places small, powerful computers closer to the devices, right at the edge of the network. This proximity reduces the time it takes for data to travel and allows for faster decision-making. However, these edge systems operate in a chaotic environment. The number of tasks arriving changes every second, the wireless signals fluctuate due to interference or movement, and the available computing power shifts as other devices join or leave the network. Managing this requires a constant, split-second balancing act: deciding which tasks should be handled locally by the device itself and which should be sent to a nearby server, while simultaneously figuring out how much communication bandwidth and processing power to allocate to each job. If the system makes a poor choice, tasks get delayed, or batteries drain prematurely.

Researchers at Northeastern University in China have tackled this complex, shifting problem by developing a new method to optimize these decisions in real-time. They recognized that traditional approaches often treat these decisions as a static puzzle, solving for a single moment in time without accounting for how the system evolves. In reality, tasks arrive in waves, or "batches," and the conditions for the next wave are heavily influenced by how the previous wave was handled. Unfinished tasks from one moment carry over to the next, occupying resources and changing the landscape for new arrivals. To address this, the team created a sophisticated algorithm called LRC-DNSGA-II. This system is designed to handle two conflicting goals simultaneously: minimizing the time it takes to complete tasks and reducing the energy consumed by the devices. Instead of trying to find a single "perfect" answer, the algorithm searches for a set of balanced solutions, allowing the system to adapt as the environment changes.

The core innovation of this new method lies in how it handles the relationship between where a task is sent and how much power it gets. In many existing systems, the decision of where to send a task (the assignment) and the decision of how much resource to give it (the allocation) are treated somewhat separately. The researchers found that these two choices are deeply intertwined. If a task is moved from a local device to a remote server, the rules for how it shares resources change completely; the bandwidth and computing power it needs are no longer the same. The new algorithm respects this connection. When it considers changing the location of a task, it immediately resets the associated resource settings to match the new environment, rather than trying to force old settings onto a new situation. This ensures that the system never wastes time exploring impossible or inefficient combinations.

Furthermore, the researchers addressed the challenge of moving from one batch of tasks to the next. In a dynamic system, the tasks arriving in the next moment might be completely different from the ones just processed, making it difficult to simply copy over previous solutions. The team introduced a mechanism that looks at the specific characteristics of the new tasks—such as their size and complexity—and matches them with the most relevant historical decisions. This allows the system to "remember" useful strategies from the past without blindly applying them to unrelated new problems. By combining this smart memory with the location-aware adjustments, the algorithm can adapt quickly when the system conditions shift, such as when a sudden drop in wireless signal strength occurs or when a large batch of new data arrives.

To test their approach, the researchers simulated a mobile edge computing environment with fifty devices and five nearby servers over a period of six distinct time slots. They introduced realistic variations, including gradual changes in network conditions and a sudden, significant shift in the workload and available resources partway through the simulation. They compared their new method against four other established algorithms used for similar problems. The results showed that their approach consistently produced better outcomes. In terms of the quality of the solutions found, the new method achieved a significantly higher score in covering the range of possible trade-offs between speed and energy. It also found solutions that were much closer to the theoretical best possible performance than the other methods.

The study also examined how quickly the system could recover after a major change in conditions. When the environment shifted abruptly, all the algorithms experienced a temporary drop in performance, but the new method recovered much faster, stabilizing its decisions in fewer steps than its competitors. This rapid adaptation is crucial for real-world applications where delays can have immediate consequences. The researchers further tested the system with different numbers of incoming tasks, ranging from small batches to large surges of data. In every scenario, the new method maintained its advantage, suggesting that it scales well as the complexity of the network increases.

A detailed analysis of the algorithm's components revealed why it worked so well. The researchers found that the part of the system responsible for linking location decisions with resource settings was the primary driver of high-quality final results. This component ensured that the solutions found were robust and efficient. The part responsible for remembering and reusing past decisions played a more specific role: it helped the system get a head start when a new batch of tasks arrived, speeding up the initial adaptation phase. Without this memory, the system took longer to find good solutions after a change, but without the location-resource link, the final solutions were significantly worse.

The findings suggest that for mobile edge computing to be truly effective in dynamic, real-world settings, optimization strategies must treat task assignment and resource allocation as a single, coupled problem rather than separate steps. By acknowledging that changing where a task goes fundamentally changes the resources it needs, and by using smart matching to carry forward relevant experience, the system can maintain high performance even as conditions fluctuate. The researchers conclude that this approach offers a promising path forward for managing the growing complexity of connected devices, ensuring that the edge computing networks of the future can handle the unpredictable demands of modern applications with both speed and efficiency.

Technical Summary: Dynamic Multi-Objective Optimization for Batch-wise Task Assignment and Resource Allocation in Mobile Edge Computing

Problem Formulation
This paper addresses the challenge of task assignment and resource allocation in Mobile Edge Computing (MEC) systems where computation tasks arrive in successive batches. Unlike static formulations that assume a fixed task set, practical MEC environments involve time-varying conditions, including fluctuating task attributes, wireless channel states, and available computing resources. The authors formulate this as a constrained dynamic bi-objective optimization problem. The objectives are to minimize the average task completion delay and the average device energy consumption for newly arrived tasks in each decision slot. The problem is characterized by a tightly coupled mixed discrete–continuous structure: discrete decisions determine whether a task is executed locally or offloaded to a specific edge server, which in turn dictates the continuous allocation of communication bandwidth and computing resources. Furthermore, the problem includes stateful elements, where uncompleted tasks from previous slots carry over, occupying resources and affecting the feasible decision space for new tasks.

Methodology: LRC-DNSGA-II
To solve this dynamic mixed discrete–continuous problem, the authors propose the Location-Resource Coupled Dynamic NSGA-II (LRC-DNSGA-II). The algorithm integrates two primary mechanisms to handle the specific challenges of batch-wise arrivals and the coupling between assignment and allocation:

Task-Feature-Matched Dynamic Response (TFM): To address the issue that successive task batches may differ in size and attributes (rendering direct chromosome position reuse ineffective), TFM establishes correspondences between tasks in consecutive slots based on intrinsic task features (e.g., workload, data sizes) and state-dependent execution references. Matched tasks inherit location and resource-weight genes from their historical counterparts, while unmatched tasks are initialized randomly. This mechanism facilitates the transfer of relevant historical decision information across slots.
Location-Resource Coupled Variation (LRCV): This operator addresses the dependency between discrete assignment and continuous resource allocation. When a mutation changes a task's execution location, the associated resource-sharing context changes. LRCV restricts location mutations to accessible execution sites and, crucially, resets the associated resource-weight genes (bandwidth and computing weights) to median values of the new location group whenever a location change occurs. This ensures consistency between the discrete assignment and the continuous resource variables.

The algorithm operates in a slot-based manner. At the beginning of each slot, it observes the system state, constructs a task-feature matrix, and initializes the population using TFM (for $t > 1$ ). It then performs within-slot evolution using LRCV for crossover and mutation, followed by standard NSGA-II environmental selection. A representative solution is selected from the final Pareto front for deployment, and the system state is updated based on remaining workloads.

Key Contributions
The paper makes three main contributions:

Problem Formulation: It formulates batch-wise task assignment and resource allocation as a constrained dynamic bi-objective optimization problem that explicitly captures successive task arrivals, time-varying resources, location-dependent resource sharing, and the carry-over impact of unfinished tasks.
Algorithm Development: It develops LRC-DNSGA-II, featuring the Location-Resource Coupled Variation operator to maintain consistency between assignment and allocation decisions, and a task-feature-matched dynamic response mechanism to adapt to changing task sets across slots.
Empirical Validation: Through extensive experiments, the study demonstrates the algorithm's superiority over representative baselines (DNSGA-II, DMOEA/D-COPMEC, DMOPSO, and TL-MOEA) in terms of Hypervolume (HV) and Inverted Generational Distance (IGD).

Experimental Results
The proposed method was evaluated in a simulated dynamic MEC environment with 50 end devices and 5 edge servers over six decision slots, including a scenario with significant joint changes in task loads and system resources.

Performance: LRC-DNSGA-II consistently achieved the highest mean HV and lowest mean IGD across all decision slots compared to the four comparison methods. The improvements ranged from 5.33% to 30.73% in HV and 22.40% to 64.57% in IGD.
Adaptation: Evolutionary behavior analysis showed that LRC-DNSGA-II recovered more quickly from environmental changes (slot transitions) and maintained superior solution quality throughout the evolutionary process.
Scalability: The performance advantage was maintained as the number of newly arrived tasks increased from 50 to 90 per slot, with only a marginal increase in runtime (approx. 12–20% higher than the baseline DNSGA-II).
Ablation Studies:
- Removing LRCV resulted in a significant degradation in final approximation quality (4.25% lower HV, 14.24% higher IGD), indicating that coupled variation is the primary driver of solution quality.
- Removing TFM had a limited effect on final solution quality but significantly impacted early-stage adaptation, confirming its role in accelerating convergence after batch transitions.

Significance and Claims
The paper claims that the proposed approach effectively addresses the dual challenges of batch-wise task variability and the tight coupling between discrete assignment and continuous resource allocation in dynamic MEC. By distinguishing the roles of its two core components, the authors demonstrate that effective dynamic optimization in this domain requires both task-relevant cross-slot information transfer (to handle changing task sets) and location-aware coordination (to handle the mixed discrete–continuous decision space). The work provides a robust framework for jointly optimizing delay and energy in time-varying edge computing environments, outperforming existing dynamic multi-objective methods that do not explicitly model the location-resource coupling or the specific nature of batch-wise task arrivals.

More like this