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

A Truthful Mechanism for the generalized assignment problem

ACM TRANSACTIONS ON ECONOMICS AND COMPUTATION 2017年第3期5卷 1–18页

作者： Fadaei, Salman Bichler, Martin Frankfurter Ring 105A D-80807 Munich Germany Tech Univ Munich Dept Informat Boltzmannstr 3 D-85748 Munich Germany

We propose a truthful-in-expectation, (1 - 1/e)-approximation mechanism for a strategic variant of the generalized assignment problem (GAP). 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 the strategic variant of the problem we study, values for assigning items to bins are the private information of bidders and the mechanism should provide bidders with incentives to truthfully report their values. The approximation ratio of the mechanism is a significant improvement over the approximation ratio of the existing truthful mechanism for GAP. The proposed mechanism comprises a novel convex optimization program as the allocation rule as well as an appropriate payment rule. To implement the convex program in polynomial time, we propose a fractional local search algorithm which approximates the optimal solution within an arbitrarily small error leading to an approximately truthful-in-expectation mechanism. The proposed algorithm improves upon the existing optimization algorithms for GAP in terms of simplicity and runtime while the approximation ratio closely matches the best approximation ratio known for GAP when all inputs are publicly known.

关键词： generalized assignment problem mechanism design truthful-in-expectation convex optimization

来源：评论

学校读者我要写书评

暂无评论

(1,K)-CONFIGURATION FACETS FOR THE generalized assignment problem

引用

MATHEMATICAL PROGRAMMING 1990年第1期46卷 53-60页

作者： GOTTLIEB, ES RAO, MR NYU STERN SCH BUSINESSNEW YORKNY 10003

class of facet defining inequalities for the generalized assignment problem is derived. These inequalities are based upon multiple knapsack constraints and are derived from (1,k)-configuration inequalities.

关键词： (1, k)-configurations facets generalized assignment problem integer polytope knapsack problem special ordered sets

来源：评论

学校读者我要写书评

暂无评论

A hybrid heuristic algorithm for the sequencing generalized assignment problem in an assembly line

引用

IFAC-PapersOnLine 2018年第2期51卷 695-700页

作者： Moussavi, S.E. Mahdjoub, M. Grunder, O. Nanomedicine lab Univ. Bourgogne Franche-Comté UTBM BelfortF-90010 France ELLIADD Lab Univ. Bourgogne Franche-Comté UTBM Montbéliard25200 France

The generalized assignment problem (GAP) is an enlarged version of the classical assignment problem in which the assignment of several tasks to an agent is possible. The only restriction that can limit the assignment of the tasks to the agents is the capacity of the agent. In this study, a manpower planning is modeled as a GAP in an assembly line. The considered assembly line consists of a number of workstations in series where each workstation contains several jobs in parallel. The present research seeks to assign the best operator to the jobs in order to minimize the processing time in each workstation and in the whole of the system. The generalized assignment formulation is adapted to this case. A mixed-integer mathematical model is proposed for this problem and proved that the considered problem is NP-complete. The model is solved in various sizes by employing Gurobi mixed-integer solver. This paper presents a greedy heuristic combined with a local search for the generalized assignment problem. The slight deviation from the optimal solutions and the computational times which is extremely reduced, validate the efficiency of the proposed heuristic approach for solving such problems. © 2018

关键词： problem solving Assembly Assembly machines Combinatorial optimization Heuristic algorithms Heuristic methods assignment problems Computational time generalized assignment problem generalized assignments Greedy heuristics Heuristic approach Hybrid heuristic algorithms Optimal solutions

来源：评论

学校读者我要写书评

暂无评论

A transportation branch and bound algorithm for solving the generalized assignment problem

引用

INTERNATIONAL JOURNAL OF SYSTEM ASSURANCE ENGINEERING AND MANAGEMENT 2015年第3期6卷 217-223页

