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.
Rightsdefined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Showing items related by title, author, creator and subject.
Humara, Michael Jesus (Monterey California. Naval Postgraduate School, 2020-05);Developing accurate and computationally efficient models for ocean acoustics is inherently challenging due to several factors including the complex physical processes and the need to provide results on a large range of ...
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 ...