# EPO Extension of Dispatching Rules to Minimize Effects of Time Uncertainty in Production Scheduling
## 3 EPO Extension
### EPO Extension in Forward Scheduling  
In forward scheduling using dispatching rules with EPO extension, each job to be scheduled (\(J_{TD}\)) is characterized by its _earliest start time_ (\(EST_{J_{TD}}\)). \(EST_{J_{TD}}\) of a job that starts the production path (\(Preds_{J_{TD}}=\emptyset\)) is defined based on, e.g., the date of delivery of semi-finished products or raw materials that are necessary to start the job. \(EST_{J_{TD}}\) of a job that has predecessors in a production path (\(Preds_{J_{TD}}\
eq\emptyset\)) must be computed based on the end times of all \(J_{PR}\in Preds_{J_{TD}}\). To take into account the uncertainty of the processing time of predecessors, we compute the EPO end times for each \(J_{PR}\in Preds_{J_{TD}}\) using the following formulas:  
\[ \begin{split} FT_{E,J_{PR}}&=ST_{J_{PR}}+E,\\ FT_{P,J_{PR}}&=ST_{J_{PR}}+P,\\ FT_{O,J_{PR}}&=ST_{J_{PR}}+O,\end{split}  \tag{6}\]  
where \(ST_{J_{PR}}\) (\(ST_{J_{PR}}\geqslant EST_{J_{PR}}\)) is the actual start time of \(J_{PR}\). Based on the expected (\(FT_{E,J_{PR}}\)), optimistic (\(FT_{O,J_{PR}}\)) and pessimistic (\(FT_{P,J_{PR}}\)) end times of all the predecessors of \(J_{TD}\), we compute the earliest start time of \(J_{TD}\) from the following formula:  
\[EST_{J_{TD}}=\max_{J_{PR}\in Preds_{J_{TD}}}\left\{ \begin{array}{l}FT_{E,J_{PR }},\text{if}\ M_{J_{PR}}=M_{J_{TD}}\ \text{and}\ Lag_{J_{PR}}=0,\\ FT_{P,J_{PR}}+TT_{M_{J_{PR}},M_{J_{TD}}}+Lag_{J_{PR}},\text{otherwise},\end{array} \right. \tag{7}\]  
where \(M_{J_{PR}}\) and \(M_{J_{TD}}\) are machines used to produce, respectively, the jobs \(J_{PR}\) and \(J_{TD}\), \(TT_{M_{J_{PR}},M_{J_{TD}}}\geqslant 0\) is the transport time between the machines \(M_{J_{PR}}\) and \(M_{J_{TD}}\), and \(Lag_{J_{PR}}\geqslant 0\) is the lag time between the two subsequent stages of the production process imposed by a technology (for example, cooling down or drying of the semi-finished product before the next production stage). To minimize the probability of machine downtime (due, e.g., to the lack of production components), we use the pessimistic end time (\(FT_{P,J_{PR}}\)) if jobs \(J_{TD}\) and \(J_{PR}\) are produced on different machines. If \(J_{PR}\) and \(J_{TD}\) are produced on the same machine, there is no need to take into account a longer production time (constituting a kind of a safety buffer), because in such a case there is no risk of machine downtime (late termination of the predecessor will automatically delay the production of the successors). Let us note that if time windows are not taken into account, then the earliest start time is the same for all jobs and is equal to the scheduling start time. The last important aspect of the EPO extension is an additional constraint on the start time of the job \(J_{TD}\). For the purposes of the presentation, assume that the job \(J_{TD}\) is to be scheduled on machine \(M\). As already mentioned, \(ST_{J_{TD}}\) must satisfy the inequality \(ST_{J_{TD}}\geqslant EST_{J_{TD}}\), where \(EST_{J_{TD}}\) must take into account the end times of all predecessors of \(J_{TD}\) (cf. Formula (7)). However, \(EST_{J_{TD}}\) should also take into account the end time of the  
Figure 2: Exemplary production path represented by acyclic directed graph; jobs \(J_{1},J_{2},J_{3}\) have no predecessors (start production path), jobs \(J_{4},J_{5},J_{6},J_{7}\), \(J_{8},J_{11},J_{12},J_{13},J_{14}\) have one predecessor, jobs \(J_{9},J_{10}\) have two predecessors. job, which was last processed on the machine \(M\). This additional condition can be written as follows:  
\[EST_{I_{TD}}\leqslant\left\{ \begin{array}{ll}FT_{O,I_{lat}}&\text{if }\left|SV \right|_{FT_{O,I_{lat}}}\right|>0,\\ FT_{E,I_{lat}}&\text{if }\left|SV\right|_{FT_{E,I_{lat}}}\right|>0,\\ \infty&\text{otherwise,}\end{array}