Sojourn Times in G/M/1 Fork-Join Networks

다국어 초록 (Multilingual Abstract)

We consider a processing network in which jobs arrive at a fork-node according to a renewal process. Each job requires the completion of two tasks, which are instantaneously assigned by the fork-node to two task-processing nodes that operate like G/M/1 queueing stations. The job is completed when both of two tasks are finished. The sojourn time (or response time) of a job in this G/M/1 fork-join network is the total time it takes to complete the two tasks. Our main result is a closed-form formula for approximating the sojourn-time distribution of a job that arrives in equilibrium.
Preliminary results establish the existence and general formulas for the limiting distribution of the task completion times and sojourn times. These formulas, which are not tractable for computations, provide a framework for our approximation based on certain key parameters. Formulas for these parameters are obtained by the use of bounds, properties of D/M/1 and M/M/1 fork-join networks, and exploratory simulations. Statistical tests show that our formulas are good fits for the sojourn-time distributions obtained from simulations.

목차 (Table of Contents)

• Abstract
• 1. INTRODUCTION
• 2. PRELIMINARIES
• 3. MAIN RESULT
• 4. JUSTIFICATION OF APPROXIMATION 2
• 5. NUMERICAL EXAMPLES
• REFERENCES