Incremental Integer Linear Programming Models for Petri Nets Reachability Problems

摘要: The operational management of complex systems is characterized, in general, by the existence a huge number solutions. Decision-making processes must be implemented order to find best results. These need suitable modeling tools offering true practical resolution perspectives. Among them, Petri nets (PNs) provide simple graphical model taking into account, same formalism, concurrency, parallelism and synchronization. Their precise nature, their firm mathematical foundation aboundance analysis methods have made them become classical tool for study discrete event systems, ranging from operating logistic ones. However, interest field problem solving still badly known. In this paper, we consider some PN reachability problems. Since PNs can flows natural efficient way, many operations research problems defined using between states, e.g. scheduling (Lee DiCesare, 1994; Van Der AAlst, 1995), planning (Silva et al., 2000), car-sequencing (Briand, 1999). Moreover, on addresses issue flexibility: extensions been proposed facilitate addition ``color’’, ``time’’ ``hierarchy’’ (Jensen, 1992; Wang,1998). For example, it relatively easy map onto timed PNs. nature reinforce obviously strength, allowing kind interactivity with system. At last, large difficult are equivalent problem, or its variants sub-problems (Keller, 1976). Particularly, model-checking (Latvala, 2001) which represents key point when dealing directly linked an exhaustive traversal corresponding graph. Various suggested handle problem. propose use programming paradigm. Some already handled such techniques (Melzer Esparza, 1996;Silva 1998; Khomenko Koutny, but none has considered general approach based implicit net graph, does not construction. This done considering unique sequence steps growing incrementally represent exactly total behavior net. We follow here