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

A branch-and-price approach for the stochastic generalized assignment problem

NAVAL RESEARCH LOGISTICS 2014年第2期61卷 131-143页

作者： Sarin, Subhash C. Sherali, Hanif D. Kim, Seon Ki Virginia Tech Grado Dept Ind & Syst Engn 0118 Blacksburg VA 24061 USA

In this article, we address a stochastic generalized assignment machine scheduling problem in which the processing times of jobs are assumed to be random variables. We develop a branch-and-price (B&P) approach for solving this problem wherein the pricing problem is separable with respect to each machine, and has the structure of a multidimensional knapsack problem. In addition, we explore two other extensions of this method-one that utilizes a dual-stabilization technique and another that incorporates an advanced-start procedure to obtain an initial feasible solution. We compare the performance of these methods with that of the branch-and-cut (B&C) method within CPLEX. Our results show that all B&P-based approaches perform better than the B&C method, with the best performance obtained for the B&P procedure that includes both the extensions aforementioned. We also utilize a Monte Carlo method within the B&P scheme, which affords the use of a small subset of scenarios at a time to estimate the "true" optimal objective function value. Our experimental investigation reveals that this approach readily yields solutions lying within 5% of optimality, while providing more than a 10-fold savings in CPU times in comparison with the best of the other proposed B&P procedures. (c) 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 131-143, 2014

关键词： branch-and-price Monte Carlo method generalized assignment problem stochastic programming

来源：评论

学校读者我要写书评

暂无评论

A path relinking approach with ejection chains for the generalized assignment problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2006年第2期169卷 548-569页

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

The generalized assignment problem is a classical combinatorial optimization problem known to be NP-hard. It can model a variety of real world applications in location, allocation, machine assignment, and supply chains. The problem has been studied since the late 1960s, and computer codes for practical applications emerged in the early 1970s. We propose a new algorithm for this problem that proves to be more effective than previously existing methods. The algorithm features a path relinking approach, which is a mechanism for generating new solutions by combining two or more reference solutions. It also features an ejection chain approach, which is embedded in a neighborhood construction to create more complex and powerful moves. Computational comparisons on benchmark instances show that the method is not only effective in general, but is especially effective for types D and E instances, which are known to be very difficult. (c) 2004 Elsevier B.V. All rights reserved.

关键词： metaheuristics scatter search path relinking ejection chains generalized assignment problem

来源：评论

学校读者我要写书评

暂无评论

A modified genetic algorithm for a special case of the generalized assignment problem

引用

TURKISH JOURNAL OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCES 2017年第2期25卷 794-805页

作者： Dorterler, Murat Bay, Omer Faruk Akcayol, Mehmet Ali Gazi Univ Dept Comp Engn Ankara Turkey Gazi Univ Dept Elect & Elect Engn Ankara Turkey Gazi Univ Dept Comp Engn Ankara Turkey

Many central examinations are performed nationwide in Turkey. These examinations are held simultaneously throughout Turkey. Examinees attempt to arrive at the examination centers at the same time and they encounter problems such as traffic congestion, especially in metropolises. The state of mind that this situation puts them into negatively affects the achievement and future goals of the test takers. Our solution to minimize the negative effects of this issue is to assign the test takers to closest examination centers taking into account the capacities of examination halls nearby. This solution is a special case of the generalized assignment problem (GAP). Since the scale of the problem is quite large, we have focused on heuristic methods. In this study, a modified genetic algorithm (GA) is used for the solution of the problem since the classical GA often generates infeasible solutions when it is applied to GAPs. A new method, named nucleotide exchange, is designed in place of the crossover method. The designed method is run between the genes of a single parent chromosome. In addition to the randomness, the consciousness factor is taken into consideration in the mutation process. With this new GA method, results are obtained successfully and quickly in large-sized data sets.

关键词： Genetic algorithm optimization generalized assignment problem

来源：评论

学校读者我要写书评

暂无评论

The equilibrium generalized assignment problem and genetic algorithm

引用

APPLIED MATHEMATICS AND COMPUTATION 2012年第11期218卷 6526-6535页

作者： Liu, Linzhong Mu, Haibo Song, Yubo Luo, Haiyan Li, Xiaojing Wu, Fang Lanzhou Jiaotong Univ Sch Traff & Transportat Lanzhou 730070 Peoples R China Lanzhou Jiaotong Univ Mechatron Technol Inst Lanzhou 730070 Peoples R China

