# Connected and Autonomous Vehicle Scheduling Problems: Some Models and Algorithms
## 5 A Crossroad with Dividing Lines  
In this section, we consider a crossroad with dividing lines and four sets, \(N_{1},N_{2},N_{3},N_{4}\), of CAVs. They share four sectors of a crossroad denoted by \(M_{1}\), \(M_{2},M_{3}\), \(M_{4}\) (see Figure 5). We have to find an optimal sequence of passing these sectors. We can formulate the following job shop scheduling problem with four machines. There are four sets, \(N_{1},N_{2},N_{3},N_{4}\), of jobs and four machines corresponding to the sectors \(M_{1}\), \(M_{2}\), \(M_{3}\), \(M_{4}\). Each job \(j\) consists of two operations. For each job \(j\in N_{1}\), its first operation has to be processed on machine \(M_{1}\) and its second one has to be processed on machine \(M_{2}\). For each job \(j\in N_{2}\), its first operation has to be processed on machine \(M_{2}\) and its second one has to processed on machine \(M_{4}\). For each job \(j\in N_{3}\), its first operation has to be processed on machine \(M_{3}\) and its second one has to be processed on machine \(M_{1}\). For each job \(j\in N_{4}\), its first operation has to be processed on machine \(M_{4}\) and its second one has to be processed on machine \(M_{3}\). The processing times of the operations are equal to \(p\). Precedence relations can be given as chains of jobs. If the lengths of the dividing lines are equal to 0, then the second operation of a job \(j\) should be processed immediately after the first one. Otherwise, for each of the sets \(N_{1},N_{2},N_{3},N_{4}\), there are four buffers of limited capacities, namely \(b_{1},b_{2},b_{3},b_{4}\) jobs for the corresponding set of jobs. At any moment, for the set \(N_{1}\), there can be up to \(b_{1}\) jobs for which the first operation is completed and the second one is not yet started. We denote these problems by \(J4|4\)_chains_, \(p_{j}=p,r_{j}|f\), \(f\in\{C_{max},\sum w_{j}C_{j},\sum w_{j}T_{j},\sum w_{j}U_{j}\}\). The problems \(J4|4\)_chains_, \(p_{j}=p,r_{j}|f\), \(f\in\{C_{max},\sum w_{j}C_{j},\sum w_{j}T_{j},\sum w_{j}U_{j}\}\) can be solved by a branch-and-bound (B&B) algorithm. The search (rooted) tree is constructed by the following branching rule. For any node of the tree, we consider the following 8 possible branches:  
* Schedule the first unscheduled possible operation for a job \(j\in N_{1}\) on machine \(M_{1}\) at the earliest possible starting time. If there is no such an operation, skip this branch. * Schedule the first unscheduled possible operation for a job \(j\in N_{3}\) on machine \(M_{1}\) at the earliest possible starting time. Figure 4: The initial positions of the jobs and an optimal schedule for Example 2. Figure 5: A crossroad with dividing lines. * Schedule the first unscheduled possible operation for a job \(j\in N_{1}\) on machine \(M_{2}\) at the earliest possible starting time. * Schedule the first unscheduled possible operation for a job \(j\in N_{2}\) on machine \(M_{2}\) at the earliest possible starting time. * Schedule the first unscheduled possible operation for a job \(j\in N_{3}\) on machine \(M_{3}\) at the earliest possible starting time. * Schedule the first unscheduled possible operation for a job \(j\in N_{4}\) on machine \(M_{3}\) at the earliest possible starting time. * Schedule the first unscheduled possible operation for a job \(j\in N_{2}\) on machine \(M_{4}\) at the earliest possible starting time. * Schedule the first unscheduled possible operation for a job \(j\in N_{4}\) on machine \(M_{4}\) at the earliest possible starting time. Thus, there are up to \(2^{3}=8\) branches for each node to be considered. Since there are \(2n\) operations, where \(n=|N_{1}\bigcup N_{2}\bigcup N_{3}\bigcup N_{4}|\), there are no more than \(2n\) levels in the search tree. Thus, we have no more than \((2^{3})^{2n}=2^{6n}\) nodes to be considered. If some of the values \(b_{1},b_{2},b_{3},b_{4}\) are equal to \(0\), we have fewer nodes. As an example, if each of them is equal to \(0\), then we have only \(2^{3n}\) nodes.