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

Bicriteria Multiresource generalized assignment problem

NAVAL RESEARCH LOGISTICS 2014年第8期61卷 621-636页

作者： Karsu, Ozlem Azizoglu, Meral Bilkent Univ Dept Ind Engn TR-06800 Ankara Turkey Middle E Tech Univ Dept Ind Engn TR-06531 Ankara Turkey

In this study, we consider a bicriteria multiresource generalized assignment problem. Our criteria are the total assignment load and maximum assignment load over all agents. We aim to generate all nondominated objective vectors and the corresponding efficient solutions. We propose several lower and upper bounds and use them in our optimization and heuristic algorithms. The computational results have shown the satisfactory behaviors of our approaches. (c) 2014 Wiley Periodicals, Inc. Naval Research Logistics, 61: 621-636, 2014

关键词： generalized assignment problem linear programming relaxation branch and bound heuristics

来源：评论

学校读者我要写书评

暂无评论

A computational study of exact knapsack separation for the generalized assignment problem

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2010年第3期45卷 543-555页

作者： Avella, Pasquale Boccia, Maurizio Vasilyev, Igor Russian Acad Sci Inst Syst Dynam & Control Theory Siberian Branch Irkutsk 664033 Russia Univ Sannio Res Ctr Software Technol I-82100 Benevento Italy

The generalized assignment problem is a well-known NP-hard combinatorial optimization problem which consists of minimizing the assignment costs of a set of jobs to a set of machines satisfying capacity constraints. Most of the existing algorithms are of a Branch-and-Price type, with lower bounds computed through Dantzig-Wolfe reformulation and column generation. In this paper we propose a cutting plane algorithm working in the space of the variables of the basic formulation, whose core is an exact separation procedure for the knapsack polytopes induced by the capacity constraints. We show that an efficient implementation of the exact separation procedure allows to deal with large-scale instances and to solve to optimality several previously unsolved instances.

关键词： generalized assignment problem Cutting plane algorithm Exact separation

来源：评论

学校读者我要写书评

暂无评论

A hybrid tabu search/branch & bound approach to solving the generalized assignment problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2010年第2期207卷 566-578页

作者： Woodcock, Andrew J. Wilson, John M. Univ Nottingham Sch Business Nottingham NG8 1BB England Univ Loughborough Loughborough LE11 3TU Leics England Aberystwyth Univ Aberystwyth SY23 2DD Dyfed Wales

A new approach for solving the generalized assignment problem (GAP) is proposed that combines the exact branch & bound approach with the heuristic strategy of tabu search (TS) to produce a hybrid algorithm for solving GAP. The algorithm described uses commercial software to solve sub-problems generated by the TS guiding strategy. The TS approach makes use of the concept of referent domain optimisation and introduces novel add/drop strategies. In addition, the linear programming relaxation of GAP that forms part of the branch & bound approach is itself helpful in suggesting which variables might take binary values. Computational results on benchmark test instances are presented and compared with results obtained by the standard branch & bound approach and also several other heuristic approaches from the literature. The results show the new algorithm performs competitively against the alternatives and is able to find some new best solutions for several benchmark instances. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Integer programming Tabu search Branch and bound generalized assignment problem

来源：评论

学校读者我要写书评

暂无评论

Performance analysis of swarm optimization approaches for the generalized assignment problem in multi-target tracking applications

引用

TURKISH JOURNAL OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCES 2010年第6期18卷 1059-1076页

作者： Bozdogan, Ali Onder Yilmaz, Asim Egemen Efe, Murat Ankara Univ Fac Engn Dept Elect Engn TR-06100 Ankara Turkey

The aim of this study is to investigate the suitability of selected swarm optimization algorithms to the generalized assignment problem as encountered in multi-target tracking applications. For this purpose, we have tested variants of particle swarm optimization and ant colony optimization algorithms to solve the 2D generalized assignment problem with simulated dense and sparse measurement/track matrices and compared their performance to that of the auction algorithm. We observed that, although with some modification swarm optimization algorithms provide improvement in terms of speed, they still fall behind the auction algorithm in finding the optimum solution to the problem. Among the investigated colony optimization approaches, the particle swarm optimization algorithm using the proposed 1-opt local search was found to perform better than other modifications. On the other hand, it is assessed that swarm optimization algorithms might be powerful tools for multiple hypothesis target tracking applications at noisy environments, since within single execution they provide a set of numerous good solutions to the assignment problem.

关键词： generalized assignment problem ant colony optimization particle swarm optimization data association target tracking

来源：评论

学校读者我要写书评

暂无评论

Improved differential evolution algorithms for solving generalized assignment problem

引用

EXPERT SYSTEMS WITH APPLICATIONS 2016年 45卷 450-459页

作者： Sethanan, Kanchana Pitakaso, Rapeepan Khon Kaen Univ Fac Engn Dept Ind Engn Res Unit Syst Modeling Ind Khon Kaen 40002 Thailand Ubon Ratchathani Univ Fac Engn Dept Ind Engn Metaheurist Logist Optimizat Lab Ubon Ratchathani Thailand

