Hybrid approach using simulation-based optimisation for job shop scheduling problems

Abstract

In this paper, we present a hybrid modelling approach and formulation using simulation-based optimisation (SbO) for solving complex problems, viz., job shop scheduling. The classical job shop scheduling problem is NP-Hard. Traditionally, the problem is modelled as a Mixed-Integer Programming (MIP) model and solved using exact algorithms (branch-and-bound, branch-and-cut, etc) or using meta-heuristics (Genetic Algorithm, Particle Swarm Optimisation, etc). In our hybrid SbO approach, we propose a modified formulation of the scheduling problem where the operational aspects of the job shop are captured only in the simulation model. Two new decision variables, controller delays and queue priorities, are introduced. The performances of the MIP-based approach and the proposed hybrid approach are compared through the number of decision variables, run time and the objective values for select deterministic benchmark problem instances. The results clearly indicate that the hybrid approach outperforms the traditional MIP for all large-scale problems, resulting in solutions closer to optimum in a much lesser computational time. Interestingly, it is also observed that the introduction of an ‘error’ term in the objective of the deterministic problem improves performance. Finally, the performance of the proposed SbO approach is analysed for stochastic job shops.

Keywords:

• simulation optimisation
• heuristic
• job shop
• scheduling