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

Minimizing flowtime in a flowshop scheduling problem with a biased random-key genetic algorithm

EXPERT SYSTEMS WITH APPLICATIONS 2019年第0期128卷 67-80页

作者： Andrade, Carlos E. Silva, Thuener Pessoa, Luciana S. AT&T Labs Res 200 South Laurel Ave Middletown NJ 07748 USA PUC Rio Dept Ind Engn Rua Marques Sao Vicente 225 BR-22453900 Gavea Rio De Janeiro RJ Brazil

In this paper, we advance the state of the art for solving the Permutation Flowshop Scheduling Problem with total flowtime minimization. For this purpose, we propose a biased random-key genetic algorithm (BRKGA) introducing on it a new feature called shaking. With the shaking, instead to full reset the population to escape from local optima, the shaking procedure perturbs all individuals from the elite set and resets the remaining population. We compare results for the standard and the shaking BRKGA with results from the Iterated Greedy Search, the Iterated Local Search, and a commercial mixed integer programming solver, in 120 traditional instances. For all algorithms, we use warm start solutions produced by the state-of-the-art Beam-Search procedure. Computational experiments show the efficiency of proposed BRKGA, in addition to identify lower and upper bounds, as well as some optimal values, among the solutions. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： Flowshop scheduling biased random-key genetic algorithm Metaheuristics

来源：评论

学校读者我要写书评

暂无评论

A biased random-key genetic algorithm for the capacitated minimum spanning tree problem

引用

COMPUTERS & OPERATIONS RESEARCH 2015年第May期57卷 95-108页

作者： Ruiz, Efrain Albareda-Sambola, Maria Fernandez, Elena Resende, Mauricio G. C. Univ Politecn Cataluna Dept Estadist & Invest Operat BarcelonaTech ES-08034 Barcelona Spain Univ Politecn Cataluna Dept Estadist & Invest Operat BarcelonaTech Barcelona 08222 Spain AT&T Labs Res Network Evolut Res Dept Middletown NJ 07748 USA

This paper focuses on the capacitated minimum spanning tree (CMST) problem. Given a central processor and a set of remote terminals with specified demands for traffic that must flow between the central processor and terminals, the goal is to design a minimum cost network to carry this demand. Potential links exist between any pair of terminals and between the central processor and the terminals. Each potential link can be included in the design at a given cost. The CMST problem is to design a minimum-cost network connecting the terminals with the central processor so that the flow on any arc of the network is at most Q. A biased random-key genetic algorithm (BRKGA) is a metaheuristic for combinatorial optimization which evolves a population of random vectors that encode solutions to the combinatorial optimization problem. This paper explores several solution encodings as well as different strategies for some steps of the algorithm and finally proposes a BRKGA heuristic for the CMST problem. Computational experiments are presented showing the effectiveness of the approach: Seven new best-known solutions are presented for the set of benchmark instances used in the experiments. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Optimization Combinatorial optimization Networks Graphs Trees Spanning trees Capacitated minimum spanning tree Heuristics biased random-key genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

A biased random-key genetic algorithm for the maximum quasi-clique problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2018年第3期271卷 849-865页

作者： Pinto, Bruno Q. Ribeiro, Celso C. Rosseti, Isabel Plastino, Alexandre Inst Fed Educ Ciencia & Tecnol Triangulo Mineiro BR-38411104 Uberlandia MG Brazil Univ Fed Fluminense Inst Comp BR-24210240 Niteroi RJ Brazil

