An Efficient Method to Compute Collision Probability in a Series-Parallel Machines Model

摘要

Collision probability is one of the most important factors relating to the productivity of a manufacturing line, and focused investigation of collision probability has recently been taking place. There are two areas of collision probability studies: theoretical studies, which focus on the analysis of collision probability, and algorithmic studies, which focus on the computation of collision probability using simulation. The results of theoretical studies so far have been somewhat limited in comparison to the results of their algorithmic counterparts. Recently, a computation method for collision probability in a series-parallel machines model was presented. In this paper, we present a new method for computing collision probability in the series-parallel machines model. The previous method includes a sorting procedure, and this sorting procedure has an influence on the time complexity of the previous method. On the other hand, the proposed method utilizes a priority queue, and does not require a sorting procedure. Consequently, we offer an efficient method to compute collision probability in the series-parallel machines model. Moreover, we carry out computational experimentation in order to show that our method is actually fast. We also show the computational results relating to an optimal machine allocation.