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

Kishore Kulkarni and J Venkateswaran

Journal of Simulation, 2015, vol. 9, issue 4, 312-324

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.

Date: 2015
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1057/jos.2014.40 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tjsmxx:v:9:y:2015:i:4:p:312-324

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjsm20

DOI: 10.1057/jos.2014.40

Access Statistics for this article

Journal of Simulation is currently edited by Christine Currie

More articles in Journal of Simulation from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().