# A Heuristic Approach to Solving the Train Traffic Re-Scheduling Problem in Real Time
## 3 Modelling the Job-Shop Scheduling Problem Using a Graph  
A well-known and efficient way of modelling the job-shop scheduling problem is to use graphs. Graph theory is a well-studied area in the computational sciences, and it provides efficient algorithms and data structures for implementation. These features make the graph a suitable candidate for modeling the problem addressed in this paper. In a job-shop scheduling problem, there are \(n\) jobs that have to be served by \(m\) different types of machines. Each job \(j\in J\) has its own sequence of operations \(O_{j}=\left\{o_{j,1},o_{j,2},\ldots,o_{j,m}\right\}\) to be served by different predefined machines from the set \(M\). The jobs have to be served by machines exclusively. The job-shop scheduling problem can be formulated using a mixed graph model \(G=(O,C,D)\), or equivalently by a disjunctive graph model. Let \(O\) denote the set of all operations to be executed by a set of different machines \(M\). The set \(C\) represents a predefined sequence of operations for each job \(j\) to visit machines from the set \(M\). The two operations \(o_{j,i}\) and \(o_{j,i}\), which have to be executed on the same machine \(m\in M\), cannot be processed simultaneously. This restriction is modelled by an edge \(\left[o_{j,i},o_{j,i}\right]\in D\) (if a mixed graph is used) or equivalently by pairs of disjunctive arcs \(\left\{\left(o_{j,i},o_{j,i}\right)\right\}\), and \(\left(o_{j,i},o_{j,i}\right)\) ) (if a disjunctive graph is used). In this paper, the mixed graph is used for modelling the primary state of the problem. Two vertices, \(o_{s}\) and \(o_{d}\) as the source and destination vertices, respectively, are added to the model to transform it to a directed acyclic graph. Using the terms \"arc\" and \"edge\" may be confusing. Edges may be directed or undirected; undirected edges are also called \"lines\", and directed edges are called \"arcs\" or \"arrows\". In this paper, the term \"edge\" is used for undirected edges, and the term \"arc\" is used for directed edges. To serve the operations in a job-shop scheduling problem, only one instance of each machine of type \(m\) is available. In a hybrid job-shop as a derivation of the job-shop scheduling problem, a set \(M_{m}\) (\(|M_{m}|\geq 1\) ) is available to serve the operations [28]. The notation \(\left\langle m,u\right\rangle\) is used to indicate a specific machine or resource \(u\) from a set \(M_{m}\) if it is necessary. These uniform parallel machine sets increase the throughput and provide more flexibility in the scheduling process. A train is here synonymous with a job in the job-shop scheduling problem. A train route from the source station to the destination can be considered to be a sequence of operations for a job \(j\). Each railroad section is synonymous to a machine \(m\). In Table 1, below, we introduce the notations that are used to describe and define the hybrid graph model, algorithmic approach, and corresponding MIP model. To solve the job-shop scheduling problem modelled by a graph, for every two conflicting operations the algorithm is responsible for determining the best execution order to reduce the objective function value. A potential conflict occurs when for two events \(o_{j,i}\), and \(o_{j,i^{\prime}}\) belonging to jobs \(j\) and \(j^{\prime}\) respectively, the following criteria become true:  
\[x^{begin}_{j,i}<x^{begin}_{j^{\prime},i^{\prime}}\quad\text{and}\quad x^{ end}_{j^{\prime},i^{\prime}}\leq x^{begin}_{j,i}+d_{j^{\prime},i^{\prime}} \tag{1}\]  
The algorithm is in charge of replacing the set of edges \(D\) with a subset of arcs \(D^{\prime}\), which defines the order to be served by a resource. As a result, the set of edges \(D\) will be substituted by a selected subset of directed arcs \(D^{\prime}\), and the mixed graph \(G=(O,C,D)\) will be transformed into a digraph \(G^{\prime}=(O,C\cup D^{\prime},\varnothing)\).