A Stochastic Generalized Assignment Problem
Wood, R. Kevin
MetadataShow full item record
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%.
Working Paper, Operations Research Department, Naval Postgraduate School.
Showing items related by title, author, creator and subject.
Copley, David C. (Monterey, California. Naval Postgraduate School, 1984-06);The stochastic forcing theory of Frankignoul and Hasselmann, 1977 is modified to include a mixed layer model. This enables the examination of the interaction between stochastic heat flux or wind stress components and the ...
Goggins, David A. (Monterey, California. Naval Postgraduate School, 1995-09);This thesis is a continuation of optimization modeling research conducted at the Naval Postgraduate School for the U.S. Air Force Studies and Analyses Agency. That work resulted in Throughput II, a multi-period model for ...
Melton, Andrew W. (Monterey, California. Naval Postgraduate School, 1996-09);The Analyst's WorkBench is a deterministic integrated framework developed and used by the Weapons Planning Group at NAWC China Lake. The model has no stochastic capability which requires all analysis to be conducted using ...