DISTRIBUTION OF THE MINIMAL COMPLETION-TIME OF PARALLEL TASKS IN MULTI-REWARD SEMI-MARKOV MODELS

The completion time of parallel tasks executed on a randomly varying system is represented as the barrier hitting time in a multi-reward stochastic model. The work produced by the system is calculated by means of two types of functionals that account for different mechanisms of accumulation of the reward in physical systems. The work requirement of each parallel task is assigned as an absorbing barrier acting on the corresponding functional. The distribution of the first time at which one of the functionals hits its barrier is investigated. If the barrier levels are assumed to be PH random variables, the hitting time becomes a PH random variable and the completion time problem is converted into the solution of a suitable expanded Markov chain.