# Connected and Autonomous Vehicle Scheduling Problems: Some Models and Algorithms
## 2 A Road with Two Lanes and One Lane Closure
For each job \(i_{k}\) and a state \((f^{k-1},C_{max}^{k-1},pos^{k-1})\), we compute  
of the considered objective function. Moreover, let \(pos_{k}\in\{0,1,\ldots,n_{1},n_{1}+1\}\), \(k=1,\ldots,n\), be the position of job \(i_{k}\in N_{2}\) in the job sequence. This means that job \(j_{pos_{k}}\) is processed before job \(i_{k}\) and job \(j_{pos_{k}+1}\) is processed after it, where \(j_{0}\) means that job \(i_{k}\) is processed before job \(j_{1}\) and \(j_{n_{1}+1}\) means hat job \(i_{k}\) is processed after job \(j_{n_{1}}\). Let \(f^{\prime}\) be the objective function value for the job sub-sequence \((\pi_{1},i_{k})\). Next, we prove the following Property (*). Property (*): At each stage \(k\) of Algorithm 1, for each job \(i_{k}\) the state \((f_{k},C_{i_{k}},pos_{k})\) and the corresponding partial job sequence \((\pi^{k},i_{k})\) will be considered, where \(C_{i_{k}}(\pi^{*})=C_{i_{k}}\) and \(f^{\prime}=f_{k}\). For stage 1, Property (*) holds since we consider and save in the set of states all \(n_{1}+1\) possible positions for job \(i_{1}\). Let Property (*) hold for stage \(k-1\), i.e., the state \((f_{k-1},C_{i_{k-1}},pos_{k-1})\) is contained in the set of states. Then, according to step [2.2.2] of Algorithm 1, the state \((f_{k},C_{i_{k}},pos_{k})\) will be considered and stored in the set of states. So, according to step [3.] of Algorithm 1, the job sequence \(\pi\) will be constructed with the objective function value \(f=f^{*}\) and the problems \(1|2\)_chains_, \(p_{j}=p,r_{j}|f\), \(f\in\{\sum w_{j}C_{j},\sum w_{j}T_{j},\sum w_{j}U_{j}\}\) can be solved by a dynamic program. There are \(O(n)\) stages and \(O(n^{3})\) states \((f,C_{max},pos)\) at each stage, since \(C_{max}\in\Theta\) with \(|\Theta|\leq n^{2}\), and \(pos\in\{0,1,\ldots,n_{1}\}\). At the next stage, for each state generated at the previous stage in step [2.2.2], we need to consider \(O(n)\) new states. To perform all steps [2.2.2.1] in [2.2.2], we need \(O(n)\) operations. In step [2.2.2.1], to construct a partial solution, we need to schedule the jobs \(j_{pos^{k-1}+1},j_{pos^{k-1}+2},\cdots,j_{pos^{\prime}}\) into the partial solution, i.e., to calculate their starting times according to \(C_{max}^{k-1}\), the release dates, and the processing time. We need \(O(1)\) operations to calculate the starting time of each job, and we calculate the starting time for a job only once in step [2.2.2], e.g., the starting time of job \(j_{pos^{k-1}+1}\) is calculated only once in [2.2.2]. So, to perform all steps [2.2.2.1] in the cycle [2.2.2], we need \(O(n)\) operations, and to perform all steps [2.2.2.1] in Algorithm 1, we need \(O(n^{5})\) operations. To perform step [2.2.2.2] in \(O(1)\) time, we additionally keep \(PositionsList\) in a 2-dimensional array with \(O(n^{2})\) rows corresponding to all possible values \(C_{max}\) and \(O(n)\) columns corresponding to all possible values \(pos\). We initiate the array in step [2.1]. So, to check a dominated value, we need \(O(1)\) time. Thus, we need \(O(n^{5})\) operations to perform all steps [2.2.2.1] in Algorithm DP. To perform all steps [2.2.2.3] in Algorithm 1, we need \(O(n^{5})\) time, since it is performed only for the last job in the set \(N_{2}\). So, the running time of Algorithm 1 is \(O(n^{5})\). The theorem has been proven. We conjecture that there are other solution algorithms with a running time less than \(O(n^{5})\). Here, our motivation is only to show that the problems are polynomially solvable. For real-world problems, there are more parameters and constraints that have to be taken into consideration, and they can be possibly solved by other methods than dynamic programming.