Naval personnel assignment:an application of linear-quadratic penalty methods

Abstract

The problem of optimally (re)allocating Navy personnel to permanent stations is compounded by several considerations: budgetary requirements, staffing of positions by occupation groups or ranks, and maintaining an acceptable level of readiness. The problem can be formulated as a transportation problem with side constraints. An additional, non-network, variable measures the readiness level. However the resulting mathematical programs are very large - up to 66,000 variables and 36,000 constraints including 5,400 non-network inequalities. In this paper we report on an application of the Linear-Quadratic Penalty (LQP) method to solve this large scale problem. It is therefore possible to exploit the structure of the embedded transportation problem. The algorithm solves efficiently, and to a high degree of accuracy, models that would not be solved with a general purpose solver. Hence, the model can be used for strategic planning decisions. Further work on the CRAY Y-MP supercomputer illustrates the use of vector computers for solving the Naval personnel scheduling problem in a way that makes it useful for operational planning purposes.