The well-known generalized assignment problem (GAP) is to minimize the costs of assigning n jobs to m capacity constrained agents (or machines) such that each job is assigned to exactly one agent. This problem is known to be NP-hard and it is hard from a computational point of view as well. In this paper, follows from practical point of view in real systems, the GAP is extended to the equilibrium generalized assignment problem (EGAP) and the equilibrium constrained generalized assignment problem (ECGAP). A heuristic equilibrium strategy based genetic algorithm (GA) is designed for solving the proposed EGAP. Finally, to verify the computational efficiency of the designed GA, some numerical experiments are performed on some known benchmarks. The test results show that the designed GA is very valid for solving EGAP. (C) 2011 Elsevier Inc. All rights reserved.

关键词： assignment problem Equilibrium optimization generalized assignment problem Genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

Heuristics for the multi-resource generalized assignment problem

引用

NAVAL RESEARCH LOGISTICS 2001年第6期48卷 468-483页

作者： Mazzola, JB Wilcox, SP Georgetown Univ McDonough Sch Business Washington DC 20057 USA Logicon Inc Arlington VA 22204 USA

The well-known generalized assignment problem (GAP) involves the identification of a minimum-cost assignment of tasks to agents when each agent is constrained by a resource in limited supply. The multi-resource generalized assignment problem (MRGAP) is the generalization of the GAP in which there are a number of different potentially constraining resources associated with each agent. This paper explores heuristic procedures for the MRGAP. We first define a three-phase heuristic which seeks to construct a feasible solution to MRGAP and then systematically attempts to improve the solution. We then propose a modification of the heuristic for the MRGAP defined previously by Gavish and Pirkul. The third procedure is a hybrid heuristic that combines the first two heuristics, thus capturing their relative strengths. We discuss extensive computational experience with the heuristics. The hybrid procedure is seen to be extremely effective in solving MRGAPs, generating feasible solutions to more than 99% of the test problems and consistently producing near-optimal solutions. (C) 2001 John Wiley & Sons, Inc.

关键词： 0-1 integer programming generalized assignment problem heuristics

来源：评论

学校读者我要写书评

暂无评论

A class of greedy algorithms for the generalized assignment problem

引用

DISCRETE APPLIED MATHEMATICS 2000年第1-3期103卷 209-235页

作者： Romeijn, HE Morales, DR Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA Erasmus Univ Rotterdam Sch Management NL-3000 DR Rotterdam Netherlands

The generalized assignment problem (GAP) is the problem of finding the minimal cost assignment of jobs to machines such that each job is assigned to exactly one machine, subject to capacity restrictions on the machines. We propose a class of greedy algorithms for the GAP. A family of weight functions is defined to measure a pseudo-cost of assigning a job to a machine. This weight function in turn is used to measure the desirability of assigning each job to each of the machines. The greedy algorithm then schedules jobs according to a decreasing order of desirability. A relationship with the partial solution given by the LP-relaxation of the GAP is found, and we derive conditions under which the algorithm is asymptotically optimal in a probabilistic sense. (C) 2000 Elsevier Science B.V, All rights reserved.

关键词： generalized assignment problem greedy heuristic asymptotic feasibility asymptotic optimality

来源：评论

学校读者我要写书评

暂无评论

A probabilistic feasibility and value analysis of the generalized assignment problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2000年第3期4卷 325-355页

作者： Romeijn, HE Piersma, N Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA Erasmus Univ Inst Econometr NL-3000 DR Rotterdam Netherlands

We study the generalized assignment problem, under a probabilistic model for its cost and requirement parameters. First we address the issue of feasibility by deriving a tight condition on the probabilistic model that ensures that the corresponding problem instances are feasible with probability one as the number of jobs goes to infinity. Then, under an additional condition on the parameters, we show that the optimal solution value, normalized by dividing by the number of jobs, converges with probability one to a constant, again as the number of jobs goes to infinity. Finally, we discuss various examples.

关键词： generalized assignment problem probabilistic model empirical processes

来源：评论

学校读者我要写书评

暂无评论

An efficient approximation for the generalized assignment problem

引用

INFORMATION PROCESSING LETTERS 2006年第4期100卷 162-166页

作者： Cohen, Reuven Katzir, Liran Raz, Danny Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

