Dynamic feeding in a stochastic parallel processing system

This paper considers a dynamic input scheduling problem of a stochastic parallel processing system consisting of n identical flexible machining cells. The processing times at each cell are independent random variables. Previous study has indicated the NP complexity of the problem. The paper proves the separability under an ideal just-in-time input condition. Using the separability, it then constructs an approximation procedure for most realistic applications where the separability condition is violated. The approximation procedure requires only linear time and performed quite well on an extensive test with numerical examples.