# Connected and Autonomous Vehicle Scheduling Problems: Some Models and Algorithms
## 2 A Road with Two Lanes and One Lane Closure  
In this section, we consider a road with two lanes, where two sets of CAVs, \(N_{1}\) and \(N_{2}\), are given. The CAVs from the set \(N_{1}\) go on lane 1, and the CAVs from the set \(N_{2}\) go on lane 2. Both lanes have the same direction. On lane 2, there is a lane closure and the CAVs from the set \(N_{2}\) have to move to lane 1, see Figure 1.  
We have to find a sequence of passing the lane closure by the CAVs from the sets \(N_{1}\) and \(N_{2}\) in order to minimize a given objective function, e.g., the total passing time. We assume that  
* a maximal feasible speed of the CAVs is given. The CAVs either go with the maximal feasible speed or brake in order to let another CAV change the lane. * an acceleration is not taken into account. * the time needed to change the lane is not taken into account, i.e., it is equal to zero. * the CAVs have the same length. * the safe distance between two CAVs is the same for all vehicles. Since the problems investigated in this paper have not been considered in the literature so far, these assumptions are made for the first time to obtain simplified models. In real-world problems, these assumptions can be false, although solution algorithms for simplified models can be used to solve sub-problems or to obtain lower or upper bounds. The same problem arises, e.g., on railway sections and in automated warehouses of logistics companies with autonomous robot transporters. This simplified problem can be formulated as a single machine scheduling problem as follows. Given a set \(N=N_{1}\bigcup N_{2}\) of \(n\) jobs that have to be processed on a single machine from time 0 on. For each job \(j\), a processing time \(p_{j}=p>0\), a release date \(r_{j}\geq 0\), a due date \(d_{j}\geq 0\), and a weight \(w_{j}>0\) are given. The machine can process no more than one job at a time. The processing time \(p\) can be computed from the maximal feasible speed and the length of a CAV. The value \(r_{j}\) corresponds to the earliest time when the processing of the vehicle can start, resulting from the position of the CAV \(j\) on the road. For example, let the speed of each car be 60 km per hour and the length of the closed road section be 100 m. Thus, a car needs 6 s to pass the road closure. Therefore, we assume \(p=6\) (in seconds). Let a car \(j\) be 0 m from the beginning of the road closure and a car \(i\) be 200 m behind. So, we assume \(r_{j}=0\) and \(r_{i}=12\) according to their speed and the distances. Moreover, let the starting time of any schedule computed be 05:00:00 a.m. which we consider as time 0. Let the due date for car \(i\) be 05:00:15, then we assume \(d_{i}=15\). It is obvious that the tardiness of car \(i\) is no less that \(6+12-15=3\) seconds in any feasible schedule. We call a feasible schedule active if one cannot reduce the objective function value by shifting a single job to an earlier time without violating the constraints. Without loss of generality, we consider only active schedules in this paper. A schedule is uniquely determined by a permutation \(\pi\) of the CAVs of the set \(N\). Let \(S_{j}(\pi)\) be the starting time of job \(j\) in the schedule \(\pi\). Then, \(C_{j}(\pi)=S_{j}(\pi)+p\) is the completion time of job \(j\) in the schedule \(\pi\). A precedence relation can be defined as follows. For the jobs from the set \(N_{1}=\{j_{1},j_{2},\ldots,j_{n_{1}}\}\), we have \(j_{1}\to j_{2}\to\cdots\to j_{n_{1}}\), where \(n_{1}=|N_{1}|\) and \(j\to i\) means that the processing of job \(j\) precedes the processing of job \(i\). Thus, there is a chain of jobs on lane 1. Analogously, a chain of jobs is defined for the set \(N_{2}=\{i_{1},i_{2},\ldots,i_{n_{2}}\}\). For the single machine scheduling problem of minimizing total completion time, the goal is to find an optimal schedule \(\pi^{*}\) that minimizes  
\[\sum C_{j}=\sum_{j\in N}C_{j}(\pi). \tag{1}\]  
Here, the completion time of a job is equal to the time when the vehicle passes the closed lane segment.