检索结果-内蒙古大学图书馆

generalized assignment problem: Truthful mechanism design without money

OPERATIONS RESEARCH LETTERS 2017年第1期45卷 72-76页

作者： Fadaei, Salman Bichler, Martin Tech Univ Munich Dept Informat Munich Germany

We propose truthful approximation mechanisms for strategic variants of the generalized assignment problem (GAP) in a payment-free environment. In GAP, a set of items has to be optimally assigned to a set of bins without exceeding the capacity of any singular bin. In our strategic variant, bins are held by strategic agents and each agent may hide its willingness to receive some items in order to obtain items of higher values. The model has applications in auctions with budgeted bidders. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Mechanism design without money generalized assignment problem Truthfulness Approximation

来源：评论

学校读者我要写书评

暂无评论

An exact method with variable fixing for solving the generalized assignment problem

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2012年第3期52卷 629-644页

作者： Posta, Marius Ferland, Jacques A. Michelon, Philippe Univ Montreal Dept Informat & Rech Operat Montreal PQ H3C 3J7 Canada Univ Avignon & Pays Vaucluse Lab Informat Avignon F-84911 Avignon 9 France

We propose a simple exact algorithm for solving the generalized assignment problem. Our contribution is twofold: we reformulate the optimization problem into a sequence of decision problems, and we apply variable-fixing rules to solve these effectively. The decision problems are solved by a simple depth-first lagrangian branch-and-bound method, improved by our variable-fixing rules to prune the search tree. These rules rely on lagrangian reduced costs which we compute using an existing but little-known dynamic programming algorithm.

关键词： Integer programming generalized assignment problem Branch and bound Lagrangian relaxation Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

A column generation heuristic for a dynamic generalized assignment problem

引用

COMPUTERS & OPERATIONS RESEARCH 2009年第9期36卷 2670-2681页

作者： Moccia, Luigi Cordeau, Jean-Francois Monaco, Maria Flavia Sammarra, Marcello Canada Res Chair Logist & Transportat Montreal PQ H3T 2A7 Canada HEC Montreal CIRRELT Montreal PQ H3T 2A7 Canada CNR Ist Calcolo & Reti Ad Alte Prestaz I-87036 Arcavacata Di Rende CS Italy Univ Calabria Dipartimento Elettron Informat & Sistemist I-87036 Arcavacata Di Rende CS Italy CR Trisaia ENEA Ente Nuove Tecnol Energia & Ambiente TER ENETEC Tecnol Usi Fnali Energia I-75026 Rotondella MT Italy

This paper studies the dynamic generalized assignment problem (DGAP) which extends the well-known generalized assignment problem by considering a discretized time horizon and by associating a starting time and a finishing time with each task. Additional constraints related to warehouse and yard management applications are also considered. Three linear integer programming formulations of the problem are introduced. The strongest one models the problem as an origin-destination integer multi-commodity flow problem with side constraints. This model can be solved quickly for instances of small to moderate size. However, because of its computer memory requirements, it becomes impractical for larger instances. Hence, a column generation algorithm is used to compute lower bounds by solving the linear program (LP) relaxation of the problem. This column generation algorithm is also embedded in a heuristic aimed at finding feasible integer solutions. Computational experiments on large-scale instances show the effectiveness of the proposed approach. (C) 2008 Elsevier Ltd. All rights reserved.

关键词： generalized assignment problem Dynamic problem Column generation Warehouse management Yard management

来源：评论

学校读者我要写书评

暂无评论

Analysis of a local search heuristic for the generalized assignment problem with resource-independent task profits and identical resource capacity

引用

ENGINEERING OPTIMIZATION 2022年第8期54卷 1426-1440页

作者： El Yafrani, Mohamed Sung, Inkyung Krach, Bernhard Katsilieris, Fotios Nielsen, Peter Aalborg Univ Operat Res Grp Aalborg Denmark Airbus Def & Space Manching Germany

In practice, allocating tasks to resources is often tackled in (near) real-time due to the latency of the task information and sudden task arrivals into a system. Therefore, the problem must be solved within a very short time budget, when tasks are urgent or idle resources are critical to the system's performance. Local search algorithms could be a good solution to this issue. These algorithms usually focus the search on limited solution areas by applying local updates on an incumbent solution. To investigate the feasibility and performance of applying a local search algorithm to resource allocation, a special case of the generalized assignment problem (GAP) is modelled, where task profits are independent of the resources assigned and resources' capacities are identical. Then the performance of a local search algorithm to the target problems is examined empirically, characterizing the features of the GAP that make the problem hard for heuristics.

