Stochastic algorithms in scheduling theory (Diss., TU Berlin) (Q2726304)

In the thesis the author investigates stochastic algorithms and their application within the scheduling theory. The most popular model to describe stochastic processes is the theory of Markov chains. Simulated annealing-based algorithms can be directly derived from the Markov chain model. We develop simulated annealing-based heuristics for solving the core scheduling problem, namely, the job shop problem. A new, neighborhood relation is introduced which involvesa a non-uniform generation probability of neighbors. It depends on the number of longest paths in the underlying graph representation. The neighborhood function is combined with two cooling schedules and the resulting algorithms are analyzed in terms of their run-time complexity.