A Stochastic Generalized Assignment Problem
Loading...
Authors
Spoerl, D.R.
Wood, R. Kevin
Subjects
Programming, stochastic; Programming, integer; Probability, stochastic model
applications
Advisors
Date of Issue
2004-01
Date
2004-01
Publisher
Language
Abstract
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%.
Type
Article
Description
Working Paper, Operations Research Department, Naval Postgraduate School.
Series/Report No
Department
Operations Research (OR)
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Spoerl, D.R. and Wood, R.K, 2004, “A Stochastic Generalized Assignment Problem,” Working Paper, Operations Research Department, Naval Postgraduate School.
Distribution Statement
Rights
defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.