Title: An executable modelling and simulation framework for NP-complete complexity problems and different forms of uncertainties

Authors: Hyunsoo Lee; Amarnath Banerjee

Addresses: School of Industrial Engineering, Kumoh National Institute of Technology, Gumi, Gyeongbuk, P.O. 730-701, Korea. ' Department of Industrial and Systems Engineering, Texas A&M University, 3131 TAMUS, College Station, TX 77843-3131, USA

Abstract: With rapid globalisation and increasing complexity of processes in service systems, there is need for a new and executable modelling framework that can be used to model, simulate and analyse the complex processes. The target processes often belong to the class of problems that are NP-complete. Existing frameworks for modelling NP-complete problems have certain limitations. A new Petri Net-based framework, Fuzzy Coloured Petri Net with stochastic time delay and NP-complete cases (FCPN-std/NPC), is presented in this paper that allows modelling, simulation and analysis of processes that have an underlying NP-complete complexity problem. The framework has the ability to characterise two types of uncertainties, variance type uncertainty and ambiguity type uncertainty. A new set of process-semantics-based nodes and mapping functions are defined for the FCPN-std/NPC framework that allows modelling of a class of NP-complete problems. A small supply chain example is used to illustrate the operational characteristics of the framework.

Keywords: process modelling; NP-complete complexity; ambiguity type uncertainty; variance type uncertainty; FCPN-std/NPC; fuzzy Petri nets; coloured Petri nets; stochastic time delay; FCPN; NPC; simulation; supply chain design; supply chain management; SCM.

DOI: 10.1504/IJSOI.2012.048789

International Journal of Services Operations and Informatics, 2012 Vol.7 No.1, pp.1 - 17

Received: 03 Apr 2012
Accepted: 09 Apr 2012

Published online: 30 Aug 2012 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article