# EPO Extension of Dispatching Rules to Minimize Effects of Time Uncertainty in Production Scheduling
## 3 EPO Extension
### EPO Extension in Backward Scheduling  
In backward scheduling using dispatching rules with EPO extension, each job (\(J_{TD}\)) to be scheduled is characterized by its latest end time (\(LFT_{I_{TD}}\)). \(LFT_{I_{TD}}\) of a job that ends the production path (\(Succs_{I_{TD}}=\emptyset\)) is usually defined based on the date of delivery to a customer. \(LFT_{I_{TD}}\) of a job that has successors (\(Succs_{I_{TD}}\
eq\emptyset\)) must be calculated based on the start time of all its successors \(J_{SC}\in Succs_{I_{TD}}\). To take into account uncertainty of the processing time of successors, we compute the EPO start times for each \(J_{SC}\in Succs_{I_{TD}}\) using the following formulas:  
\[ST_{E,J_{SC}} =FT_{J_{SC}}-E,\] \[ST_{P,J_{SC}} =FT_{J_{SC}}-P, \tag{10}\] \[ST_{O,J_{SC}} =FT_{J_{SC}}-O,\]  
where \(FT_{E,J_{SC}}\) is the actual end time of the job \(J_{SC}\). Based on the expected (\(ST_{E,J_{SC}}\)), pessimistic (\(ST_{P,J_{SC}}\)), and optimistic (\(ST_{O,J_{SC}}\)) start times of all the successors of \(J_{TD}\), we compute the latest end time of the job \(J_{TD}\) from the following formula:  
\[LFT_{I_{TD}}=\min_{J_{SC}\in Succs_{I_{TD}}}\left\{ \begin{array}{ll}ST_{E,J_{ SC}},\text{if }M_{J_{SC}}=M_{I_{TD}}\text{ and }Lag_{J_{TD}}=0,\\ ST_{P,J_{SC}}-TT_{M_{J_{SC}}}M_{I_{TD}}-Lag_{J_{TD}},\text{otherwise,}\end{array} \right. \tag{11}\]  
where \(M_{J_{SC}}\) and \(M_{I_{TD}}\) are machines used to produce, respectively, the jobs \(J_{SC}\) and \(J_{TD}\), \(TT_{M_{J_{SC}M_{I_{TD}}}}\geqslant 0\) is the transport time between the machines \(M_{J_{SC}}\) and \(M_{I_{TD}}\), and \(Lag_{J_{SC}}\geqslant 0\) is the lag time between the two subsequent stages of the production process imposed by a technology. Similarly as in the case of EPO-forward scheduling, \(LFT_{I_{TD}}\) should also take into account the following additional condition:  
\[LFT_{I_{TD}}\geqslant\left\{ \begin{array}{ll}ST_{O,I_{lat}}&\text{if }\left|SV \right|_{ST_{O,I_{lat}}}\right|>0,\\ ST_{E,I_{lat}}&\text{if }\left|SV\right|_{ST_{E,I_{lat}}}\right|>0,\\ -\infty&\text{otherwise,}\end{array} \right. \tag{12}\]where \(J_{first}\) is the first job completed on the machine \(M\), \(ST_{O,fint}\) and \(ST_{E,first}\) are, respectively, the optimistic and pessimistic start time of the last job, and  
\[SVI_{t}=\big{\{}J\mid LFT_{J}\geqslant t\big{\}}\]  
is the set of jobs that can be scheduled on the machine \(M\) at time \(t\). In this case, the availability time of the machine \(M\) is defined as follows:  
\[MAT_{M}=\max\{EST_{J}\mid J\in JF_{M}\}. \tag{13}\]  
Schedules obtained from constructive algorithms can be far from optimal, but this is the trade-off between the computational cost and the quality of the solutions. However, even if the obtained solution (schedule) is not satisfactory, it can still be very useful. For example, it can be used as an initial solution for local search metaheuristics (LNS, VNS, ILS, etc.). The main advantage of the solutions obtained from constructive algorithms over the randomly generated solutions is the fact that the former solutions are certainly admissible, that is, they satisfy all constraints. The most basic constraint is the requirement that each successor job is performed after all its predecessors, and each predecessor job is performed prior to all its successors. Schedules built using dispatching rules with EPO extension can be optimized in the same way as the schedules created with the forward and backward methods. The conditions of admissibility of the given schedule should include the inequalities (8) or (12). This will ensure that the schedule will be robust, that is, it will take into account the uncertainty of processing times. The proposed EPO extension ensures higher flexibility of production plans and also less frequent interventions (e.g., due to delays in production) by planners. The presented formulas allow one to easily determine all three times of the EPO extension.