关键词： generalized assignment problem iterative local search real-time decision-making resource-independent task profits identical resource capacity

来源：评论

学校读者我要写书评

暂无评论

AN APPROXIMATION ALGORITHM FOR THE generalized assignment problem

引用

MATHEMATICAL PROGRAMMING 1993年第3期62卷 461-474页

作者： SHMOYS, DB TARDOS, E School of Operations Research and Engineering Cornell University Ithaca USA

The generalized assignment problem can be viewed as the following problem of scheduling parallel machines with costs. Each job is to be processed by exactly one machine;processing job j on machine i requires time p(ij) and incurs a cost of c(ij);each machine i is available for T(i) time units, and the objective is to minimize the total cost incurred. Our main result is as follows. There is a polynomial-time algorithm that, given a value C, either proves that no feasible schedule of cost C exists, or else finds a schedule of cost at most C where each machine i is used for at most 2T(i) time units. We also extend this result to a variant of the problem where, instead of a fixed processing time p(ij) there is a range of possible processing times for each machine-job pair, and the cost linearly increases as the processing time decreases. We show that these results imply a polynomial-time 2-approximation algorithm to minimize a weighted sum of the cost and the makespan, i.e., the maximum job completion time. We also consider the objective of minimizing the mean job completion time. We show that there is a polynomial-time algorithm that, given values M and T, either proves that no schedule of mean job completion time M and makespan T exists, or else finds a schedule of mean job completion time at most M and makespan at most 2T.

关键词： APPROXIMATION ALGORITHMS generalized assignment problem SCHEDULING UNRELATED PARALLEL MACHINES

来源：评论

学校读者我要写书评

暂无评论

Solving the reliability-oriented generalized assignment problem by Lagrangian relaxation and Alternating Direction Method of Multipliers

引用

EXPERT SYSTEMS WITH APPLICATIONS 2022年 205卷

作者： Song, Maocan Cheng, Lin Southeast Univ Sch Transportat Jiangning Dist Nanjing Jiangsu Provinc Peoples R China

The well-known generalized assignment problem has many real-world applications. The assignment costs be-tween agents and tasks affected by several factors could be unstable and uncertain. In this paper, we assume that the means and variances of assignment costs are known in advance. The idea is that the decision-maker aims to minimize the total assignment costs not only on average, but also to keep their variability as small as possible. Then, a reliability-oriented model with a nonlinear and concave objective function is formulated, and two decomposition-based methods are systematically developed for this challenging problem. The task allocation constraints are dualized and the Lagrangian relaxed problem is broken into many reliability-oriented knapsack subproblems. By the Lagrangian substitution technique, each subproblem is further decomposed into a standard knapsack problem and a simple univariate concave minimization problem. A lower bound is constructed and multipliers are optimized in dual problems by the subgradient method. Feasible solutions can be generated from the results of these reliability-oriented subproblems by Lagrangian heuristic. To further improve the convergence and solution quality, an Alternating Direction Method of Multipliers (ADMM) based decomposition approach is proposed. The augmented Lagrangian relaxed problem is split into a sequence of subproblems by the block coordinate descent method. To cope with the quadratic terms and the concave terms in these subproblems, linearization and Lagrangian substitution techniques are applied. Feasible solutions are produced from these subproblems, and solution quality can be evaluated by the lower bound provided by the Lagrangian relaxed problem. Numerical experiments are conducted on the test cases transformed from the standard benchmark instances, and the ADMM-based method has superior convergence and solution quality.

关键词： generalized assignment problem Mean-standard deviation objective problem decomposition Lagrangian relaxation Alternating Direction Method of Multipliers

来源：评论

学校读者我要写书评

暂无评论

A Discrete Differential Evolution Algorithm for the Multi-Objective generalized assignment problem

引用

JOURNAL OF COMPUTATIONAL AND THEORETICAL NANOSCIENCE 2013年第12期10卷 2819-2825页

作者： Jiang, Zhong-Zhong Xia, Chao Chen, Xiaohong Meng, Xuanyu He, Qi Cent S Univ Sch Business Changsha 410083 Peoples R China Northeastern Univ Sch Business Adm Shenyang 110004 Peoples R China