Given a graph G = (V, E) and a threshold gamma is an element of (0, 1 j, the maximum cardinality quasi-clique problem consists in finding a maximum cardinality subset C. of the vertices in V such that the density of the graph induced in G by C* is greater than or equal to the threshold gamma. This problem is NP-hard, since it admits the maximum clique problem as a special case. It has a number of applications in data mining, e.g. in social networks or phone call graphs. In this work, we propose a biased random-key genetic algorithm for solving the maximum cardinality quasi-clique problem. Two alternative decoders are implemented for the biased random-key genetic algorithm and the corresponding algorithm variants are evaluated. Computational results show that the newly proposed approaches improve upon other existing heuristics for this problem in the literature. All input data for the test instances and all detailed numerical results are available from Mendeley. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Metaheuristics biased random-key genetic algorithm Maximum quasi-clique problem Maximum clique problem Graph density

来源：评论

学校读者我要写书评

暂无评论

An extended Akers graphical method with a biased random-key genetic algorithm for job-shop scheduling

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2014年第2期21卷 215-246页

作者： Goncalves, Jose Fernando Resende, Mauricio G. C. Univ Porto Fac Econ INESC TEC LIAAD P-4200464 Oporto Portugal AT&T Labs Res Algorithms & Optimizat Res Dept Florham Pk NJ 07932 USA

This paper presents a local search, based on a new neighborhood for the job-shop scheduling problem, and its application within a biased random-key genetic algorithm. Schedules are constructed by decoding the chromosome supplied by the genetic algorithm with a procedure that generates active schedules. After an initial schedule is obtained, a local search heuristic, based on an extension of the 1956 graphical method of Akers, is applied to improve the solution. The new heuristic is tested on a set of 205 standard instances taken from the job-shop scheduling literature and compared with results obtained by other approaches. The new algorithm improved the best-known solution values for 57 instances.

关键词： job-shop scheduling genetic algorithm biased random-key genetic algorithm heuristics random keys graphical approach

来源：评论

学校读者我要写书评

暂无评论

A biased random-key genetic algorithm for OSPF and DEFT routing to minimize network congestion

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2011年第3期18卷 401-423页

作者： Reis, Roger Ritt, Marcus Buriol, Luciana S. Resende, Mauricio G. C. Univ Fed Rio Grande do Sul Inst Informat Porto Alegre RS Brazil AT&T Labs Res Algorithms & Optimizat Res Dept Florham Pk NJ 07932 USA

Interior gateway routing protocols like Open Shortest Path First (OSPF) and Distributed Exponentially Weighted Flow Splitting (DEFT) send flow through forward links toward the destination node. OSPF routes only on shortest-weight paths, whereas DEFT sends flow on all forward links, but with an exponential penalty on longer paths. Finding suitable weights for these protocols is known as the weight setting problem (WSP). In this paper, we present a biased random-key genetic algorithm for WSP using both protocols. The algorithm uses dynamic flow and dynamic shortest path computations. We report computational experiments that show that DEFT achieves less network congestion when compared with OSPF, while, however, yielding larger delays.

关键词： networks networking telecommunication networks routing genetic algorithm biased random-key genetic algorithm local search metaheuristics

来源：评论

学校读者我要写书评

暂无评论

A biased random-key genetic algorithm for the two-stage capacitated facility location problem

引用

EXPERT SYSTEMS WITH APPLICATIONS 2019年 115卷 418-426页

作者： Biajoli, Fabricio Lacerda Chaves, Antonio Augusto Nogueira Lorena, Luiz Antonio Univ Fed Sao Paulo BR-12231280 Sao Jose Dos Campos Brazil

This paper presents a new metaheuristic approach for the two-stage capacitated facility location problem (TSCFLP), which the objective is to minimize the operation costs of the underlying two-stage transportation system, satisfying demand and capacity constraints. In this problem, a single product must be transported from a set of plants to meet customers demands passing out by intermediate depots. Since this problem is known to be NP-hard, approximated methods become an efficient alternative to solve real industry problems. As far as we know, the TSCFLP is being solved in most cases by hybrid approaches supported by an exact method, and sometimes a commercial solver is used for this purpose. Bearing this in mind, a BRKGA metaheuristic and a new local search for TSCFLP are proposed. It is the first time that BRKGA had been applied to this problem and the computational results show the competitiveness of the approach developed in terms of quality of the solutions and required computational time when compared with those obtained by state-of-the-art heuristics. The approach proposed can be easily coupled in intelligent systems to help organizations enhance competitiveness by optimally placing facilities in order to minimize operational costs. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： Two-stage capacitated facility location biased random-key genetic algorithm Local search Transportation systems

来源：评论

学校读者我要写书评

暂无评论

A matheuristic approach for the minimum broadcast time problem using a biased random-key genetic algorithm

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2024年第1期31卷 246-273页

作者： Lima, Alfredo Aquino, Andre L. L. Nogueira, Bruno Pinheiro, Rian G. S. Univ Fed Alagoas Inst Comp Av Lourival Melo Mota S-N BR-57072900 Maceio Alagoas Brazil

The Minimum Broadcast Time (MBT) is a well-known data dissemination problem whose goal is to find a broadcast scheme that minimizes the number of steps needed to execute the broadcast operation. The problem has many applications in distributed systems and, in particular, the Industry 4.0 domain. Because Industry 4.0 applications rely primarily on the use of large-scale machine to machine communications, they need data dissemination techniques that combine high reliability with low communication latency. This work proposes a biased random-key genetic algorithm and a matheuristic for the MBT. We carry out experiments with our algorithms on instances commonly used in the literature (hypercube, shuffle exchange, cube-connected cycles, de Bruijn, Harary graphs), and also on massive synthetic instances (up to 1000 vertices), allowing to cover many possibilities of real industry topologies. Our proposal is also compared with state-of-the-art exact methods and heuristics. Experimental results show that our algorithm is able to outperform the best-known heuristics for the MBT, and also that it is a very good alternative for large instances that cannot be solved by current exact methods.

关键词： combinatorial optimization minimum broadcast time matheuristic biased random-key genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

A biased random-key genetic algorithm for the project scheduling problem with flexible resources

引用

TOP 2018年第2期26卷 283-308页

作者： Almeida, Bernardo F. Correia, Isabel Saldanha-da-Gama, Francisco Univ Lisbon Dept Estat & Invest Operac Ctr Matemat Aplicacoes Fundamentais & Invest Oper Fac Ciencias P-1749016 Lisbon Portugal Univ Nova Lisboa Fac Ciencias & Tecnol Dept Matemat Ctr Matemat & Aplicacoes P-2829516 Caparica Portugal

In this paper, we investigate a resource-constrained project scheduling problem with flexible resources. This is an -hard combinatorial optimization problem that consists of scheduling a set of activities requiring specific resource units of several skills. The goal is to minimize the makespan of the project. We propose a biased random-key genetic algorithm for computing feasible solutions for the referred problem. We study different decoding mechanisms: an already existing method in the literature, a new adapted serial scheduling generation scheme, and a combination of both. The new procedure is tested using a set of benchmark instances of the problem. The results provide strong evidence that the new heuristic is robust and yields high-quality feasible solutions.

关键词： Resource-constrained project scheduling Flexible resources biased random-key genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

biased random-key genetic algorithm for the job sequencing and tool switching problem with non-identical parallel machines

引用

COMPUTERS & OPERATIONS RESEARCH 2024年 163卷

作者： Soares, Leonardo C. R. Carvalho, Marco A. M. Inst Fed Sudeste Minas Gerais Campus Manhuacu BR-36909300 Manhuacu MG Brazil Univ Fed Ouro Preto Campus Morro Cruzeiro BR-35400000 Ouro Preto MG Brazil

We address the job sequencing and tool switching problem associated with non-identical parallel machines - a variation of the well-known sequencing and switching problem (SSP) better adapted to reflect the challenges in modern production environments. The NP-hard problem is approached by considering two isolated objective functions: the minimization of the makespan and the minimization of the total flow time. We present two versions of a parallel biased random-key genetic algorithm hybridized with tailored local search procedures that are organized using variable neighborhood descent. The proposed methods are compared with state-of-the-art methods by considering 640 benchmark instances from literature. For both objective functions considered, the proposed methods consistently outperform the compared methods. All known optimal values for both objectives are achieved, and a substantial gap is reported for all instance groups when compared with the best previously published solution values.

关键词： Combinatorial optimization biased random-key genetic algorithm Job sequencing and tool switching problem with non-identical parallel machines Flexible manufacturing system

来源：评论

学校读者我要写书评

暂无评论

A biased random-key genetic algorithm for Placement of Virtual Machines across Geo-Separated Data Centers 15

A Biased Random-key Genetic Algorithm for Placement of Virtu...

引用

17th genetic and Evolutionary Computation Conference (GECCO)

作者： Stefanello, Fernando Aggarwal, Vaneet Buriol, Luciana S. Goncalves, Jose F. Resende, Mauricio G. C. Univ Fed Rio Grande do Sul Inst Informat Porto Alegre RS Brazil Purdue Univ Sch Ind Engn W Lafayette IN 47907 USA Univ Porto Fac Econ P-4200464 Oporto Portugal Amazon Com Math Optimizat & Planning Seattle WA 98109 USA

ISBN: (纸本)9781450334723

Cloud computing has recently emerged as a new technology for hosting and supplying services over the Internet. This technology has brought many benefits, such as eliminating the need for maintaining expensive computing hardware and allowing business owners to start from small and increase resources only when there is a rise in service demand. With an increasing demand for cloud computing, providing performance guarantees for applications that run over cloud become important. Applications can be abstracted into a set of virtual machines with certain guarantees depicting the quality of service of the application. In this paper, we consider the placement of these virtual machines across multiple data centers, meeting the quality of service requirements while minimizing the bandwidth cost of the data centers. This problem is a generalization of the NP-hard Generalized Quadratic Assignment Problem (GQAP). We formalize the problem and propose a novel algorithm based on a biased random-key genetic algorithm (BRKGA) to find nearoptimal solutions for the problem. The experimental results show that the proposed algorithm is effective in quickly finding feasible solutions and it produces better results than a baseline aproach provided by a commercial solver and a multi-start algorithm.

关键词： Combinatorial optimization Cloud computing biased random-key genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：