CPS中面向区间任务的多类资源分配方法  

Interval Job Oriented Multi-types of Resources Allocation Problems in Cyber-Physical Systems

作　　者：周浩浩 马武彬[1] 吴亚辉[1] 邓苏[1] ZHOU Haohao;MA Wubin;WU Yahui;DENG Su(National Key Laboratory of Information Systems Engineering,National University of Defense Technology,Changsha 410072,China)

机构地区：[1]国防科技大学信息系统工程全国重点实验室,湖南长沙410072

出　　处：《运筹与管理》2024年第9期106-112,共7页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(61401482);中国博士后科学基金项目(2019M664033)。

摘　　要：随着数字孪生、物联网等技术的快速发展,对于信息物理融合系统(Cyber-Physical System,CPS)的相关研究变得愈发重要。本文针对CPS中作业调度的特点,以获取最大作业收益为目标,基于多类资源探讨面向区间作业的CPS资源分配方法。作为一类新的资源分配问题,其相比以往研究的相关问题复杂度更高,本文区分收益与成本关系提出了两类子问题:VCC和VCN,并构建了整数规划模型。针对模型中存在的非线性约束条件,使用预处理算法将相关非线性约束条件进行转换,在此基础上应用贪婪算法、分支定界算法和遗传算法求解该VCC和VCN问题。实验通过设置大量算例验证了三种算法的有效性,并分析了作业到达率、作业规模等参数对三种算法的影响,对区间调度问题的研究提供了可参考的理论和方法。With the rapid development of technologies such as digital twins and the Internet of Things(IoT),research on Cyber-Physical Systems(CPS)has become increasingly important.This paper focuses on the characteristics of job scheduling in CPS,aiming to maximize job value.Based on multiple types of resources,we explore resource allocation methods for interval jobs in CPS.As a new type of resource allocation problem,it is more complex than previous problems.In this paper,two subclasses of problems,VCC(Value-Cost Correlated)and VCN(Value-Cost Non-correlated)are distinguished based on the relationship between gains and costs,and integer programming models are constructed.To address the nonlinear constraints within these models,a preprocessing algorithm is used to transform the relevant nonlinear constraints.On this basis,greedy algorithms,branch-and-bound algorithms,and genetic algorithms are applied to solve the VCC and VCN problems.The experiments with a large number of test cases validate the effectiveness of the three algorithms and with the experiments we analyze the impact of parameters such as job arrival rates and job sizes on the algorithms,providing theoretical and methodological references for research on interval scheduling problems.As digital twin and Internet of Things(IoT)technologies advance,the boundaries between the information domain and the physical domain are becoming increasingly blurred,making the role of CPS even more critical.In CPS,the number of resources is typically limited,and when the volume of jobs exceeds the system’s capacity,it will become necessary to select from the set of jobs.Each job has a certain value,which in commercial applications often translates into economic value,i.e.,the price of the job.Additionally,considering cost-effectiveness,the economic benefits generated by allocating the same resources to different jobs can vary.Interval jobs are modeled in set form under both two situations,which is non-linear when processing.We design a feasible set judgment algorithm to transfo

关 键 词：资源分配 作业调度 CPS 分支定界 遗传算法 

分 类 号：TB114.1[理学—运筹学与控制论]