# Heuristic Method for Decision-Making in Common Scheduling Problems
## 5 Characteristic of the Algorithm Class That Generates the Final Parts of the Trajectory
### Initial State for Final Part of Trajectory Selection Technique  
The generation of all process states is ineffective and successfully used only for problems of small size. Thus, in the case of NP-hard problems the number of constructed trajectories is limited. In such a situation it is very important to construct trajectories with the best value for the quality criterion. The decision technique in the course of a single trajectory generation is one of the factors affecting it. The second factor is the choice of the state from which the final part of the trajectory starts.  
The method of selecting this state can be one, predetermined for all generated trajectories, or varied, depending on the obtained result. The simplest way to select any initial state for the final part of a trajectory is a random selection or a selection based on the order of generation.  
The classical methods of searching for a solution can be used, for example \"best-first search\" (the state with the lowest quality criterion value is selected). However, such methods are not effective for the mentioned class of problems. Therefore, a heuristic state selection method should be used, where the state evaluation function depends on the quality of trajectories generated so far, and may be changed.  
In the presented approach we use a set of untaken decisions in state \(U_{p,ut}(s)\), which is assigned to each process state. Initially, this set equals the set of possible decisions in this state, and is reduced by the decision taken.  
Generation of the trajectory final part begins with the state belonging to the set of open states \(O\). It is defined as a subset of all the admissible states for which the set of untaken decisions in this state is not empty and the value of the quality criterion for the initial part of the trajectory (from the initial state to that state) is less than the best quality criterion for the previously generated admissible trajectory. Thus, the set of open states \(O\) is increased at the moment of generating a new state by that state. Moreover, set \(O\) is first reduced by the state at the time of considering the last decision from the set of possible decisions in that state, and secondly reduced by the states for which the value of the quality criterion is higher than the new best value of the quality criterion for the newly generated admissible trajectory.  
Each process state may be related to a set of attributes (parameters). The form of these attributes depends on the problem under consideration and is based on the knowledge gained from the problem analysis, some observations and intuition, and expert knowledge. Attributes can be considered separately or as a function, including a set of attributes with appropriate weights.  
Therefore, the initial state for the new final part of a trajectory is a state belonging to the set of open states \(O\), for which the value of the specially defined attribute (heuristic function) is the best. Figure 2 shows state graph constructing. In the figure distinctive states are highlighted: green indicates the goal state, red a non-admissible state, violet open states, and gray states in which the trajectory is being pruned.