- 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. Copyright 2012 Inderscience Enterprises Ltd.