Solution approaches for solving stochastic job shop and blocking job shop problems

Abstract

The Stochastic and Blocking Job Shop Scheduling problems are two extensions of the Standard Job Scheduling Problem. In the stochastic extension, processing times retrieve a probability distribution. This results in an objective function that is also a stochastic variable. In order to reliably calculate the objective value, a simulation has to be executed. When solving such problems, new complexities come into play and different solution approaches need to be developed. This thesis presents several new solution approaches that can optimize the Stochastic Job Shop Scheduling Problem. The blocking extension removes the unlimited intermediate machine buffers. When the buffers are not available, the already NP-Hard job shop becomes even harder to solve. In this thesis, additional solution approaches, built upon existing approaches, are discussed that can optimize the Blocking Job Shop Problem better. Using a randomized neighbourhood in combination with a MIP, new areas of solutions are being explored that lead to better solutions. Also a cycle analysis is given that describes the problem infeasibilities in greater detail.