Efficient Algorithms for Calculating the System Matrix and the Kleene Star Operator for Systems Defined by Directed Acyclic Graphs over Dioids
Esmaeil Bahalkeh · OhioLink ETD Center (Ohio Library and Information Network) · 2015
Calculating the performance measures of a manufacturing system is of fundamental importance in many industrial engineering problems, particularly scheduling.The max-plus algebra representation of a system is given by the system matrix, shown by , that can be used to calculate different performance measurements.This study proposes an efficient and structured algorithm to calculate from the graph representation of the system.The proposed algorithm uses Kahn's algorithm [1] to topologically sort the nodes in the graph.In addition, using the same algorithm the Kleene star of a matrix can be computed in a slightly more efficient way.Kleene star contains longest path values between any two vertices.It is used to solve linear equations and also for performance measure purposes.Moreover, this study performs interval analysis on proposed algorithms.In interval system, unlike deterministic systems, input data of the system such as processing times are shown by intervals.