This paper presents algorithms based on differential evolution (DE) to solve the generalized assignment problem (GAP) with the objective to minimize the assignment cost under the limitation of the agent capacity. Three local search techniques: shifting, exchange, and k-variable move algorithms are added to the DE algorithm in order to improve the solutions. Eight DE-based algorithms are presented, each of which uses DE with a different combination of local search techniques. The experiments are carried out using published standard instances from the literature. The best proposed algorithm using shifting and k-variable move as the local search (DE-SK) techniques was used to compare its performance with those of Bee algorithm (BEE) and Tabu search algorithm (TABU). The computational results revealed that the BEE and DE-SK are not significantly different while the DE-SK outperforms the TABU algorithm. However, even though the statistical test shows that DE-SK is not significantly different compared with the BEE algorithm, the DE-SK is able to obtain more optimal solutions (87.5%) compared to the BEE algorithm that can obtain only 12.5% optimal solutions. This is because the DE-SK is designed to enhance the search capability by improving the diversification using the DE's operators and the k-variable moves added to the DE can improve the intensification. Hence, the proposed algorithms, especially the DE-SK, can be used to solve various practical cases of GAP and other combinatorial optimization problems by enhancing the solution quality, while still maintaining fast computational time. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： generalized assignment problem Differential evolution algorithm Shifting procedure Exchange procedure

来源：评论

学校读者我要写书评

暂无评论

An LP-based metaheuristic procedure for the k-sequential generalized assignment problem

引用

OPTIMIZATION METHODS & SOFTWARE 2011年第2期26卷 225-238页

作者： French, A. P. Nygreen, B. Wilson, J. M. Univ Loughborough Sch Business Loughborough Leics England Norwegian Univ Sci & Technol Dept Ind Econ & Technol Management N-7034 Trondheim Norway Aberystwyth Univ Sch Business & Management Aberystwyth Dyfed Wales

The k-sequential generalized assignment problem (GAPkSeq) is a problem of allocating tasks to time periods, where each of n tasks must be assigned to k sequential time periods out of a total of m. Using standard mathematical programming software, GAPkSeq becomes intractable for relatively small values of k, m and n;hence there is a need for heuristic algorithms to solve such problems. It is shown how a heuristic combining both divide-and-conquer and a linear programming-based heuristic developed previously for the generalized assignment problem with special ordered sets can be modified and extended to solve GAPkSeq. Encouraging results in terms of speed and accuracy are described.

关键词： generalized assignment problem metaheuristics local search linear programming divide and conquer

来源：评论

学校读者我要写书评

暂无评论

An ejection chain approach for the generalized assignment problem

引用

INFORMS JOURNAL ON COMPUTING 2004年第2期16卷 133-151页

作者： Yagiura, M Ibaraki, T Glover, F Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto 6068501 Japan Univ Colorado Leeds Sch Business Boulder CO 80309 USA

We propose a tabu search algorithm for the generalized assignment problem, which is one of the representative combinatorial optimization problems known to be NP-hard. The algorithm features an ejection chain approach, which is embedded in a neighborhood construction to create more complex and powerful moves. We also incorporate an adaptive mechanism for adjusting search parameters, to maintain a balance between visits to feasible and infeasible regions. Computational results on benchmark instances of small sizes show that the method obtains solutions that are optimal or that deviate by at most 0.16% from the best known solutions. Comparisons with other approaches from the literature show that, for instances of larger sizes, our method obtains the best solutions among all heuristics tested.

关键词： generalized assignment problem ejection chain adaptive parameter adjustment metaheuristics tabu search local search

来源：评论

学校读者我要写书评

暂无评论

Relaxation heuristics for a generalized assignment problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1996年第3期91卷 600-610页

作者： Lorena, LAN Narciso, MG INST NACL PESQUISAS ESPACIAIS LAB ASSOCIADO COMPUTACAO & MATEMAT APLICADACAIXA POSTAL 515BR-12201 S JOSE CAMPOSSPBRAZIL

We propose relaxation heuristics for the problem of maximum profit assignment of n tasks to m agents (n > m), such that each task is assigned to only one agent subject to capacity constraints on the agents. Using Lagrangian or surrogate relaxation, the heuristics perform a subgradient search obtaining feasible solutions. Relaxation considers a vector of multipliers for the capacity constraints. The resolution of the Lagrangian is then immediate. For the surrogate, the resulting problem is a multiple choice knapsack that is again relaxed for continuous values of the variables, and solved in polynomial time. Relaxation multipliers are used with an improved heuristic of Martello and Toth or a new constructive heuristic to find good feasible solutions. Sh heuristics are tested with problems of the literature and random generated problems. Best results are less than 0.5% from the optimal, with reasonable computational times for an AT/386 computer. It seems promising even for problems with correlated coefficients.

关键词： heuristics Lagrangian and surrogate relaxation generalized assignment problem

来源：评论

学校读者我要写书评

暂无评论

HEURISTICS FOR THE generalized assignment problem - SIMULATED ANNEALING AND TABU SEARCH APPROACHES

引用

OR SPEKTRUM 1995年第4期17卷 211-225页

作者： OSMAN, IH UNIV KENT INST MATH & STAT CANTERBURY CT2 7NF KENT ENGLAND

The generalised assignment problem (GAP) is the problem of finding a minimum cost assignment of a set of jobs to a set of agents. Each job is assigned to exactly one agent. The total demands of all jobs assigned to any agent can not exceed the total resources available to that agent. A review of exact and heuristic methods is presented. A lambda-generation mechanism is introduced. Different search strategies and parameter settings are investigated for the lambda-generation descent, hybrid simulated annealing/tabu search and tabu search heuristic methods. The developed methods incorporate a number of features that have proven useful for obtaining optimal and near optimal solutions. The effectiveness of our approaches is established by comparing their performance in terms of solution quality and computional requirement to other specialized branch-and-bound tree search, simulated annealing and set partitioning heuristics on a set of standard problems from the literature.

关键词： generalized assignment problem LOCAL SEARCH SIMULATED ANNEALING TABU SEARCH HEURISTICS SET PARTITIONING BRANCH AND BOUND

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：