# Generating Datasets for Real-Time Scheduling on 5G New Radio
## 5 Formulation of the SMT Problem
### Improvement
The subsequent packets contain all packets in \(V^{m^{\prime}-1},\ldots,V^{1}\), whose weighted objective is \(\sum\limits_{\forall m\in[1,m^{\prime})}{(w^{m}\times|V^{m}|)}\), and the packets after \(k\) in \(V^{m^{\prime}}\), whose weighted objective is \(w^{m^{\prime}}\times(|V|-k-\sum\limits_{\forall m\in[1,m^{\prime})}{|V^{m}|)}\). In addition, the weight of the packet that might be placed is \(w^{\frac{L\times P-\sum\limits_{\forall m\in[1,m^{\prime}]}{(w^{m}_{j}\times 4 )}}{4}}\). Therefore, \(B\) is the sum of the first two parts, and then minus a placeable packet. Heuristic algorithms can be used to solve the 5G NR scheduling problem. Since the solution of SMT must be better than or equal to those of heuristic algorithms, the solutions of heuristic algorithms can be used as the upper bound \(C\) of \(A\). Our problem is the same as that addressed by the SAC algorithm [9]. Although SAC can be used to determine \(C\), it is only suitable for scheduling problems with long times and narrow bandwidth. Therefore, we propose a more applicable algorithm (as shown in Algorithm 1). The 5G NR scheduling problem is a three-dimensional bin packing problem for irregular objects. The placement space of packets is time-frequency two-dimensional space, whereas the cover and confriction relationship between packets is three-dimensional. Therefore, our heuristic algorithm learns from the classical bottom-left bin packing algorithm [25] and then considers whether the three-dimensional relationship between packets satisfies the scheduling constraints. For each object, the classical bottom-left algorithm selects the bottommost leftmost position that can be placed without confriction. The two-dimensional space of the bottom-left algorithm is placed from bottom to top, whereas our scheduling method should be placed on the left first because packet models occupy resources from left to right. Thus, we adopt a left-top strategy. For each packet in \(V\), the left-top strategy searches for available places in \(L\times P\) first in the leftmost column from top to bottom, then in the second column from top to bottom, and so on. The first place where the packet does not conflict with the other packets in \(L\times P\times M\) is its final place. Hence, the time complexity of the simple strategy is \(O(|V|LPLPM)=O(n^{6})\). In order to reduce the solution time, our proposed heuristic algorithm simplifies the search process and reduces the time complexity to \(O(LP+|V|LPM)=O(n^{4})\). The pseudocode of our algorithm is shown in Algorithm 1. Figure 5: Example of the lower bound \(B\). ```
0:\(V\), \(L\), \(P\)
0:\(obj\) or FAIL
1:\(obj=0\); \(x=0\), \(y=L-1\); \(\forall x,y,z,S[x][y][z]=0\);
2: sort the packets of \(V\) in descending order of the number of transmissions, and store them in \(V^{\prime\prime}\) in order;
3:for\(i=1\) to \([V^{\prime\prime}]\)do
4:if\(LT(v_{i}^{\prime\prime},S,x,y,0)\) returns \((x_{i}^{\prime\prime},y_{i}^{\prime\prime})\)then
5:\((x_{i}^{\prime},y_{i}^{\prime\prime})\) is the place of \(v_{i}^{\prime\prime}\), then update \(S[\,]\,[\,]\,[\,]\);
6:\(V^{\prime\prime}=V^{\prime\prime}-\{v_{i}^{\prime\prime}\}\);
7:\((y_{i}^{\prime\prime}==0)? (x=x_{i}^{\prime\prime}+1,y=L-1):(x=x_{i}^{\prime \prime},y=y_{i}^{\prime\prime}-1)\);
8:if\(V^{\prime\prime}\) is an empty set then
9:return\(0\);
10:else
11:\(x=0\);\(y=L-1\);
12:for each \(v_{i}^{\prime\prime}\) in \(V^{\prime\prime}\)do
13:if\(LT(v_{i}^{\prime\prime},S,x,y,1)\) returns \((x_{i}^{\prime\prime},y_{i}^{\prime\prime})\)then
14:\((x_{i}^{\prime\prime},y_{i}^{\prime\prime})\) is the place of \(v_{i}^{\prime\prime}\), then update \(S[\,]\,[\,]\,[\,]\);
15:\((y_{i}^{\prime\prime}==0)? (x=x_{i}^{\prime\prime}+1,y=L-1):(x=x_{i}^{\prime \prime},y=y_{i}^{\prime\prime}-1)\);
16:\(obj=obj+w^{\prime\prime}\);
17:else
18:return FAIL;
19:return\(obj\);
```  
**Algorithm 1** Packet placement algorithm.