Abstract:
In Russian universities, the problem of distributing the departmental educational load is annually resolved. This problem belongs to the class of combinatorial discrete optimization problems. To solve some problems of this class, it is effective to use the selection sequence optimization algorithm developed by the authors earlier. This article provides a flowchart of this algorithm for the purpose of its visual presentation, which is aimed at further understanding of the material presented. Modeling the dynamics of the algorithm is carried out using a mathematical model built on the basis of one of the varieties of colored Petri nets - that is, on the J-net. The operating logic of this model is described in detail. A reachability tape has been built for this J-net. It contains 269 markings, some of which, representing the main nuances, are presented in the paper in table form. The reachability tape has a significant size even with a minimal non-trivial amount of simulated data, so unattainable markings are rejected by additional analysis of some inequalities sets. Due to the difficulty of contemplative analysis of inequalities’ systems, à software tool has been developed for solving these systems, whose algorithm has polynomial time complexity. Analysis of the reachability tape shows the correct operation of the optimization algorithm. Scientific novelty of the work is that for the first time, a reachability tape for the J-net has been constructed.
Keywords:reachability tape, selection sequence optimization, discrete optimization, educational load, J-net, Petri net
Fulltext:
PDF file (2074 kB)