Joint computation offloading and parallel scheduling to maximize delay-guarantee in cooperative MEC systems

The growing development of the Internet of Things(IoT)is accelerating the emergence and growth of new IoT services and applications,which will result in massive amounts of data being generated,transmitted and pro-cessed in wireless communication networks.Mobile Edge Computing(MEC)is a desired paradigm to timely process the data from IoT for value maximization.In MEC,a number of computing-capable devices are deployed at the network edge near data sources to support edge computing,such that the long network transmission delay in cloud computing paradigm could be avoided.Since an edge device might not always have sufficient resources to process the massive amount of data,computation offloading is significantly important considering the coop-eration among edge devices.However,the dynamic traffic characteristics and heterogeneous computing capa-bilities of edge devices challenge the offloading.In addition,different scheduling schemes might provide different computation delays to the offloaded tasks.Thus,offloading in mobile nodes and scheduling in the MEC server are coupled to determine service delay.This paper seeks to guarantee low delay for computation intensive applica-tions by jointly optimizing the offloading and scheduling in such an MEC system.We propose a Delay-Greedy Computation Offloading(DGCO)algorithm to make offloading decisions for new tasks in distributed computing-enabled mobile devices.A Reinforcement Learning-based Parallel Scheduling(RLPS)algorithm is further designed to schedule offloaded tasks in the multi-core MEC server.With an offloading delay broadcast mechanism,the DGCO and RLPS cooperate to achieve the goal of delay-guarantee-ratio maximization.Finally,the simulation results show that our proposal can bound the end-to-end delay of various tasks.Even under slightly heavy task load,the delay-guarantee-ratio given by DGCO-RLPS can still approximate 95%,while that given by benchmarked algorithms is reduced to intolerable value.The simulation results are demonstrated the effective-ness of DGCO-RLPS for delay guarantee in MEC.

Improved STNModels and Heuristic Rules for Cooperative Scheduling in Automated Container Terminals

Improving the cooperative scheduling efficiency of equipment is the key for automated container terminals to copewith the development trend of large-scale ships. In order to improve the solution efficiency of the existing spacetimenetwork (STN) model for the cooperative scheduling problem of yard cranes (YCs) and automated guidedvehicles (AGVs) and extend its application scenarios, two improved STN models are proposed. The flow balanceconstraints in the original model are decomposed, and the trajectory constraints of YCs and AGVs are added toacquire the model STN_A. The coupling constraint in STN_A is updated, and buffer constraints are added toSTN_A so that themodel STN_B is built.As the size of the problem increases, the solution speed of CPLEX becomesthe bottleneck. So a heuristic method containing three groups of heuristic rules is designed to obtain a near-optimalsolution quickly. Experimental results showthat the computation time of STN_A is shortened by 49.47% on averageand the gap is reduced by 1.69% on average compared with the original model. The gap between the solution ofthe heuristic rules and the solution of CPLEX is less than 3.50%, and the solution time of the heuristic rules is onaverage 99.85% less than the solution time of CPLEX. Compared with STN_A, the computation time for solvingSTN_B increases by 58.93% on average.

Cooperative-Guided Ant Colony Optimization with Knowledge Learning for Job Shop Scheduling Problem

With the advancement of the manufacturing industry,the investigation of the shop floor scheduling problem has gained increasing importance.The Job shop Scheduling Problem(JSP),as a fundamental scheduling problem,holds considerable theoretical research value.However,finding a satisfactory solution within a given time is difficult due to the NP-hard nature of the JSP.A co-operative-guided ant colony optimization algorithm with knowledge learning(namely KLCACO)is proposed to address this difficulty.This algorithm integrates a data-based swarm intelligence optimization algorithm with model-based JSP schedule knowledge.A solution construction scheme based on scheduling knowledge learning is proposed for KLCACO.The problem model and algorithm data are fused by merging scheduling and planning knowledge with individual scheme construction to enhance the quality of the generated individual solutions.A pheromone guidance mechanism,which is based on a collaborative machine strategy,is used to simplify information learning and the problem space by collaborating with different machine processing orders.Additionally,the KLCACO algorithm utilizes the classical neighborhood structure to optimize the solution,expanding the search space of the algorithm and accelerating its convergence.The KLCACO algorithm is compared with other highperformance intelligent optimization algorithms on four public benchmark datasets,comprising 48 benchmark test cases in total.The effectiveness of the proposed algorithm in addressing JSPs is validated,demonstrating the feasibility of the KLCACO algorithm for knowledge and data fusion in complex combinatorial optimization problems.