作者： Munapo, Elias Lesaoana, 'Maseka Nyamugure, Philimon Kumar, Santosh Univ KwaZulu Natal Grad Sch Business & Leadership Westville Campus Durban South Africa Univ Limpopo Dept Stat & Operat Res ZA-0727 Sovenga South Africa Natl Univ Sci & Technol Dept Stat & Operat Res Bulawayo Zimbabwe Univ Melbourne Dept Math & Stat Parkville Vic Australia

This paper presents a transportation branch and bound algorithm for solving the generalized assignment problem. This is a branch and bound technique in which the sub-problems are solved by the available efficient transportation techniques rather than the usual simplex based approaches. A technique for selecting branching variables that minimize the number of sub-problems is also presented.

关键词： generalized assignment problem Branch and bound method Transportation model

来源：评论

学校读者我要写书评

暂无评论

THE generalized assignment problem - VALID INEQUALITIES AND FACETS

引用

MATHEMATICAL PROGRAMMING 1990年第1期46卷 31-52页

作者： GOTTLIEB, ES RAO, MR NYU STERN SCH BUSINESSNEW YORKNY 10003

Three classes of valid inequalities based upon multiple knapsack constraints are derived for the generalized assignment problem. General properties of the facet defining inequalities are discussed and, for a special case, the convex hull is completely characterized. In addition, we prove that a basic fractional solution to the linear programming relaxation can be eliminated by a facet defining inequality associated with an individual knapsack constraint.

关键词： facets generalized assignment problem integer polytope knapsack problem special ordered sets

来源：评论

学校读者我要写书评

暂无评论

Novel parallel hybrid genetic algorithms on the GPU for the generalized assignment problem

引用

JOURNAL OF SUPERCOMPUTING 2022年第1期78卷 144-167页

作者： Huang Zhi-Bin Fu Guang-Tao Dong Dan-Yang Xiao Chen Ding Zhe-Lun Dai Zhi-Tao Beijing Univ Posts & Telecommun BUPT Sch Comp Sci Beijing Key Lab Intelligent Telecommun Software & Beijing 100876 CO Peoples R China

The emergence of GPU-CPU heterogeneous architecture has led to a significant paradigm shift in parallel programming. How to effectively implement Parallel Genetic Algorithm (GA) in these environments has become one of the current hot issues. GA's calculation and operators are closely related to specific problems, thereby significantly affecting the acceleration method of GA algorithms. The generalized assignment problem (GAP) is a classic NP-hard combinatorial optimization problem. The more widely used genetic algorithms to solve the GAP in the CPU are difficult to be parallelized in a GPU environment due to severe data dependencies. To address this problem, two algorithms suitable for the implementation on the GPU are proposed, namely RPE algorithm and NNE algorithm, which obtain significant performance speedup by alleviating data dependencies and mutually exclusive synchronization overheads. At the same time, considering the new GPU architecture features and programming models, three different granular implementations of parallel genetic algorithms to solve the GAP are proposed, namely GPGA(thread), GPGA(warpsp) and GPGA(cgroup), by utilizing the warp-specialization technology and the cooperative group mechanism. GPGA series algorithms obtain better solution quality and very significant performance improvements compared with Serial GA, GTS (the GPU-CPU hybrid implementation of Scatter Search with Tabu lists) and Lagrange Relaxation algorithm on a CPU by solving 16 typical large-scale GAP instances.

关键词： Parallel genetic algorithms GPU Warp specialization Cooperative group generalized assignment problem

来源：评论

学校读者我要写书评

暂无评论

TABU SEARCH FOR THE MULTILEVEL generalized assignment problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1995年第1期82卷 176-189页

作者： LAGUNA, M KELLY, JP GONZALEZVELARDE, JL GLOVER, F UNIV COLORADO GRAD SCH BUSINESS & ADMBOULDERCO 80309 ITESM CTR SISTEMAS MFGMEXICO CITY 64849MEXICO

The multilevel generalized assignment problem (MGAP) differs from the classical GAP in that agents can perform tasks at more than one efficiency level. Important manufacturing problems, such as lot sizing, can be formulated as MGAPs;however, the large number of variables in the related 0-1 integer program makes the use of commercial optimization packages impractical. In this paper, we present a heuristic approach to the solution of the MGAP, which consists of a novel application of tabu search (TS). Our TS method employs neighborhoods defined by ejection chains, that produce moves of greater power without significantly increasing the computational effort.

