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

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