# A Heuristic Approach to Solving the Train Traffic Re-Scheduling Problem in Real Time
## 3 Modelling the Job-Shop Scheduling Problem Using a Graph
In this paper, a multi-track railway traffic network will be considered as a job-shop scheduling problem with parallel machines (hybrid job-shop) at each stage. \begin{table}
\begin{tabular}{c l} \hline \hline
**Sets and Indices** & **Description** \\ \hline \(M\) & Set of all railway sections (i.e., machines). \\ \(m\) & The index used to denote a specific section in the set \(M\). \\ \(M_{m}\) & The sub-set of tracks and platforms that belongs to section \(m\). (i.e., parallel machines) \\ \(m_{t},u\) & A track/platform/resource instance number \(u\) from a set \(M_{m}\). \\ \(J\) & Set of all trains (i.e., jobs). \\ \(j\) & The index used to denote a specific train. \\ \(O\) & Set of all train events (i.e., operations). \\ \(O_{j}\) & Set of all events that belong to train \(j\). \\ \(O^{m}\) & Set of all events to be scheduled on a section \(m\). \\ \(O^{m,u}\) & Set of all events to be scheduled on track \(u\) of section \(m\). \\ \(i\) & The index used to denote a specific train event \(i\). \\ \(o_{j,i}\) & The symbol used to denote the event \(i\) which belongs to train \(j\). \\ \(\langle j,i,m,u\rangle\) & Tuple which refers to train \(j\) and its event \(i\) which occurs in section \(m\) and scheduled for track \(u\). When the section is single line \(u\) will be ignored. \\ \((t)\) & Prime symbol used to distinguish between two instances (i.e., job \(j\) and \(j^{\prime}\) ). \\ \hline
**Parameters** & **Description** \\ \hline \(c_{m}\) & The required minimum clear time that must pass after a train has released the assigned track \(u\) of section \(m\) and before another train may enter track \(u\) of section \(m\). \\ \(h_{m}\) & The minimum headway time distance that is required between trains (head-head and tail-tail) that run in sequence on the same track \(u\) of section \(m\). \\ \(d_{j,i}\) & The minimum running time, or dwell time, of event \(i\) that belongs to train \(j\). \\ \(b^{initial}_{j,i}\) & This parameter specifies the initial starting time of event \(i\) that belongs to train \(j\). \\ \(e^{initial}_{j,i}\) & This parameter specifies the initial completion time of event \(i\) that belongs to train \(j\). \\ \(ps_{j,i}\) & This parameter indicates if event \(i\) includes a planned stop at the associated segment. \\ \hline
**Variables** & **Description** \\ \hline \(x^{begin}_{j,i}\) & The re-scheduled starting time of event \(i\) that belongs to train \(j\). \\ \(x^{end}_{j,i}\) & The re-scheduled completion time of event \(i\) that belongs to train \(j\). \\ \(f_{j,i}\) & The tardiness (i.e., delay for train \(j\) to complete event \(i\) ). \\ \(z^{i}_{j,i}\) & Delay of event \(i,i\in O\), exceeding \(\mu\) time units, which is set to three minutes here. \\ \(q_{j,i,n}\) & A binary variable which is 1, if the event \(i\) uses track \(u\). \\ \(\gamma_{j,i,j,i}\) & A binary variable which is 1, if the event \(i\) occurs before event \(i\). \\ \(\lambda_{j,i,j,i}\) & A binary variable which is 1, if the event \(i\) is rescheduled to occur after event \(i\). \\ \(buf_{j,i}\) & Remaining buffer time for train \(j\) to complete an event \(\langle j,i\rangle\). \\ \(TFD_{j}\) & The delay for train \(j\) once it reaches its final destination, i.e., \(t_{j,last}\) which corresponds to the delay when completing its last event. \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The notations used for sets, indices, parameters, and variables.