A Stochastic Generalized Assignment Problem

Working Paper, Operations Research Department, Naval Postgraduate School. ; We develop a stochastic version of the Elastic Generalized Assignment Problem (EGAP) that incorporates independent, normally distributed resource-consumption coefficients and other random parameters. The Stochastic EGAP (SEGAP) is a stochastic integer program with simple recourse. We construct two deterministic equivalents: The “proportional mean-variance model” (PMVM) assumes a common mean-to-variance ratio for all coefficients associated with a single resource, while the “general mean-variance model” (GMVM) relaxes this assumption. Models for more general distributions are also described. We test PMVM and GMVM to assign a set of petroleum-order deliveries with uncertain durations to a set of trucks; overtime pay accrues when regular working hours are exceeded. Realistic instances of SEGAP solve in times that are comparable to the EGAPs, sometimes faster, and the relative value of the stochastic solution can exceed 24%.