A Stochastic Generalized Assignment Problem
A Stochastic Generalized Assignment Problem
复制标题
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
D. Spoerl;R. K. Wood
中科院分区：
文献类型：
--
作者：
D. Spoerl;R. K. Wood
我们开发了弹性广义分配问题（EGAP）的随机版本，其中包含独立的、正态分布的资源消耗系数和其他随机参数。随机 EGAP (SEGAP) 是一个具有简单追索权的随机整数规划。我们构建了两个确定性等价物：“比例均值方差模型”（PMVM）假设与单个资源相关的所有系数都有一个共同的均值方差比，而“一般均值方差模型”（GMVM）放宽了这一假设。还描述了更一般分布的模型。我们测试 PMVM 和 GMVM，将一组持续时间不确定的石油订单交付分配给一组卡车；当超出正常工作时间时，就会产生加班费。 SEGAP 的实际实例求解时间与 EGAP 相当，有时甚至更快，并且随机解的相对值可以超过 24%。
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%.