Competitive and Cooperative-Based Strength Pareto Evolutionary Algorithm for Green Distributed Heterogeneous Flow Shop Scheduling

This work aims to resolve the distributed heterogeneous permutation flow shop scheduling problem(DHPFSP)with minimizing makespan and total energy consumption(TEC).To solve this NP-hard problem,this work proposed a competitive and cooperative-based strength Pareto evolutionary algorithm(CCSPEA)which contains the following features:1)An initialization based on three heuristic rules is developed to generate a population with great diversity and convergence.2)A comprehensive metric combining convergence and diversity metrics is used to better represent the heuristic information of a solution.3)A competitive selection is designed which divides the population into a winner and a loser swarms based on the comprehensive metric.4)A cooperative evolutionary schema is proposed for winner and loser swarms to accelerate the convergence of global search.5)Five local search strategies based on problem knowledge are designed to improve convergence.6)Aproblem-based energy-saving strategy is presented to reduce TEC.Finally,to evaluate the performance of CCSPEA,it is compared to four state-of-art and run on 22 instances based on the Taillard benchmark.The numerical experiment results demonstrate that 1)the proposed comprehensive metric can efficiently represent the heuristic information of each solution to help the later step divide the population.2)The global search based on the competitive and cooperative schema can accelerate loser solutions convergence and further improve the winner’s exploration.3)The problembased initialization,local search,and energy-saving strategies can efficiently reduce the makespan and TEC.4)The proposed CCSPEA is superior to the state-of-art for solving DHPFSP.

Optimization Task Scheduling Using Cooperation Search Algorithm for Heterogeneous Cloud Computing Systems

Cloud computing has taken over the high-performance distributed computing area,and it currently provides on-demand services and resource polling over the web.As a result of constantly changing user service demand,the task scheduling problem has emerged as a critical analytical topic in cloud computing.The primary goal of scheduling tasks is to distribute tasks to available processors to construct the shortest possible schedule without breaching precedence restrictions.Assignments and schedules of tasks substantially influence system operation in a heterogeneous multiprocessor system.The diverse processes inside the heuristic-based task scheduling method will result in varying makespan in the heterogeneous computing system.As a result,an intelligent scheduling algorithm should efficiently determine the priority of every subtask based on the resources necessary to lower the makespan.This research introduced a novel efficient scheduling task method in cloud computing systems based on the cooperation search algorithm to tackle an essential task and schedule a heterogeneous cloud computing problem.The basic idea of thismethod is to use the advantages of meta-heuristic algorithms to get the optimal solution.We assess our algorithm’s performance by running it through three scenarios with varying numbers of tasks.The findings demonstrate that the suggested technique beats existingmethods NewGenetic Algorithm(NGA),Genetic Algorithm(GA),Whale Optimization Algorithm(WOA),Gravitational Search Algorithm(GSA),and Hybrid Heuristic and Genetic(HHG)by 7.9%,2.1%,8.8%,7.7%,3.4%respectively according to makespan.

No-cooperative games for multiple emergency locations in resource scheduling

When an emergency happens, the scheduling of relief resources to multiple emergency locations is a realistic and intricate problem, especially when the available resources are limited. A non-cooperative games model and an algorithm for scheduling of relief resources are presented. In the model, the players correspond to the multiple emergency locations, strategies correspond to all resources scheduling and the payoff of each emergency location corresponds to the reciprocal of its scheduling cost. Thus, the optimal results are determined by the Nash equilibrium point of this game. Then the iterative algorithm is introduced to seek the Nash equilibrium point. Simulation and analysis are given to demonstrate the feasibility and availability of the model.

MANUFACTURING SYSTEM SCHEDULING BASED ON MULTI-AGENT COOPERATION GAME

