# A Heuristic Approach to Solving the Train Traffic Re-Scheduling Problem in Real Time
## 4 A Heuristic Algorithm for Conflict Resolution in the Mixed Graph \(G\)
If the algorithm adds the opposite arc (\(o_{j^{\prime},i}\), \(o_{j^{\prime},i}\) ), then operation \(o_{j^{\prime},i}\) have to be served before the operation \(o_{j,i}\), which means that the predefined order of the trains for using this section is changed. This condition occurs when the algorithm tries to prevent deadlocks (unfeasible solutions), or the operation \(o_{j,i}\) has a high tardiness (a delayed train). Six dispatching rules are provided for the conflict resolution process. Table 2 is a description of those dispatching rules. In the train scheduling problem, a train blocks its current section until obtaining the next section or block. Therefore, swapping is not possible in the train scheduling problem. Accordingly, the _addArc_ function has to satisfy the blocking condition in the graph \(G\) (the alternative graph approach). To fulfil the blocking condition, instead of adding an arc from the operation \(o_{j,i}\) to the operation \(o_{j,i}\), an arc from the next operation \(o_{j,i+1}\) with a zero weight will be added to the operation \(o_{j,i}\). This directed arc means that the operation \(o_{j^{\prime},i}\) cannot proceed with its execution on the machine \(m\) until the operation \(o_{j,i+1}\) starts (\(x^{begin}_{j,i^{\prime}}\) ), meanwhile, the operation \(o_{j,i}\) is finished). This condition blocks job \(j^{\prime}\) on theprevious machine, even if it is completed. If the operation \(o_{j,i}\) is the last operation of job \(j\), then an arc with a weight \(d_{j,i}\) has to be added. \begin{table}
\begin{tabular}{p{142.3 pt} p{142.3 pt}} \hline \hline
**Conflict Resolution Strategy** & **Description** \\ \hline
1. Minimum release time goes first & The train with the earliest initial start time (\(b_{j,i}^{initial}\) ) goes first if no deadlock occurs. \\
2. More delay goes first & If there is a conflict between two trains, the one with the largest tardiness (delay) goes first. The tardiness is calculated as \(t_{j,i}=Max\big{(}0,b_{j,i}^{begin}-b_{j,i}^{initial}\big{)}\big{)}\). \\
3. Less real buffer time goes first & The train with the smallest buffer time goes first. Buffer time is defined as a subtraction of initial ending time and real finishing time \(\left(buf_{j,i}=e_{j,i}^{initial}-\left(X_{j,i}^{begin}+d_{j,i}\right)\right)\right)\) for two operations to be scheduled on the same, occupied machine. \\
4. Less programmed buffer time goes first & The train with smallest buffer time goes first. Buffer time is defined as a subtraction of initial ending time and programmed ending time \(\left(buf_{j,i}=e_{j,i}^{initial}-\left(b_{j,i}^{initial}+d_{j,i}\right)\right)\) for two operations to be scheduled on the same, occupied machine. \\
5. Less total buffer goes first & The train with smallest total buffer time goes first. Total buffer time is defined as a summation of programmed buffer times until the destination point for the trains, i.e., \(\left(\sum\limits_{k=i}^{\left(\frac{\text{test}}{k}buf_{j,k}\right)\right)\). \\
6. Less total processing time & The train with smallest running time to get to the destination goes first (i.e., the minimum total processing time). The total processing time is defined as a summation of required time to pass each section, for a train, i.e., \(\left(\sum\limits_{k=i}^{\left(\frac{\text{test}}{k}d_{j,k}\right)\right)\). \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Description of dispatching rules used for conflict resolution. Figures 1 and 2 illustrate the difference between the mixed graph and alternative graph models for conflict resolution. There are two conflicting trains in the same path on the sections \(m_{1}\) and \(m_{2}\). The train \(j_{1}\) is planned on the sections \(m_{1},m_{2}\), and \(m_{3}\). The route for the train \(j_{2}\) is \(m_{1},m_{2}\), and \(m_{4}\). The events \(o_{1,1}\) and \(o_{2,1}\) have a conflict on the machines \(m_{1}\) and events \(o_{1,2}\) and \(o_{2,2}\) on the machine \(m_{2}\).