关键词： TABU SEARCH generalized assignment problem LOT SIZING RESOURCE ALLOCATION

来源：评论

学校读者我要写书评

暂无评论

A SET PARTITIONING HEURISTIC FOR THE generalized assignment problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1994年第1期72卷 167-174页

作者： CATTRYSSE, DG SALOMON, M VANWASSENHOVE, LN ERASMUS UNIV ROTTERDAM POB 1738 3000 DR ROTTERDAM NETHERLANDS KATHOLIEKE UNIV LEUVEN B-3001 LOUVAIN BELGIUM INSEAD F-77305 FONTAINEBLEAU FRANCE

This paper discusses a heuristic for the generalized assignment problem (GAP). The objective of GAP is to minimize the costs of assigning J jobs to M capacity constrained machines, such that each job is assigned to exactly one machine. The problem is known to be NP-Hard, and it is hard from a computational point of view as well. The heuristic proposed here is based on column generation techniques, and yields both upper and lower bounds. On a set of relatively hard test problems the heuristic is able to find solutions that are on average within 0.13% from optimality.

关键词： generalized assignment problem SET PARTITIONING COLUMN GENERATION DUAL ASCENT

来源：评论

学校读者我要写书评

暂无评论

ALGORITHMS FOR THE MULTI-RESOURCE generalized assignment problem

引用

MANAGEMENT SCIENCE 1991年第6期37卷 695-713页

作者： GAVISH, B PIRKUL, H OHIO STATE UNIV COLL BUSINESSCOLUMBUSOH 43210

The multi-resource generalized assignment problem is encountered when a set of tasks have to be assigned to a set of agents in a way that permits assignment of multiple tasks to an agent subject to the availability of a set of multiple resources consumed by that agent. This problem differs from the generalized assignment problem in that an agent consumes not just one but a variety of resources in performing the tasks assigned to him. This paper develops effective solution procedures for the multi-resource generalized assignment problem. Various relaxations of the problem are studied and theoretical relations among these relaxations are pointed out. Rules for reducing problem size are discussed and are shown to be effective through computational experiments. Heuristic solution procedures and an efficient branch and bound procedure are developed. Results of computational experiments testing these procedures are reported.

关键词： combinatorial optimization Lagrangian relaxation subgradient optimization generalized assignment problem

来源：评论

学校读者我要写书评

暂无评论

Algorithms for the Min-max Regret generalized assignment problem with Interval Data

Algorithms for the Min-max Regret Generalized Assignment Pro...

引用

IEEE International Conference on Industrial Engineering and Engineering Management

作者： Wu, W. Iori, M. Martello, S. Yagiura, M. Nagoya Univ Nagoya Aichi Japan Univ Modena & Reggio Emilia Reggio Emilia Italy Univ Bologna Bologna Italy

ISBN: (纸本)9781479964109

Many real life optimization problems do not have accurate estimates of the problem parameters at the optimization phase. For this reason, the min-max regret criteria are widely used to obtain robust solutions. In this paper we consider the generalized assignment problem (GAP) with min-max regret criterion under interval costs. We show that the decision version of this problem is Sigma(p)(2)-complete. We present two heuristic methods: a fixed-scenario approach and a dual substitution algorithm. For the fixed-scenario approach, we show that solving the classical GAP under a median-cost scenario leads to a solution of the min-max regret GAP whose objective function value is within twice the optimal value. We also propose exact algorithms, including a Benders' decomposition approach and branch-and-cut methods which incorporate various methodologies, including Lagrangian relaxation and variable fixing. The resulting Lagrangian-based branch-and-cut algorithm performs satisfactorily on benchmark instances.

关键词： generalized assignment problem min-max regret branch-and-cut Benders' decomposition variable fixing Lagrangian relaxation heuristics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：