Aiming at the flexible manufacturing system with multi-machining and multi-assembly equipment, a new scheduling algorithm is proposed to decompose the assembly structure of the products, thus obtaining simple scheduling problems and forming the cOrrespOnding agents. Then, the importance and the restriction of each agent are cOnsidered, to obtain an order of simple scheduling problems based on the cooperation game theory. With this order, the scheduling of sub-questions is implemented in term of rules, and the almost optimal scheduling results for meeting the restriction can be obtained. Experimental results verify the effectiveness of the proposed scheduling algorithm.

Improved Fruit Fly Optimization Algorithm for Solving Lot-Streaming Flow-Shop Scheduling Problem

An improved fruit fly optimization algorithm( iFOA) is proposed for solving the lot-streaming flow-shop scheduling problem( LSFSP) with equal-size sub-lots. In the proposed iFOA,a solution is encoded as two vectors to determine the splitting of jobs and the sequence of the sub-lots simultaneously. Based on the encoding scheme,three kinds of neighborhoods are developed for generating new solutions. To well balance the exploitation and exploration,two main search procedures are designed within the evolutionary search framework of the iFOA,including the neighborhood-based search( smell-vision-based search) and the global cooperation-based search. Finally,numerical testing results are provided,and the comparisons demonstrate the effectiveness of the proposed iFOA for solving the LSFSP.

Dynamic Resource Scheduling in Emergency Environment

Nowadays,emergency accidents could happen at any time.The accidents occur unpredictably and the accidents requirements are diversely.The accidents happen in a dynamic environment and the resource should be cooperative to solve the accidents.Most methods are focusing on minimizing the casualties and property losses in a static environment.However,they are lack in considering the dynamic and unpredictable event handling.In this paper,we propose a representative environmental model in representation of emergency and dynamic resource allocation model,and an adaptive mathematical model based on Genetic Algorithm(GA)to generate an optimal set of solution domain.The experimental results show that the proposed algorithm can get a set of better candidate solutions.

Cooperative Game Theory Based Coordinated Scheduling of Two-Machine Flow-Shop and Transportation

A cooperative game theoretical approach is taken to production and transportation coordinated scheduling problems of two-machine flow-shop(TFS-PTCS problems)with an interstage transporter.The authors assume that there is an initial scheduling order for processing jobs on the machines.The cooperative sequencing game models associated with TFS-PTCS problems are established with jobs as players and the maximal cost savings of a coalition as its value.The properties of cooperative games under two different types of admissible rearrangements are analysed.For TFS-PTCS problems with identical processing time,it is proved that,the corresponding games areσ_(0)-component additive and convex under one admissible rearrangement.The Shapley value gives a core allocation,and is provided in a computable form.Under the other admissible rearrangement,the games neither need to beσ_(0)-component additive nor convex,and an allocation rule of modified Shapley value is designed.The properties of the cooperative games are analysed by a counterexample for general problems.

考虑多重不确定性与电碳耦合交易的多微网合作博弈优化调度

双碳背景下,构建低碳运行的能源系统是实现“双碳”目标的重要方向与实施路径。为了促进多微网系统内部能源的本地消纳以及低碳经济运行,该文对不确定性环境下多微网系统的合作运行及电碳耦合交易展开研究。首先,对于每个微网,构建了电转气碳捕集系统相耦合的热电联产运行模式,基于地方碳交易市场和阶梯碳交易机制,提出了多能源微网的低碳运行模型;其次,考虑到新能源发电和电力市场电价都存在不确定性的实际情况,采用机会约束和鲁棒优化的方法,以降低不确定性影响;再次,基于纳什谈判理论,建立了多个微网电碳耦合的合作博弈模型,各微网主体可同时参与到上级能源市场和地方能源市场中进行电能和碳排放配额的交易;最后,将非凸的合作博弈问题分解为两个线性可求解的子问题,进一步采用交替方向乘子法对问题进行求解。通过算例验证,该文所提方法可以有效提升各微网经济效益并减少碳排放。

基于储能和水电调节的跨区风光水联合优化调度策略

