Tactical Manpower Planning via Programming Under Uncertainty

This paper presents models for different types of manpower pooling policies. A multi-grade manpower system with mutually exclusive skills is considered. The work load imposed is a random variable characterized by the known joint distribution of the number of jobs to be performed and of the time to do a job. The basic models are developed as a tool for manpower planning in the jobbing workshops of an oil company. The resulting "two-stage programmes under uncertainty" are shown to reduce to mixed-integer linear programmes. The models are then generalized to permit their use in a larger class of manpower planning problems.     

Short-term manpower planning for MRT carriage maintenance under mixed deterministic and stochastic demands

The purpose of this research is to develop two manpower supply planning models and a solution algorithm for mass rapid transit carriage maintenance under mixed deterministic and stochastic demands. These models are formulated as mixed integer programs that are characterized as NP-hard. We employ problem decomposition techniques, coupled with the CPLEX mathematical programming solver, to develop an algorithm that is capable of efficiently solving the problems. The models and the method used currently in actual operations are evaluated by a simulation-based evaluation method. Finally, we perform a case study using real operating data from a Taiwan MRT maintenance facility. The preliminary results are good, showing that the models could be useful for planning carriage maintenance manpower supply.     

Stochastic models for air cargo terminal manpower supply planning in long‐term operations

In this research, based on two deterministic‐demand planning models, we established two long‐term stochastic‐demand planning models by incorporating the stochastic disturbances of manpower demands that occur in actual operations. The models are formulated as mixed integer linear programs that are solved using a mathematical programming solver. To compare the performance of the two stochastic‐demand and two deterministic‐demand planning models under the stochastic demands that occur in actual operations, we further develop a simulation‐based evaluation method. Finally, we perform numerical tests using real operating data from a Taiwan air cargo terminal. The preliminary results show that the stochastic models could be useful for planning air cargo terminal manpower supply. Copyright © 2008 John Wiley & Sons, Ltd.     

A Family of Stochastic Programming Test Problems Based on a Model for Tactical Manpower Planning

Ariyawansa and Felt (2001, 2004) have recently created a test problem collection for testing software for stochastic linear programs. This freely-available, web-based collection was originally created with 35 problem instances from 11 problem families representing a variety of application areas. The collection was created with plans for enriching it with problem instances based on different application areas from the research community. The work of Martel and Al-Nuaimi (1973) on manpower planning under uncertain demand represents an application area suitable for creating new problem instances to be added to the collection. The purpose of this paper is to describe the construction of a new family of stochastic programming test problems based on the work of Martel and Al-Nuaimi (1973). As part of our construction, we review the work of Martel and Al-Nuaimi (1973) leading to an extension of their models for which their solution procedure does not apply. The new test problems are based on this extension. We also present solutions to the test problems obtained using the software package CPA (2002) for stochastic programming developed by Ariyawansa, Felt and Sarich. Mathematics Subject Classifications (2000) 90C15, 90C90, 65K05. K. A. Ariyawansa: The work of this author was supported in part by the U.S. Army Research Office under Grant DAAD 19-00-1-0465.     

On capacity expansion planning under strategic and operational uncertainties based on stochastic dominance risk averse management

A new scheme for dealing with uncertainty in scenario trees is presented for dynamic mixed 0–1 optimization problems with strategic and operational stochastic parameters. Let us generically name this type of problems as capacity expansion planning (CEP) in a given system, e.g., supply chain, production, rapid transit network, energy generation and transmission network, etc. The strategic scenario tree is usually a multistage one, and the replicas of the strategic nodes root structures in the form of either a special scenario graph or a two-stage scenario tree, depending on the type of operational activity in the system. Those operational scenario structures impact in the constraints of the model and, thus, in the decomposition methodology for solving usually large-scale problems. This work presents the modeling framework for some of the risk neutral and risk averse measures to consider for CEP problem solving. Two types of risk averse measures are considered. The first one is a time-inconsistent mixture of the chance-constrained and second-order stochastic dominance (SSD) functionals of the value of a given set of functions up to the strategic nodes in selected stages along the time horizon, The second type is a strategic node-based time-consistent SSD functional for the set of operational scenarios in the strategic nodes at selected stages. A specialization of the nested stochastic decomposition methodology for that problem solving is outlined. Its advantages and drawbacks as well as the framework for some schemes to, at least, partially avoid those drawbacks are also presented.     

