Dynamic control of the N queueing network with application to shipbuilding

Abstract

The US shipbuilding industry faces challenges of building ships on time and within budgeted cost. We introduce an operational flexibility to shipbuilding to improve the system control. We model the flexible ship production system as an ‘N’ queueing network. However, the ‘N’ network model still lacks effective and computationally lightweight policies, especially with non-preemption. We use a Markov Decision Process (MDP) to gain structural insights into the optimal control policy. We develop a state dependent Optimal Threshold policy and benchmark it against other policies to show its excellent robustness and effectiveness. Our extensive test suite shows that (1) the Optimal Threshold policy performs the best in all the heuristics we tested; and (2) the cost of the system under control of this threshold policy is very close to the optimal cost calculated by the MDP. To calculate the exact optimal threshold level is difficult; therefore, we develop a birth-death process to determine a Analytical threshold level. Based on the optimal threshold values over a large test suite, we refine the analytical threshold level using a second-order regression model. We find the performance of the Regression Threshold policy to be within a few percent of optimal.

Keywords:

• operational flexibility
• Markov decision processes
• heuristic scheduling policies
• shipbuilding

Acknowledgments

The authors acknowledge Hoda Parvin for her work on modelling and preliminary simulation studies related to this research. This work was supported in part by the National Science Foundation under Grant No. DMI-0542063, and Office of Naval Research (ONR) N00014-08-1-0579.