Exact and heuristic algorithms for the interval min-max regret generalized assignment problem
Exact and heuristic algorithms for the interval min-max regret generalized assignment problem
复制标题
区间最小-最大遗憾广义分配问题的精确启发式算法
DOI：
10.1016/j.cie.2018.08.007
复制
发表时间：
2018
影响因子：
7.9
通讯作者：
Yagiura Mutsunori
中科院分区：
文献类型：
--
作者：
Wu Wei;Iori Manuel;Martello Silvano;Yagiura Mutsunori
考虑了区间费用下带最小-最大后悔准则的广义指派问题。该问题模拟了许多现实世界的应用程序，其中必须将工作分配给代理，但在做出决定后分配成本可能会有所不同。我们计算研究两种启发式方法：固定场景的方法和双替代算法。我们还研究了精确的算法方法（本德的分解和分支和切割），并进一步介绍了一个更复杂的算法，采用了各种方法，包括拉格朗日松弛和变量固定。由此产生的拉格朗日为基础的分支和切割算法表现令人满意的基准实例。
We consider thegeneralized assignment problem(GAP) with min-max regret criterion under interval costs. This problem models many real-world applications in which jobs must be assigned to agents but the costs of assignment may vary after the decision has been taken. We computationally examine two heuristic methods: a fixed-scenario approach and a dual substitution algorithm. We also examine exact algorithmic approaches (Benders-like decomposition and branch-and-cut) and further introduce a more sophisticated algorithm that incorporates various methodologies, including Lagrangian relaxation and variable fixing. The resulting Lagrangian-based branch-and-cut algorithm performs satisfactorily on benchmark instances.
登录
查看更多内容
DOI：
10.1016/j.disopt.2017.09.004
发表时间：
2017-01
期刊：
Discret. Optim.
影响因子：
--
作者：
M. Poss
通讯作者：
M. Poss
航空医疗路线和调度模型
DOI：
10.1111/j.1475-3995.1999.tb00143.x
发表时间：
1999
影响因子：
3.1
作者：
K. Ruland
通讯作者：
K. Ruland
Minmax后悔线性资源分配问题
DOI：
10.1016/s0167-6377(03)00091-9
发表时间：
2004
期刊：
Oper. Res. Lett.
影响因子：
--
作者：
I. Averbakh
通讯作者：
I. Averbakh
区间数据最小-最大后悔广义分配问题的算法
DOI：
--
发表时间：
2014
期刊：
影响因子：
--
作者：
W. Wu;M. Iori;S. Martello and M. Yagiura
通讯作者：
S. Martello and M. Yagiura
在不确定成本下跨越树状结构的最小最大遗憾
DOI：
10.1016/j.ejor.2006.07.036
发表时间：
2007
期刊：
Eur. J. Oper. Res.
影响因子：
--
作者：
E. Conde;A. Candia
通讯作者：
A. Candia