Modelling heterogeneity in a manpower system: a review

Manpower planning is an essential methodology for business and industry; it allows managers to make more efficient use of human resources. However, human behaviour is highly variable and it is therefore essential for manpower planning that population heterogeneity is successfully modelled. In this paper we review methods of incorporating population heterogeneity into manpower modelling. The analysis of differentials in a manpower system is emphasized since they are a source of aggregation error in stochastic models. Two strategies have been stressed, the use of observable sources of heterogeneity as they affect wastage, and the latent sources which cannot be identified precisely but are known to affect the key parameters of most models. Copyright © 2000 John Wiley & Sons, Ltd.     

Stochastic Programming Applied to Human Resource Planning

This paper shows how state space models for human resource planning may be extended from linear and goal-programming formulations to cover the case where manpower demands and available resources for future periods are not known with certainty. Under reasonable assumptions, the problem can be treated as a multi-period stochastic program with simple recourse. Normal and Beta probability distributions are fitted to the right hand sides, and the equivalent determinstic programme solved using convex separable programming. An application of this methodology to a military human resource planning problem is described. Solution times for the stochastic model compare favourably with those for a goal-programming model of the same human resource system.     

Designing a two-echelon distribution network under demand uncertainty

This paper proposes a comprehensive methodology for the stochastic multi-period two-echelon distribution network design problem (2E-DDP) where product flows to ship-to-points are directed from an upper layer of primary warehouses to distribution platforms (DPs) before being transported to the ship-to-points. A temporal hierarchy characterizes the design level dealing with DP location and capacity decisions, as well as the operational level involving transportation decisions as origin-destination flows. These design decisions must be calibrated to minimize the expected distribution cost associated with the two-echelon transportation schema on this network under stochastic demand. We consider a multi-period planning horizon where demand varies dynamically from one planning period to the next. Thus, the design of the two-echelon distribution network under uncertain customer demand gives rise to a complex multi-stage decisional problem. Given the strategic structure of the problem, we introduce alternative modeling approaches based on two-stage stochastic programming with recourse. We solve the resulting models using a Benders decomposition approach. The size of the scenario set is tuned using the sample average approximation (SAA) approach. Then, a scenario-based evaluation procedure is introduced to post-evaluate the design solutions obtained. We conduct extensive computational experiments based on several types of instances to validate the proposed models and assess the efficiency of the solution approaches. The evaluation of the quality of the stochastic solution underlines the impact of uncertainty in the two-echelon distribution network design problem (2E-DDP).     

A Dynamic Programming Approach to Determine Optimal Manpower Recruitment Policies

The manpower planning models available in the literature have dealt with how changes take place in a manpower planning system, under various operating and policy constraints. However, none of these models has identified the manpower system costs. In this paper we have identified various manpower system costs. Further, we have developed a manpower planning model with the objective of minimizing the manpower system costs. The model has been found to be analogous to the Wagner-Whitin model in production/inventory management. A numerical example has been given to illustrate the model.     

When can we improve on sample average approximation for stochastic optimization?

We explore the performance of sample average approximation in comparison with several other methods for stochastic optimization. The methods we evaluate are (a) bagging; (b) kernel density estimation; (c) maximum likelihood estimation; and (d) a Bayesian approach. We use two test sets: first a set of quadratic objective functions allowing different types of interaction between the random component and the univariate decision variable; and second a set of portfolio optimization problems. We make recommendations for effective approaches.     

Optimal recruitment strategies in a multi-level manpower planning model