针对大规模新能源经特高压直流通道跨区并网消纳,在送端采用储能调节满足直流通道直线化功率传输等约束的同时,如何减小风光入网扰动度问题;在受端采用水电调节满足风光水跟踪电网负荷变化趋势,如何解决水电调节的利益受损问题,构建了风光水跨区域联合运行的三阶段调度模型.首先,在送端基于储能调节,构建了考虑受端电网净负荷变化趋势的风光功率直线化分段调节多目标优化模型;其次,在受端基于梯级水电调节,实现风光水联合功率跟踪电网负荷变化,构建受端电网与风光水联盟主从博弈模型,优化电网电价和联盟售电计划;最后,构建了基于纳什谈判的联盟利润分配模型,实现合作后各成员利润较合作前得到提升,维系联盟合作机制的稳定.仿真算例结果表明,采用本文方法可有效提升调节资源利用效率,保证水电调节利益,促进新能源消纳.

计及碳配额的电动公交车⁃配电网协同优化调度策略

考虑个人碳交易机制在电动公交车优化调度中的应用,提出一种基于动态碳价格的碳配额激励机制,电动公交车用户可以通过出售碳配额获取一定的收益。首先,计及路况对电动公交车运行时间产生的影响,根据工作日与休息日交通指数对电动公交车进站时间进行修正,构建电动公交车工作日与休息日充电负荷模型;然后,将基于动态碳价格的碳配额激励机制运用于电动公交车与新能源协同调度策略,构建综合考虑用户与电网利益的多目标函数,并运用鲸鱼算法对目标函数进行求解;最后,基于经济指标和性能指标,对固定碳价格、动态碳价格两种激励机制进行对比分析,通过算例验证了基于动态碳价格的碳配额激励机制的电动公交车与新能源协同调度策略的优越性。

低碳综合能源系统研究框架与关键问题研究综述

低碳综合能源系统是融合多种低碳技术和措施、集成灵活性资源、促进清洁能源消纳、降低碳排放的多能源系统,是实现“双碳”目标的物理载体。首先,从能源转型的宏观战略、物理载体和低碳技术角度论证了低碳综合能源系统是能源转型的有效路径,归纳了低碳综合能源系统的定义与特征内涵;然后,构建了低碳综合能源系统的研究框架,从源-网-荷-储及碳捕集等环节挖掘了低碳综合能源系统的减排潜力;为了充分发挥低碳综合能源系统的低碳优势,从协同规划与优化调度、市场机制等角度提炼了低碳综合能源系统的几个关键问题;最后,聚焦提炼的协同优化关键问题,从研究现状、面临问题和研究展望等方面进行了阐述,以期为能源系统的低碳发展提供参考。

结合遗传算子的并行萤火虫算法及在车间调度中的应用

论文提出了一种结合遗传算子的并行萤火虫算法,该算法借鉴了萤火虫闪烁移动的思想,对两个种群进行同步并行迭代求解,以提升算法的求解速度和质量;在其中一个种群中引入多尺度协同变异算子,利用不同大小方差的自适应高斯变异机制使整个种群以尽量分散的变异尺度来对解空间进行更详尽的探索,从而使整个种群进行有效变异。函数优化结果表明了该算法的有效性,该算法用于求解以最小化最大完工时间为优化目标的流水车间调度问题,实验结果表明,较传统的单一算法而言,结合遗传算子的并行萤火虫算法在求解车间调度问题方面具有更好的性能。

基于全局向局部运行空间投影的多级调度协同模式

随着电力市场改革的推进,华东区域各省级市场均已进入试运行阶段,为统筹兼顾现货市场平稳运营与区域电网安全运行,迫切需要研究更高效的网省协同运行机制。首先,分析了现货市场环境下网省调度协同模式的挑战与改进思路。然后,构建了区域电网调度可行域与省市调度可行域模型,提出可行域模型的降维与线性化处理方法。在此基础上,提出了基于调度可行域的网省协同优化运行机制,重点对网省两级协同运行的业务流程、省市可行域的计算方法进行了探讨。最后,通过区域电网的算例分析,验证了调度可行域模型与两级市场协同运行机制的有效性。

基于深度强化学习的收割机省内协同调度优化策略

