# Connected and Autonomous Vehicle Scheduling Problems: Some Models and Algorithms
## 2 A Road with Two Lanes and One Lane Closure
We denote this problem by \(1|2\ chains,p_{j}=p,r_{j}|\sum C_{j}\) according to the traditional three-field notation \(\alpha|\beta|\gamma\) for scheduling problems proposed by [16], where \(\alpha\) describes the machine environment, \(\beta\) gives the job characteristics and further constraints, and \(\gamma\) describes the optimization criterion. Let  
\[T_{j}(\pi)=\max\{0,C_{j}(\pi)-d_{j}\}\]  
be the tardiness of job \(j\) in the schedule \(\pi\). If \(C_{j}(\pi)>d_{j}\), then job \(j\) is tardy and we have \(U_{j}=1\); otherwise, \(U_{j}=0\). Figure 1: A road with two lanes and one lane closure. Subsequently, we consider also the following objective functions:  
\[\sum w_{j}C_{j} = \sum w_{j}C_{j}(\pi)\ \text{-- total weighted completion time},\] \[\sum T_{j} = \sum T_{j}(\pi)\ \text{-- total tardiness},\] \[\sum w_{j}T_{j} = \sum w_{j}T_{j}(\pi)\ \text{-- total weighted tardiness};\] \[\sum w_{j}U_{j} = \sum w_{j}U_{j}(\pi)\ \text{-- weighted number of tardy jobs},\] \[C_{max} = \max\{C_{j}(\pi)\}\ \text{-- makespan}\]  
It is known that the problems \(1|chains,p_{j}=p,r_{j}|\sum w_{j}C_{j}\) and \(1|chains,p_{j}=p,r_{j}|\sum w_{j}T_{j}\) with an arbitrary number of chains are NP-hard, see [17]. This has been proven by a reduction from the 3-partition problem. In [18], polynomial time dynamic programming algorithms have been presented to solve the problems \(1|p_{j}=p,r_{j}|\sum T_{j}\) and \(1|p_{j}=p,r_{j}|\sum w_{j}U_{j}\). In an optimal schedule for the problem \(1|2\ chains,p_{j}=p,r_{j}|\sum C_{j}\), the jobs are processed in non-decreasing order of the values \(r_{j}\). This can be easily proven by contradiction. Assume that we have an optimal schedule \(\pi=(\ldots,j_{1},j_{1},\ldots)\), where \(r_{j_{1}}<r_{j_{2}}\). Then, for the schedule \(\pi^{\prime}=(\ldots,j_{1},j_{2},\ldots)\), we have \(\sum C_{j}(\pi)\geq\sum C_{j}(\pi^{\prime})\). For an illustration of the concepts introduced above, we consider the following small Example 1. **Example 1**. : _Let \(N_{1}=\{1,2\}\), \(N_{2}=\{3,4\}\). Moreover, the values \(p=2\), \(r_{1}=0\), \(r_{2}=3\), \(r_{3}=1\), \(r_{4}=4\), and \(d_{1}=d_{2}=10\), \(d_{3}=3\), \(d_{4}=6\) are given. For the chosen job sequence \(\pi=(1,3,2,4)\), we obtain_  
\[S_{1}(\pi)=0,\ S_{3}(\pi)=2,\ S_{2}(\pi)=4,\ S_{4}(\pi)=6\]  
_and_  
\[\sum C_{j}=\sum_{j\in N}C_{j}(\pi). \tag{1}\]0  
_Thus, we obtain_  
\[\sum C_{j}=\sum_{j\in N}C_{j}(\pi). \tag{1}\]1  
_For the job sequence \(\pi^{\prime}=(3,4,1,2)\), we obtain_  
\[\sum C_{j}=\sum_{j\in N}C_{j}(\pi). \tag{1}\]2  
We note that there exists a set \(\Theta\) of possible completion times of all jobs with \(|\Theta|\leq n^{2}\) since:  
* without loss of generality, we consider only active schedules, where no job can be processed earlier without loss of feasibility;
* there are no more than \(n\) different values \(r_{j}\);
* all processing times are equal to \(p\) and thus, for any job \(j\in N\), its completion time is equal to \(r_{i}+lp,\ i\in N,l\leq n\). 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 (DP). In the DP, we consider the jobs \(i_{1},i_{2},\ldots,i_{n_{2}}\in N_{2}\) one by one, where \(i_{1}\to i_{2}\to\cdots\to i_{n_{2}}\). Thus, at each stage \(k\) of the dynamic program, we consider a single job \(i_{k},\ k=1,2,\ldots,n_{2}\). Moreover, at each stage \(k>1\) we consider all states \((f^{k-1},C_{max}^{k-1},pos^{k-1})\) and the corresponding best partial solutions (sequences of jobs) stored at the previous stage. The meaning of the above triplet is as follows. Here, \(f^{k-1}\) is the value of the considered objective function for the partial solution. \(C_{max}^{k-1}=C_{i_{k-1}}\in\Theta\) denotes the completion time of job \(i_{k-1}\) in the corresponding partial solution. Finally, \(pos^{k-1}\in\{0,1,2,\ldots,n_{1}\}\) describes the position of a job, and this means that job \(i_{k-1}\) is processed between the jobs \(j_{pos}\in N_{1}\) and \(j_{pos+1}\in N_{1},\ 0<pos<n_{1}\).