Markov manpower planning models have extensively been analysed in the past in order to find an optimal personnel strategy for which the stocks of the manpower system evolve towards desirable ones. So far, those models do not take into account interactions among different organizational decision levels. In this paper, a multi-level manpower planning model is presented that considers, besides the desirable stock vector at overall level, proposals for the departmental stocks from lower organizational levels. Attainability of the stock vectors at departmental level is examined under control by recruitment and interdepartmental transitions. A multi-level optimization algorithm is presented to determine an optimal recruitment strategy resulting in attainable and acceptable stocks that are a compromise between the proposal from the top and the proposals from the departments.     

Multicut Benders decomposition algorithm for process supply chain planning under uncertainty

In this paper, we present a multicut version of the Benders decomposition method for solving two-stage stochastic linear programming problems, including stochastic mixed-integer programs with only continuous recourse (two-stage) variables. The main idea is to add one cut per realization of uncertainty to the master problem in each iteration, that is, as many Benders cuts as the number of scenarios added to the master problem in each iteration. Two examples are presented to illustrate the application of the proposed algorithm. One involves production-transportation planning under demand uncertainty, and the other one involves multiperiod planning of global, multiproduct chemical supply chains under demand and freight rate uncertainty. Computational studies show that while both the standard and the multicut versions of the Benders decomposition method can solve large-scale stochastic programming problems with reasonable computational effort, significant savings in CPU time can be achieved by using the proposed multicut algorithm.     

A model of distributionally robust two-stage stochastic convex programming with linear recourse

We consider distributionally robust two-stage stochastic convex programming problems, in which the recourse problem is linear. Other than analyzing these new models case by case for different ambiguity sets, we adopt a unified form of ambiguity sets proposed by Wiesemann, Kuhn and Sim, and extend their analysis from a single stochastic constraint to the two-stage stochastic programming setting. It is shown that under a standard set of regularity conditions, this class of problems can be converted to a conic optimization problem. Numerical results are presented to show the efficiency of the distributionally robust approach.     

Robust Averaged Control of Vibrations for the Bernoulli–Euler Beam Equation

This paper proposes an approach for the robust averaged control of random vibrations for the Bernoulli–Euler beam equation under uncertainty in the flexural stiffness and in the initial conditions. The problem is formulated in the framework of optimal control theory and provides a functional setting, which is so general as to include different types of random variables and second-order random fields as sources of uncertainty. The second-order statistical moment of the random system response at the control time is incorporated in the cost functional as a measure of robustness. The numerical resolution method combines a classical descent method with an adaptive anisotropic stochastic collocation method for the numerical approximation of the statistics of interest. The direct and adjoint stochastic systems are uncoupled, which permits to exploit parallel computing architectures to solve the set of deterministic problem that arise from the stochastic collocation method. As a result, problems with a relative large number of random variables can be solved with a reasonable computational cost. Two numerical experiments illustrate both the performance of the proposed method and the significant differences that may occur when uncertainty is incorporated in this type of control problems.     

Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem

In urban areas, logistic transportation operations often run into problems because travel speeds change, depending on the current traffic situation. If not accounted for, time-dependent and stochastic travel speeds frequently lead to missed time windows and thus poorer service. Especially in the case of passenger transportation, it often leads to excessive passenger ride times as well. Therefore, time-dependent and stochastic influences on travel speeds are relevant for finding feasible and reliable solutions. This study considers the effect of exploiting statistical information available about historical accidents, using stochastic solution approaches for the dynamic dial-a-ride problem (dynamic DARP). The authors propose two pairs of metaheuristic solution approaches, each consisting of a deterministic method (average time-dependent travel speeds for planning) and its corresponding stochastic version (exploiting stochastic information while planning). The results, using test instances with up to 762 requests based on a real-world road network, show that in certain conditions, exploiting stochastic information about travel speeds leads to significant improvements over deterministic approaches.     

Path planning for robots under stochastic uncertainty *

