# Heuristic Method for Decision-Making in Common Scheduling Problems
## 6 Sample Scheduling Problem
### Formal Model of Problem
\(H(s)\) denotes the set of decisions to assign one job to be performed by more than one machine and decisions not to assign any jobs to be performed by any machine when all the machines in a given state are standing. The set \(H(s)\) definition is as follows:  
\[H(s)=\{u:\left(\exists_{i,j=1,2,\ldots,|M|\
eq j}\,u^{i}(s)=u^{j}(s)\
eq 0 \right)\vee\left(\forall_{i=1,2,\ldots,|M|}u^{i}(s)=0\wedge x^{i}(s)\in X_{I} ^{m}\right)\}. \tag{9}\]  
The decision \(u=\left(u^{1},u^{2},\cdots,u^{|M|}\right)\) is non-admissible when it leads to the state \(s=(x,t)\) belonging to the set \(S_{N}\), i.e., as a result of the decision \(d(j)\) is exceeded for a job. Based on the current state \(s=(x,t)\) and the decision \(u\) taken in this state, the subsequent state \((x^{\prime},t^{\prime})=f(u,x,t)\) is generated by means of the transition function \(f\). Firstly, the moment \(t^{\prime}\) is determined. This is the nearest moment at which at least one machine will finish its work. For that purpose, \(t_{m}\) time of completion of the realized task needs to be calculated for each machine. The subsequent state will occur in the moment \(t^{\prime}=t+\Delta t\), where \(\Delta t\) equals the lowest value of the established set of \(t_{m}\). The next state occurs at the moment \(t^{\prime}=t+\Delta t\), where \(\Delta t=min_{m=1,2,\ldots,|M|}t_{m}\). Let \(|r_{min}(m,j)|\) denote the length of the shortest transportation route to job \(j\) for machine \(m\), \(V_{p}^{m}\) denote the efficiency of \(m\) machine (performing length per time unit) and \(V_{S}^{m}\) denote the speed of the machine setup. The completion time \(t_{m}\) for the machine \(m\) in a given state \(s\) depends on the type of decision and equals:  
1. the sum of the setup time (transport by the shortest transport route of \(|r_{min}(m,j)|\) length at a \(V_{S}^{m}\) speed) and the job completion time (performing job \(j\) of \(l(j)\) length at speed \(V_{P}^{m}\)) when machine \(m\in M_{1}\) is standing in node \(v\). 2. the job \(j\) completion time (performing job \(j\) of \(l(j)\) length at speed \(V_{P}^{m}\)) when the machine \(m\in M_{2}\) is standing in node \(v\). 3. the completion time remaining \(\lambda\leq l(j)\) length at speed \(V_{P}^{m}\) when machine \(m\in M\) continues processing the previously assigned job. 4. the sum of the setup time remaining \(\lambda-l(j)\) length at speed \(V_{S}^{m}\) and the job \(j\) completion time (performing job \(j\) of \(l(j)\) length at speed \(V_{P}^{m}\)) when machine \(m\in M_{1}\) continues processing the previously assigned job and is in the process of setup. 5. if the machine is standing in node \(v\) and no decision has been made to assign another job, then the completion time equals infinity. Thus, the completion time \(t_{m}\) can be represented in the following form: \[t_{m}=\left\{ \begin{array}{cl}\frac{|r_{min}(m,j)|}{V_{S}^{m}}+\frac{l(j)}{V _{P}^{m}}&:x^{m}\in X_{1}^{m}\wedge u^{m}(s)=j\wedge m\in M_{1}\\ \frac{l(j)}{V_{P}^{m}}&:x^{m}\in X_{1}^{m}\wedge u^{m}(s)=j\wedge m\in M_{2}\\ \frac{\lambda}{V_{P}^{m}}&:x^{m}\in X_{1I}^{m}\wedge u^{m}(s)=0\\ \frac{\lambda-l(j)}{V_{S}}+\frac{l(j)}{V_{P}^{m}}&:x^{m}\in X_{III}^{m}\wedge u ^{m}(s)=0\\ \infty&:x^{m}\in X_{I}^{m}\wedge u^{m}(s)=0\end{array} \right..\] (10)  
Once the moment \(t^{\prime}\) is known, it is possible to determine the proper state of the process at the time. The first coordinate \(x^{0}\) of the proper state, i.e., the set of completed jobs, is increased by the number of jobs that have been finished at moment \(t^{\prime}\):  
\[x^{0^{\prime}}=x^{0}\cup\{j:\ \exists_{m\in M}\ x^{m}(s)=(p,\omega,\lambda) \wedge p=j\wedge t_{m}=\Delta t\}. \tag{11}\]  
Afterwards, the values of subsequent coordinates in the new state are determined by \(x^{m^{\prime}}=(p^{\prime},\omega^{\prime},\lambda^{\prime})\), for \(m=1,2\ \ldots\ |M|\), which represent the states of particular machines.