# Heuristic Method for Decision-Making in Common Scheduling Problems
## 7 Experimental Results  
The purpose of the current experiments was to examine the efficiency of algorithms that generate multiple trajectories, using the ability to improve the obtained solution by changing the final part of the trajectory. For this purpose, the simulation experiments were carried out involving the construction of 40 trajectories (or trajectory final part) with the use of a specific criterion for the selection of local decisions, the modifications of the local decision search described above, the pruning of non-perspective parts of the trajectory, and the five ways described above to choose the state from which the final part of the trajectory is generated. Examples were selected so that the existence of an admissible solution could not be ruled out. A verification of the effectiveness of the proposed form of local criterion and applying the components \(E(u,x,t)\) and \(F(u,x,t)\) was carried out and shown in [32; 33]. The research was conducted for the set of four regular structure heading networks (denoted as \(GR\)) and five irregular structure heading networks (denoted as \(Glr\)). Each network is represented by a planar graph, in which the vertex degrees equal 1 to 4. The number of jobs with a deadline was approximately 25% of all jobs. Parameters of relevant heading networks (number of node, number of edge, and total length of jobs to perform) are presented in Table 3. The tasks were performed by one machine (working groups) for which setup is required and one machine (working groups) that does not require setup. The parameters of the first machine were as follows: performing speed 10.0 m/h, setup speed 100 m/h, performing cost 200.0 \(\$\)/h, transport cost 100.0 \(\$\)/h and standing cost 30.0 \(\$\)/h. The parameters of the second machine were as follows: performing speed 5.0 m/h, performing cost 50.0 \(\$\)/h and standing cost 5.0 \(\$\)/h. Table 3 presents data for all networks. Experiments were conducted as follows. Three groups of algorithms were tested; the first one used the criterion \(q1\) (Equation (8)) to select the decision in a given state, the second criterion \(q2\), and the third criterion \(q3\). The values of the component coefficients in the local criterion \(q1\), \(q2\), and \(q3\) were selected on the basis of previous results obtained for algorithms generating single whole trajectories. In each algorithm group we used the selection of state graph node method, i.e., \(\widehat{s1}\), \(\widehat{s2}\), \(\widehat{s3}\), \(\widehat{s4}\), and \(\widehat{s5}\). The brutal force algorithm was used to obtain an optimal solution and check the effectiveness of the mentioned algorithms. However, the optimal solution was obtained for one network only, namely \(GR\)-\(2\). In other cases, the simulation calculation was stopped after about two days, since the time for obtaining a solution was not effective and for real decision-making it was too long. After this time of calculation, suboptimal solutions for _GR-1a_, _GR-1b_, _GR-3_, _Glr-1_, and _Glr-4_ were obtained. For the remaining networks, an admissible solution was not found. Tables 3-12 present the results obtained for a particular network. \"_Alg._\(q1-\widehat{s3}\)\" denotes an algorithm with the criterion \(q1\) for decision selection and choice of the node for generating the final part of the trajectory, by \(\widehat{s1}\) for example. The tables show the best obtained cost, percentage error, and simulation time (in milliseconds) for particular algorithms. Based on the results obtained, it can be stated that the calculation time for these algorithms is not even 1 s, and for the largest network it is up to 24 s. The resulting objective function values (total cost of work) are also good. For the _GR-2_ network (with a known optimal solution), the maximum percentage error was 4.597%, and the best result was obtained for algorithm \(q3-\widehat{s1}\), for which the solution varied by just 0.782%. For the _GR-1a_, _GR-1b_, _GR-3_, _Glr-1_, and _Glr-4_ networks, the total cost was less than the obtained suboptimal cost.