# Heuristic Method for Decision-Making in Common Scheduling Problems
## 6 Sample Scheduling Problem
### Formal Model of Problem  
Based on the ALMM methodology, it is possible to build different models of the same problem. The model for the preparatory work in mines problem was proposed by [PERSON] in [PERSON] and Dyduch (1988). It differs from the one presented below because of another state system encoding. This section presents an algebraic-logical model of scheduling problems on unrelated parallel machines with deadline and machine setup dependent on the process state where relationship between tasks is defined by the graph. The model presented below is an extension and generalization of the model shown in [PERSON] and Dyduch (1988). Additionally, the details of the decision and transition function, set of possible decisions, and costs calculation are shown in detail. The following notation is used:  
* \(G=(V,E)\)--a non-directed graph where vertices set \(V=1,2,\ldots,n\) correspond to nodes representing places where the machine starts and/or finishes performing the current job and the edge set \(E=1,2,\ldots,e\) correspond to jobs,
* \(M\)--set of machine (working groups), \(M=M_{1}\cup M_{2}\) where \(M_{1}\)--subset of machine (working groups) for which setup is required and \(M_{2}\)--subset of machine (working groups) that does not require setup,
* \(J\)--set of jobs. The process state at any instant \(t\) is defined as a vector \(x=\left(x^{0},x^{1},\ldots,x^{|M|}\right)\), where \(M=M_{1}\cup M_{2}\). A coordinate \(x^{0}\) describes a set of jobs that have been performed up to moment \(t\). The other coordinate \(x^{m}\) describes the state of the \(m\)-th machine, where \(m=1,2  
* \(X_{I}^{m}\) is a set that corresponds to the situations where the machine is in the node: \[X_{I}^{m}=\{(p,\omega,\lambda):p=0\wedge\omega\in V\wedge\lambda=0\}.\] (4)
* \(X_{II}^{m}\) is a set that corresponds to situations where machine \(m\) is performing job \(j\) toward node \(v_{f}(j)\): \[X_{II}^{m}=\{(p,\omega,\lambda):p=j\wedge\omega=v_{f}(j)\wedge\lambda\in(0,l( j)]\}.\] (5)
* \(X_{III}^{m}\) is a set that corresponds to situations where machine \(m\in M1\) is transported to job \(j\) and will perform it toward node \(v_{f}(j)\): \[X_{III}^{m}=\{(p,\omega,\lambda):p=j\wedge\omega=v_{f}(j)\wedge\lambda\in(l( j),\infty]\}.\] (6)  
The decision \(u=\left(u^{1},u^{2},\cdots,u^{|M|}\right)\) is taken together for all machines. It determines which job or jobs should be started at moment \(t\), which machines are assigned to perform the jobs, which machines should be set up, and which machines should wait. The particular coordinate \(u^{m}\) refers to the \(m\)-th machine and \(u^{m}=J\cup\{0\}\), where \(u^{m}=j\) denotes that job \(j\) is assigned to be performed by machine \(m\) and \(u^{m}=0\) denotes a continuation of the previous machine operations. The only possible decision can be taken in the given state \(s=(x,t)\). It is impossible to start performing a job when no job represented by the adjacent edge in graph \(G\) is completed. Also, it is impossible to assign a new job to a machine that is currently continuing a previously assigned job (setup or performing job). Moreover, it may be decided to stop a machine or machines if at least one machine is currently working or has a job assigned. Thus, the set of possible decisions in the state \(s=(x,t)\) is:  
\[U_{p}(s)=U_{p}^{1}(s)\times U_{p}^{2}(s)\times\cdots\times U_{p}^{|M|}(s) \backslash H(s). \tag{7}\]  
The set of possible decisions \(U_{p}^{m}(s)\) for the \(m\)-th machine in the state \(s=(x,t)\) is defined as follows:  
\[\forall_{m=1,2,\ldots|M|}U_{p}^{m}(s)= \begin{cases}J_{D}(s)\cup\{0\}&for\ m:x^{m}(s)\in X_{I}^{m}\\ \quad\quad\quad\quad\{0\}&for\ m:x^{m}(s)\in\left(X_{II}^{m}\cup X_{III}^{m} \right),\end{cases}  \tag{8}\]  
where \(J_{D}(s)\) denotes a set of jobs that are available in a given state, including jobs that are unperformed and not assigned to any machine, and for which there is a transport path.