针对目前多机多地块间调度作业存在效率低、成本高等问题,该研究构建了以收割机地块间转移成本最小为目标的协同调度模型,设计了基于深度强化学习的收割机协同调度优化算法(inter-regional collaborative optimization scheduling algorithm based on deep reinforcement learning,DRL-ICOSA)。首先分析收割机调度作业的马尔可夫决策过程,构建基于注意力机制的策略网络和价值网络,在随机采样策略中引入动态高斯噪声,以避免训练初期陷入局部最优,同时提高网络模型的鲁棒性;接着采用近端策略优化算法(proximal policy optimization,PPO)训练网络模型;最后利用测试集验证DRL-ICOSA算法,得到收割机优化调度方案。基于有效作业时长40和24 h、农机调度中心位于作业区域中心和区域边缘的4种组合作业场景下,采用DRL-ICOSA算法、遗传算法(genetic algorithm,GA)、粒子群算法(particle swarm optimization,PSO)和模拟退火算法(simulated annealing,SA)计算调度策略并进行对比分析。试验结果表明:当调度中心位于区域中心或边缘时,有效作业时长为40 h,DRL-ICOSA算法相较于GA、PSO和SA算法,平均调度成本降幅不少于13.9%;有效作业时长为24 h,平均调度成本降幅不少于11.5%。当作业时长为40或24 h时,调度中心位于区域中心,DRL-ICOSA算法相较于GA、PSO和SA算法,平均调度成本降幅不少于12.3%;调度中心位于区域边缘时,DRL-ICOSA算法相较于GA、PSO和SA算法,平均调度降幅不低于11.5%。因此,有效作业时长为40或24 h、调度中心位于区域中心或边缘时,相比其他3种算法,DRL-ICOSA算法均能计算得到最低的调度成本。这一研究结果可为收割机省内协同作业提供科学合理的调度方案。

基于深度强化学习的办公流程任务分配优化

在办公平台中存在异构流程任务大量并行的情况,不仅需要任务执行者具有较强的能力,也对协同调度系统的性能提出了要求。采用强化学习(RL)算法,结合协作配合度、松弛度等定量分析,并基于马尔可夫博弈理论提出多智能体博弈模型,实现以总体流程配合度和最大完工时间为优化目标的优化调度系统,提高了总体执行效率。以真实的业务系统流程作为实验场景,在相同的优化目标下,对比D3QN等3种深度强化学习(DRL)算法和基于蚁群的元启发式算法,验证了所提方法的有效性。

基于多时间尺度协同的大规模原油调度进化算法

针对原油调度过程存在的资源规模庞大、约束条件复杂、多时间尺度决策衔接困难等问题,提出一种基于多时间尺度协同的进化算法(MTCEA)。首先,根据炼油企业的规模结构和实际需求,建立了一种大规模多时间尺度原油调度优化模型,该模型由面向资源的中长期调度模型和面向操作的短期调度模型构成,通过引入原油资源动态分组策略,实现原油资源的合理配置,以满足不同的调度规模、多时间尺度的特征和精细化生产的要求;其次,为促进不同时间尺度调度决策的融合衔接,设计基于多时间尺度协同的进化算法,并针对不同时间尺度调度模型中的连续决策变量构造子问题进行求解,以实现不同时间尺度调度决策之间的协同优化;最后,在3个实际工业案例进行了算法性能验证。结果表明,与3种具有代表性的大规模进化优化算法(即竞争性粒子群优化算法(CSO)、基于多轨迹搜索的自适应差分进化算法(SaDE-MMTS)和基于混合模型的进化策略(MMES))以及3种高性能混合整数非线性规划(MINLP)数学求解器(即ANTIGONE(Algorithms for coNTinuous/Integer Global Optimization of Nonlinear Equations)、SCIP(Solving Constraint Integer Programs)和SHOT(Supporting Hyperplane Optimization Toolkit))相比,MTCEA的求解最优性指标和稳定性指标分别提高了30%和25%以上。这些显著的性能提升验证了MTCEA在大规模多时间尺度原油调度决策中的实际应用价值和优势。

基于集装箱作业标记的U型堆场分类协同调度

为优化U型堆场作业因集装箱分类不合理造成调度混乱的问题,提出分类协同调度过程,以不同任务协同作业、各任务高效作业的过程为约束条件建立分类协同调度模型。提出集装箱分类原则和集装箱多重堆存原则,在堆存选位时基于集装箱作业标记进行加权计算构成惩罚机制,设计了分类协同启发式算法求解模型。实验表明:基于惩罚机制的分类协同启发式算法所采用的策略更优,减少作业过程中设备相互等待的时长,并且随着实验规模的增加等待时长占比低,进而提高U型码头整体作业效率。