# Heuristic Method for Decision-Making in Common Scheduling Problems
## 6 Sample Scheduling Problem
### Algorithm  
The algorithms based on the algebraic-logic model were developed for the problem under consideration. The corresponding algorithm for generating a single trajectory is described in [32; 33]. Its components have been partially used in the algorithms below that generate the final part of the trajectory. The basic components of the presented algorithms are as follows:  
1. preliminary analysis of data--firstly, it is verified that an admissible solution exists or the time limitation is active for the given problem. Secondly, some characteristic features of the problem have been identified, i.e., a deadline for some jobs, and a much higher cost of using machines with setup. They were used to determine the form of local optimization and attributes of state graph node selection. 2. local choice--the decision in the given state is chosen using the special local optimization task with semimetrics. Three versions of the local decision criterion are presented below. Criterion \(q1\) is as follows. The local criterion takes into account a component related to the cost of the work, a component related to the necessity for the trajectory to omit the states of set \(S_{N}\) (each job is completed before its due date) and a component for preferring some cooperative decisions. Thus, the local criterion is of the form \((a_{1},b_{1},b_{2}\)--weights of particular components): \[q1(u,x,t)=\Delta Q(u,x,t)+\widehat{Q}_{1}(u,x,t)+a_{1}E_{1}(u,x,t)+b_{1}F_{1}( u,x,t)+b_{2}F_{2}(u,x,t),\] (12) where \(\Delta Q(u,x,t)\) denotes the increase of work cost, calculated as described in Table 2. \(\widehat{Q}_{1}(u,x,t)\) is the estimated cost of finishing unperformed jobs (connected with the final section of the trajectory) and is calculated as the sum of the costs of completing decisions made earlier (performing job and/or setup machines), the cost of performing unperformed jobs by the cheapest machine, and the cost of other machines' stopover. The third component \(E_{1}(u,x,t)\) uses the value of the estimated \"distance\" between the new potential state \(s_{p\_k}\), and the set of non-admissible states. The time reserve \(r_{tc}\big{(}s_{p\_k}\big{)}=d(j)-t_{p\_k}-\tau(j)-t_{end}\) for each unfinished or unassigned \begin{table}
\begin{tabular}{c c} \hline \hline
**for the Decision to Continue the Activity of the Machine \(\mathbf{u^{m}=0}\):** \\ \hline \(\Delta Q^{m}\big{(}u^{m}_{k},s_{k}\big{)}=\begin{cases}K^{m}_{STOP}\cdot \Delta t&:x_{m}\in X^{m}_{I}\wedge m\in M\\ K^{m}_{P}\cdot\Delta t&:x_{m}\in X^{m}_{I}\wedge m\in M_{2}\\ K^{m}_{S}\cdot min\Big{(}\frac{|r_{min}(m,j)|}{V^{m}_{S}},\Delta t\Big{)}+K^{m} _{P}\cdot max\Big{(}\Delta t-\frac{|r_{min}(m,j)|}{V^{m}_{P}},0\Big{)}&:x_{m} \in X^{m}_{I}\cup X^{m}_{I\!I}\wedge m\in M_{1}\\ \hline \hline
**for the Decision to Assign a New Task to the Machine \(\mathbf{u^{m}=j}\)** \\ \hline \(\Delta Q^{m}\big{(}u^{m}_{k},s_{k}\big{)}=\begin{cases}K^{m}_{S}\cdot min \Big{(}\frac{|r_{min}(m,j)|}{V^{m}_{S}},\Delta t\Big{)}-K^{m}_{P}\cdot max\Big{(} \Delta t-\frac{|r_{min}(m,j)|}{V^{m}_{P}},0\Big{)}&:m\in M_{1}\\ K^{m}_{P}\cdot\Delta t&:m\in M_{2}\\ \end{cases}\) & \(:m\in M_{2}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Cost increase for machine \(m\). job \(j\) with a due date is calculated and takes into consideration \(d(j)\) due date for job \(j\), \(\tau(j)\) time necessary to perform job \(j\) and unperformed jobs forming the shortest path by the fastest machine, and \(t_{end}\) time necessary to finalize the fastest machine current activity. \(E_{1}(u,x,t)\) is inversely proportional to the minimum value of time reserve \(r_{tc}\big{(}s_{p,k}\big{)}\) for its values greater than 0, and equals to 0 otherwise. The component \(F_{1}(u,x,t)\) is responsible for preferring the first type of co-operation decisions, i.e., a reduction of machine idleness time in order to perform transport, especially if there are due dates. It is calculated as a penalty for a decision about a stopover in a case where a machine could have started another job.