We present a simple family of algorithms for solving the generalized assignment problem (GAP). Our technique is based on a novel combinatorial translation of any algorithm for the knapsack problem into an approximation algorithm for GAP If the approximation ratio of the knapsack algorithm is alpha and its running time is O(f (N)), our algorithm guarantees a (1 + alpha)-approximation ratio, and it runs in O(M . f (N) + M . N), where N is the number of items and M is the number of bins. Not only does our technique comprise a general interesting framework for the GAP problem;it also matches the best combinatorial approximation for this problem, with a much simpler algorithm and a better running time. (c) 2006 Elsevier B.V. All rights reserved.

关键词： generalized assignment problem local ratio approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Bees algorithm for generalized assignment problem

引用

APPLIED MATHEMATICS AND COMPUTATION 2010年第11期215卷 3782-3795页

作者： Ozbakir, Lale Baykasoglu, Adil Tapkan, Pinar Gaziantep Univ Dept Ind Engn Gaziantep Turkey Erciyes Univ Dept Ind Engn Kayseri Turkey

Bees algorithm (BA) is a new member of meta-heuristics. BA tries to model natural behavior of honey bees in food foraging. Honey bees use several mechanisms like waggle dance to optimally locate food sources and to search new ones. This makes them a good candidate for developing new algorithms for solving optimization problems. In this paper a brief review of BA is first given, afterwards development of a BA for solving generalized assignment problems (GAP) with an ejection chain neighborhood mechanism is presented. GAP is a NP-hard problem. Many meta-heuristic algorithms were proposed for its solution. So far BA is generally applied to continuous optimization. In order to investigate the performance of BA on a complex integer optimization problem, an attempt is made in this paper. An extensive computational study is carried out and the results are compared with several algorithms from the literature. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Meta-heuristics Bees algorithm generalized assignment problem Ejection chain Integer programming Swarm intelligence

来源：评论

学校读者我要写书评

暂无评论

A scalable parallel genetic algorithm for the generalized assignment problem

引用

PARALLEL COMPUTING 2015年 46卷 98-119页

作者： Liu, Yan Y. Wang, Shaowen Univ Illinois CyberGIS Ctr Adv Digital & Spatial Studies Urbana IL 61801 USA Univ Illinois CyberInfrastruct & Geospatial Informat Lab CIGI Urbana IL 61801 USA Univ Illinois Dept Geog & Geog Informat Sci Urbana IL 61801 USA Univ Illinois Natl Ctr Supercomp Applicat Urbana IL 61801 USA Univ Illinois Dept Comp Sci Urbana IL 61801 USA Univ Illinois Dept Urban & Reg Planning Urbana IL 61801 USA

Known as an effective heuristic for finding optimal or near-optimal solutions to difficult optimization problems, a genetic algorithm (GA) is inherently parallel for exploiting high performance and parallel computing resources for randomized iterative evolutionary computation. It remains to be a significant challenge, however, to devise parallel genetic algorithms (PGAs) that can scale to massively parallel computer architecture (also known as the mainstream supercomputer architecture) primarily because: (1) a common PGA design adopts synchronized migration, which becomes increasingly costly as more processor cores are involved in global synchronization; and (2) asynchronous PGA design and associated performance evaluation are intricate due to the fact that PGA is a type of stochastic algorithm and the amount of computation work needed to solve a problem is not simply dependent on the problem size. To address the challenge, this paper describes a scalable coarse-grained PGA–PGAP, for a well-known NP-hard optimization problem: generalized assignment problem (GAP). Specifically, an asynchronous migration strategy is developed to enable efficient deme interactions and significantly improve the overlapping of computation and communication. Buffer overflow and its relationship with migration parameters were investigated to resolve the issues of observed message buffer overflow and the loss of good solutions obtained from migration. Two algorithmic conditions were then established to detect these issues caused by communication delays and improper configuration of migration parameters and, thus, guide the dynamic tuning of PGA parameters to detect and avoid these issues. A set of computational experiments is designed to evaluate the scalability and numerical performance of PGAP. These experiments were conducted for large GAP instances on multiple supercomputers as part of the National Science Foundation Extreme Science and Engineering Discovery Environment (XSEDE). Results

关键词： generalized assignment problem Genetic algorithm Heuristics Parallel and distributed computing Scalability

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：