Abstract: 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 transform the non-linear form to be linear. As a NP-hard problem, its search space increases exponentially with the growth of the problem size. For example, when the total number of resources is m, and the total number of tasks is n, the potential resource allocation strategies can be as many as 2mn, which results in a dimensional disaster.
Based on the integer programming model, we have proposed several algorithms to solve the problem, including the greedy algorithm, the branch-and-bound algorithm, and the genetic algorithm. The greedy algorithm selects the best scheme at each stage according to the greedy strategy to optimize the current objective function value. The genetic algorithm is a heuristic algorithm for searching the solution space. When the problem scale is large, although it cannot guarantee the optimal solution, the genetic algorithm can usually find a good feasible solution within a limited time. Each chromosome's encoding represents a potential subset of jobs, but it may not necessarily be a feasible subset. We use a feasibility set judgment algorithm to evaluate job subsets. The branch-and-bound algorithm continuously adjusts the upper and lower bounds of the objective function value by relaxing different constraints, eventually obtaining the optimal solution. In 0-1 integer programming or mixed integer programming problems, by relaxing the integer variables in the computational integer programming problem to real variables, a linear programming problem is typically obtained as the relaxation of the integer programming problem. By repeatedly constructing a node pruning process, the optimal solution can ultimately be obtained.
Extensive computational experiments are conducted to assess the performance of the three proposed algorithms. The results indicate that the branch-and-bound algorithm excels in providing superior solutions for problems involving a smaller number of jobs. Conversely, the genetic algorithm demonstrates satisfactory performance as the number of jobs increases. Future research directions could include enhancements to the heuristic algorithm and further exploration of resource allocation models.

Key words: resource allocation, job scheduling, CPS, branch-and-bound, genetic algorithm

摘要： 随着数字孪生、物联网等技术的快速发展,对于信息物理融合系统(Cyber-Physical System,CPS)的相关研究变得愈发重要。本文针对CPS中作业调度的特点,以获取最大作业收益为目标,基于多类资源探讨面向区间作业的CPS资源分配方法。作为一类新的资源分配问题,其相比以往研究的相关问题复杂度更高,本文区分收益与成本关系提出了两类子问题:VCC和VCN,并构建了整数规划模型。针对模型中存在的非线性约束条件,使用预处理算法将相关非线性约束条件进行转换,在此基础上应用贪婪算法、分支定界算法和遗传算法求解该VCC和VCN问题。实验通过设置大量算例验证了三种算法的有效性,并分析了作业到达率、作业规模等参数对三种算法的影响,对区间调度问题的研究提供了可参考的理论和方法。

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