On symmetry and asymptotic periodicity of scheduling algorithms

The presence of symmetry and periodicity in optimization algorithms can have either positive or negative influence on dynamics of decision making. For instance, consider a cycling effect while solving the linear programming problem by the simplex method. The cycling is harmful and may cause a simplex method to get stuck in a local optimum; another example is the sub-cycles that are prohibited when solving the traveling salesman problem. On the other hand, symmetry and periodicity can be very useful when they help to quickly reach the optimum for robotic scheduling problems; such is the case, also, when the shortest path in a graph is sought bidirectionally from a start node and concurrently from an end node. The first part of the paper describes common types of symmetry and their effects on efficiency of the scheduling algorithms. In the second part, we present typical examples of periodic algorithms in scheduling theory. Finally, we present a new asymptotically periodic algorithm for solving a discrete search problem under uncertainty, when the overlooking and false alarms may occur at each step of the algorithm.