PN to CSP Methodology: Improved Bounds

Abstract

Traditional production planning techniques are constrained by large numbers of decision variables, uncertainty in demand and time production, and non-deterministic system behaviour (intrinsic characteristics in manufacturing). This paper presents an improvement to a methodology in the area of Knowledge Based Systems (KBS) which generates automatically Constraint Satisfaction Problems (CSP), using Petri-nets (PN) to model the problem and Constraint Programming (CP) in the solution. The methodology combines the modelling power of PN to represent both manufacturing architecture and production logistics, together with the optimisation performance given by CP. While PN can represent a whole production system, CP is effective in solving large problems, especially in the area of planning. The improvement raises from the design of a more complete algorithm to calculate the transitions firings bounds, and hence to remove useless problem variables.