# Heuristic Method for Decision-Making in Common Scheduling Problems
## 6 Sample Scheduling Problem
### Algorithm
The component \(F_{2}(u,x,t)\) is responsible for preferring the second type of co-operation decisions, i.e., assigning only the cheapest machines to perform jobs in case the time limits are no longer active. It is calculated as a penalty for a decision to have a job performed by other machines than the lowest-cost ones when all jobs with a due date have been finished. Criterion \(q2\) is as follows. The form of the criterion as well as the form above takes into account a component related to the cost of work, a component related to necessity for the trajectory to omit the states of set \(S_{N}\) (each job is completed before its due date), and components for preferring some co-operation decisions. However, the three components are determined in different ways. First, the exact increase of work cost, instead of being calculated, is estimated. Estimation \(\Delta Q(u,x,t)\) is equal to the sum of costs of execution of unfinished and unstarted earlier jobs that are chosen to be performed by machines in a given decision and cost of transport of machines (the machine's standing cost is omitted). Secondly, the estimated cost \(\widehat{Q}_{2}(u,x,t)\) of finishing unperformed jobs (connected with the final section of the trajectory) is calculated as the sum of the cost of performing the unfinished and unstarted earlier jobs by the cheapest machine (machine) and the cost of other standing machines. Thirdly, component \(E_{2}(u,x,t)\) is a minimum value of the sum of the shortest path to a job with deadline with these job's lengths. It is determined only for a job with a deadline that is neither finished nor started earlier nor under consideration to be performed by machines in a given decision. Finally, criterion \(q2\) is as follows: \[q2(u,x,t)=\Delta Q(u,x,t)+\widehat{Q}_{2}(u,x,t)+a_{1}E_{2}(u,x,t)+b_{1}F_{1} (u,x,t)+b_{2}F_{2}(u,x,t).\] (13) Criterion \(q3\) is as follows. The third criterion version differs from the second way of determining the component \(E(u,x,t)\). It is close to the average value of time reserves \(r_{tc}\big{(}s_{p,k}\big{)}\) for values greater than 0 and equals to 0 otherwise. Criterion \(q3\) is as follows: \[q3(u,x,t)=\Delta Q(u,x,t)+\widehat{Q}_{2}(u,x,t)+a_{1}E_{3}(u,x,t)+b_{1}F_{1} (u,x,t)+b_{2}F_{2}(u,x,t).\] (14)
3. Modification of local search--the first type of modification consists of changing the \(a_{1},b_{1},b_{2}\) coefficients value after the generation of a trajectory. If it is non-admissible, then for the subsequent trajectory, the value of weight \(a_{1}\) should be increased because of the distance from the set of non-admissible states. The increase of the weight \(b_{1}\) value, which would result in lower probability of a machine stopover, can also be helpful. If the generated trajectory is admissible, then for the subsequent trajectory the values of the coefficients may be decreased and the weight of the components related to the execution cost should be increased. The second modification type consists of changing the local optimization form during trajectory generation. When all jobs with due dates are finished, there is no need to specify \"distance\" between the state and the set of non-admissible states. Thus, it is no longer necessary to apply the component \(E(u,x,t)\) in the local criterion and the modified criterion is as follows: \[q(u,x,t)=\Delta Q(u,x,t)+\widehat{Q}_{2}(u,x,t)+b_{1}F_{1}(u,x,t)+b_{2}F_{2} (u,x,t).\] (15)4. the pruning of non-perspective parts of trajectory--a trajectory generation or its finished part is interrupted when in the newly generated state we obtain a quality index that is worse than the quality index for the best solution. The information gained as a result of the trajectory analysis is used to modify the local optimization task for the next trajectory. 5. selection of state graph node--on the basis of the problem analysis, characteristic parameters were determined: cost of jobs performing for the initial part of the trajectory, total length of part.