I consider 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. In this paper, I prove the separability under an ideal just‐in‐time input condition. Using the separability, I then construct 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.
BazaraaM. S. and ShettyC. M. (1979), Nonlinear Programming: Theory and Algorithms, John Wiley & Sons, Inc., New York.
2.
BertsekasD. M. (1976), Dynamic Programming and Stochastic Control, Academic Press, Inc., New York.
3.
BitranG. R. and TirupatiD. (1988), “Planning and Scheduling for Expitaxial Wafer Production Facilities,”Operations Research36, 34–49.
4.
DenardoE. V. (1978), Dynamic Programming: Models and Applications, Prentice‐Hall, Englewood Cliffs, NJ.
5.
LiuJ. J. (1989), “The Periodic Routing of a Flexible Manufacturing System With Centralized In‐Process Inventory Flows,”International Journal Production Research27, 943–951.
6.
LiuJ. J. (1990), “Optimal Dispatching in a Periodic‐Review Cellular Manufacturing System,”Operations Research38, 893–901.
7.
YaoD. D. and ShanthikumarJ. G. (1987), “The Optimal Input Rates to a System of Manufacturing Cells,”INFOR, 25, 57–65.