In this paper, a novel discrete differential evolution (DDE) algorithm is proposed to solve the multi-objective generalized assignment problem (mGAP), which is basically concerned with finding the optimal assignment of jobs to agents such that each job is assigned to exactly one agent, subject to capacity constraint of agents, and aims to optimize multiple objective functions simultaneously, such as minimizing cost, minimizing time, and maximizing profit. First, the mGAP is described and a standard multi-objective mathematical programming model for nnGAP is given. Second, the DDE is presented, in which individuals are represented as the integer encoding scheme, and a novel integer-encoding-based dynamic mutation operator is employed to generate new candidate solutions. Furthermore, a sequential selection operator for dealing with multiple objectives is embedded in the proposed DDE. Finally, an extensive computational study is carried out by comparison with the enumeration algorithm and genetic algorithm, the results show that the proposed DDE is an effective algorithm for mGAR

关键词： generalized assignment problem Discrete Differential Evolution Multi-Objective Optimization

来源：评论

学校读者我要写书评

暂无评论

An efficient solution to biobjective generalized assignment problem

引用

ADVANCES IN ENGINEERING SOFTWARE 2007年第1期38卷 50-58页

作者： Zhang, Cai Wen Ong, Hoon Liong Natl Univ Singapore Dept Ind & Syst Engn Singapore 119260 Singapore

The generalized assignment problem (GAP) has found applications in many real world problems. In this paper, we examine the GAP from a multiobjective point of view to accommodate some real world situations where more than one objective is involved. An efficient LP-based heuristic is proposed to solve the biobjective generalized assignment problem (BiGAP). Extensive computational experiments are carried out to evaluate the performance of the proposed method. The results show that the proposed approach is able to generate good approximations to the nondominated frontier of the BiGAP efficiently, especially when the ratio of the number of items to the number of knapsacks is large. (C) 2006 Elsevier Ltd. All rights reserved.

关键词： epsilon-nondominated solution generalized assignment problem LP-based heuristic multiobjective integer programming

来源：评论

学校读者我要写书评

暂无评论

A Tabu search heuristic for the generalized assignment problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2001年第1期132卷 22-38页

作者： Díaz, JA Fernández, E Univ Politecn Cataluna Dept Estad & Invest Operat Barcelona 08028 Spain

This paper considers the generalized assignment problem (GAP). It is a well-known NP-hard combinatorial optimization problem that is interesting in itself and also appears as a subproblem in other problems of practical importance. A Tabu search heuristic for the GAP is proposed. The algorithm uses recent and medium-term memory to dynamically adjust the weight of the penalty incurred for violating feasibility. The most distinctive features of the proposed algorithm are its simplicity and its flexibility. These two characteristics result in an algorithm that, compared to other well-known heuristic procedures, provides good quality solutions in competitive computational times. Computational experiments have been performed in order to evaluate the behavior of the proposed algorithm. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： generalized assignment problem metaheuristics Tabu search local search

来源：评论

学校读者我要写书评

暂无评论

Independent and cooperative parallel search methods for the generalized assignment problem

引用

OPTIMIZATION METHODS & SOFTWARE 2003年第2期18卷 129-141页

作者： Asahiro, Y Ishibashi, M Yamashita, M Kyushu Sangyo Univ Dept Social Informat Syst Fac Informat Sci Higashi Ku Fukuoka 8138503 Japan Kyushu Univ Dept Comp Sci & Commun Engn Grad Sch Informat Sci & Elect Engn Higashi Ku Fukuoka 8128581 Japan

The generalized assignment problem is a representative NP-hard problem, for which many heuristic algorithms are known. In this article, two parallel heuristic algorithms are proposed, which are based on the ejection chain local search (EC) proposed by Yagiura et al. One is a simple parallelization called multistart parallel EC (MPEC) and the other is cooperative parallel EC (CPEC). In MPEC each search process independently explores search space while in CPEC search processes share partial information to cooperate with each other. The experimental results with 9 computers for large benchmark instances show that (1) MPEC and CPEC, respectively, run twice and 4 times faster than EC, and (2) compared to EC, the difference in quality between obtained solutions and theoretical lower bounds is reduced to 3/4 and 2/3 by MPEC and CPEC, respectively. It is said that these methods give us full benefit of parallelization, speedup and improvement for quality of solutions.

关键词： generalized assignment problem heuristics local search parallel algorithm PC cluster

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：