In order to reduce large online measurement and correction expenses, the a priori informations on the random variations of the model parameters of a robot and its working environment are taken into account already at the planning stage. Thus, instead of solving a deterministic path planning problem with a fixed nominal parameter vector, here, the optimal velocity profile along a given trajectory in work space is determined by using a stochastic optimization approach. Especially, the standard polygon of constrained motion-depending on the nominal parameter vector-is replaced by a more general set of admissible motion determined by chance constraints or more general risk constraints. Robust values (with respect to stochastic parameter variations) of the maximum, minimum velocity, acceleration, deceleration, resp., can be obtained then by solving a univariate stochastic optimization problem Considering the fields of extremal trajectories, the minimum-time path planning problem under stochastic uncertainty can be solved now by standard optimal deterministic path planning methods     

Discrete Approximation Scheme in Distributionally Robust Optimization

Discrete approximation, which has been the prevailing scheme in stochastic programming in the past decade, has been extended to distributionally robust optimization (DRO) recently. In this paper, we conduct rigorous quantitative stability analysis of discrete approximation schemes for DRO, which measures the approximation error in terms of discretization sample size. For the ambiguity set defined through equality and inequality moment conditions, we quantify the discrepancy between the discretized ambiguity sets and the original set with respect to the Wasserstein metric. To establish the quantitative convergence, we develop a Hoffman error bound theory with Hoffman constant calculation criteria in a infinite dimensional space, which can be regarded as a byproduct of independent interest. For the ambiguity set defined by Wasserstein ball and moment conditions combined with Wasserstein ball, we present similar quantitative stability analysis by taking full advantage of the convex property inherently admitted by Wasserstein metric. Efficient numerical methods for specifically solving discrete approximation DRO problems with thousands of samples are also designed. In particular, we reformulate different types of discrete approximation problems into a class of saddle point problems with completely separable structures. The stochastic primal-dual hybrid gradient (PDHG) algorithm where in each iteration we update a random subset of the sampled variables is then amenable as a solution method for the reformulated saddle point problems. Some preliminary numerical tests are reported.     

Supply capacity acquisition and allocation with uncertain customer demands

We study a class of capacity acquisition and assignment problems with stochastic customer demands often found in operations planning contexts. In this setting, a supplier utilizes a set of distinct facilities to satisfy the demands of different customers or markets. Our model simultaneously assigns customers to each facility and determines the best capacity level to operate or install at each facility. We propose a branch-and-price solution approach for this new class of stochastic assignment and capacity planning problems. For problem instances in which capacity levels must fall between some pre-specified limits, we offer a tailored solution approach that reduces solution time by nearly 80% over an alternative approach using a combination of commercial nonlinear optimization solvers. We have also developed a heuristic solution approach that consistently provides optimal or near-optimal solutions, where solutions within 0.01% of optimality are found on average without requiring a nonlinear optimization solver.     

Modelling heterogeneity in manpower planning: dividing the personnel system into more homogeneous subgroups

Manpower planning is very useful for human resource management in large organizations. Most manpower models are concerned with the prediction of the future behaviour of the staff: they might leave the organization, get promoted or acquire more and new skills. This behaviour can vary a lot among different employees, what makes prediction difficult. It is common to tackle this problem by dividing the whole heterogeneous personnel system in several more homogeneous subgroups. This approach is often used to develop manpower planning models for prediction, control or optimization. Although the division in homogeneous subcategories is a fundamental and important step in the application of the models, up till now literature neglects to discuss a procedure to deal with this in practice. This paper suggests a general framework to find the distinguished homogeneous subcategories by determining and considering observable sources of personnel heterogeneity. Copyright © 2006 John Wiley & Sons, Ltd.     

Stochastic uncapacitated hub location

We study stochastic uncapacitated hub location problems in which uncertainty is associated to demands and transportation costs. We show that the stochastic problems with uncertain demands or dependent transportation costs are equivalent to their associated deterministic expected value problem (EVP), in which random variables are replaced by their expectations. In the case of uncertain independent transportation costs, the corresponding stochastic problem is not equivalent to its EVP and specific solution methods need to be developed. We describe a Monte-Carlo simulation-based algorithm that integrates a sample average approximation scheme with a Benders decomposition algorithm to solve problems having stochastic independent transportation costs. Numerical results on a set of instances with up to 50 nodes are reported.