Studies On Performance Evaluation Algorithms For Max-Plus-Linear Discrete Event Dynamic Systems

The discrete event dynamic systems are disciplines emerging in the early 1980s. The motivation to study DEDS originated in the queuing problems and network analysis problems. With the development, improvement of technology of information processing, computers and robotics and application requirement, a lot of man-made systems appeared, such as Computer Integrate Manufacturing Systems, Communication Network Systems, Computer Network Systems, Traffic Dispatch Systems and Public Service Systems. Therefore, it is more urgent and has more practical valuable to study on DEDS. More and more people focus on this challenging research field and study on modeling, analysis, controlling and integrating.Based on the current literature, this dissertation studies Performance Evaluation Algorithms (algorithm of computering cycle time) for Max-Plus-Linear DEDS. Howard's algorithm and CalcCycleTime algorithm show the highest efficiency by far. So this dissertation focuses on Comparison and study on them through numerical experiment, and improves the algorithms.This dissertation first studies on both of algorithms. Howard's algorithm is a policy iterative algorithm. First, a policy is chosen and the eigenmode of the corresponding policy matrix is computed. Next, it is tested whether the generalized eigenmode of the policy matrix is already a generalized eigenmode of the original matrix. If so, the cycle time of max-plus matrix has been found. If not, the policy has to be adapted. CalcCycleTime algorithm is also policy iterative algorithm, but it has several distinct thought. Frist, CalcCycleTime algorithm calls CalcSpectralRadius to calculate the spectral radius, which essence is also improve policy by iterative policy. When the policy is optimal, the largest eigenvalue of policy matrix is the spectral radius of function. Then the nodes whose cycle time equal to spectral radius will be eliminated. At last, CalcCycleTime algorithm recursively calls itself to compute the cycle time of the reduced function.Just as the iterative policy adopted, both of them are very efficient. It is almost linear on average in time complexity. The main contents in this dissertation are as follows:(1)This dissertation makes a detailed analysis of Howard's algorithm for the first time in China, and works out the detailed Chinese doucuments of Howard's algorithm. A lot of numerical experimental programs on Howard's algorithm are developed, and the datas about its operation efficiency are obtained.(2)The result of numerical experimental comparison on Howard's algorithm and CalcCycleTime algorithm shows that the performance of former algorithm is better than the latter for the first time, and points out the direction and thought for further opitimization.(3)An optimization and improvement to Howard's algorithm is obtained as far as possible. Howard's algorithm is a relatively mature algorithm, so it's difficult to improve it. This dissertation realizes the thought of "optimized selection to initial policy" put forward by predecessors, and analyses the modification by numerical experiment. The result shows that this modification is valuable both to Howard's algorithm and CalcCycleTime algorithm. A solution to infinite loop which maybe occures under the condition of float calculation (error calculation) is proposed.