# Heuristic Method for Decision-Making in Common Scheduling Problems
## 5 Characteristic of the Algorithm Class That Generates the Final Parts of the Trajectory  
Algorithms of the class under consideration raise the possibility of improving the solution by constructing many acceptable solutions and choosing the best one. Generally an algorithm can generate all trajectories of the process and in this case the optimal solution can be found as long as an admissible solution exists. Taking into consideration the fact that the problems solved belong to the NP-hard class, the purpose is not to search the whole solution space but its most perspective part. The general form of the algorithm is as follows. Initially a preliminary analysis of the input data is performed. After verification that the existence of an admissible solution is not excluded, it is possible to start generating the trajectories. The first trajectory is generated from the initial state \(s_{0}\). Each next state depends on the previous state and the decision made at that state, which is chosen from a set of possible decisions at the given state using a specific decision-making technique. Generation of the state sequence is terminated if the new state is a goal state, a non-admissible state, or a state with an empty set of possible decisions. It is possible to interrupt trajectory generating if only the quality criterion value for a given state is greater than the best quality criterion value of the found admissible trajectory. All states of constructed trajectories (first and subsequent) are stored together with the characteristic parameters. After construction of the first trajectory, the final parts of trajectory are subsequently generated, starting from one of the stored states chosen from a set of open states, using a specific selection technique. Thus, trajectories can also be constructed from the initial state. In this case, with a limited number of trajectories, it is extremely important to select the state from which the final part of trajectories is generated.  
Concluding, the important features of the presented algorithm class are as follows:  
* a trajectory sequence or a final part of the trajectory is generated, each trajectory is analyzed, and this analysis is used to obtain knowledge about the process and its control,
* all generated process states and their characteristic parameters (attributes) are stored,
* during the construction of the trajectory, the process state is analyzed and based on it the technique of selecting the decision in a given state can be modified,
* trajectory generating is interrupted if only the quality criterion value for a given state is greater than the best quality criterion value of the found admissible trajectory,
* the initial state of the final part of the trajectory is selected based on the analysis of characteristic parameters for stored states of trajectories that have been generated so far; if the selected state is the process initial state \(s_{0}\) then the whole trajectory is generated,
* the results obtained so far can be used to make any modification related to the choice of general techniques and the initial state of the trajectory final part selection general techniques.  
Therefore, distinctive components of the algorithm class that generate the final parts of the trajectory are as follow: the preliminary analysis of the problem, the technique of decision choice at a given state, the pruning non-perspective trajectory, selection technique of the initial state for the trajectory final part, and the trajectory generation parameters modification. An explanation of each component is below.