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

A biased random key genetic algorithm for the field technician scheduling problem

COMPUTERS & OPERATIONS RESEARCH 2016年 75卷 49-63页

作者： Damm, Ricardo B. Resende, Mauricio G. C. Ronconi, Debora P. Univ Sao Paulo Polytech Sch Dept Prod Engn Sao Paulo Brazil Av Prof Almeida Prado 128 Cidade Univ BR-05508070 Sao Paulo SP Brazil Amazon Com Math Optimizat & Planning 333 Boren Ave North Seattle WA 98109 USA

This paper addresses a problem that service companies often face: the field technician scheduling problem. The problem considers the assignment of a set of jobs or service tasks to a group of technicians. The tasks are in different locations within a city, with different time windows, priorities, and processing times. Technicians have different skills and working hours. The main objective is to maximize the sum of priority values associated with the tasks performed each day. Due to the complexity of this problem, constructive heuristics that explore specific characteristics of the problem are developed. A customized biased random key genetic algorithm (BRKGA) is also proposed. Computational tests with 1040 instances are presented. The constructive heuristics outperformed a heuristic of the literature in 90% of the instances. In a comparative study with optimal solutions obtained for small-sized problems, the BRKGA reached 99% of the optimal values;for medium- and large-sized problems, the BRKGA provided solutions that are on average 3.6% below the upper bounds. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Routing and scheduling technicians Time windows Heuristic biased random key genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

A bi-objective multi-population biased random key genetic algorithm for joint scheduling quay cranes and speed adjustable vehicles in container terminals

引用

FLEXIBLE SERVICES AND MANUFACTURING JOURNAL 2023年第1期35卷 241-268页

作者： Fontes, Dalila B. M. M. Homayouni, S. Mahdi INESC TEC LIAAD Porto Portugal Univ Porto Fac Econ Porto Portugal

This work formulates a mixed-integer linear programming (MILP) model and proposes a bi-objective multi-population biased random key genetic algorithm (mp-BRKGA) for the joint scheduling of quay cranes and speed adjustable vehicles in container terminals considering the dual-cycling strategy. Under such a strategy, a combination of loading and unloading containers are handled by a set of cranes (moved between ships and vehicles) and transported by a set of vehicles (transported between the quayside and the storage area). The problem consists of four components: crane scheduling, vehicle assignment, vehicle scheduling, and speed assignment both for empty and loaded journey legs. The results show that an approximated true Pareto front can be found by solving the proposed MILP model and that the mp-BRKGA finds uniformly distributed Pareto fronts, close to the true ones. Additionally, the results clearly demonstrate the advantages of considering speed adjustable vehicles since both the makespan and the energy consumption can be considerably reduced.

关键词： Joint scheduling Container terminal Speed adjustable vehicles Quay cranes Energy efficiency biased random key genetic algorithm MILP Bi-objective

来源：评论

学校读者我要写书评

暂无评论

Solving the open vehicle routing problem with capacity and distance constraints with a biased random key genetic algorithm

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2019年 133卷 207-219页

作者： Ruiz, Efrain Soto-Mendoza, Valeria Ruiz Barbosa, Alvaro Ernesto Reyes, Ricardo Inst Tecnol Saltillo Div Estudios Posgrad Blvd Venustiano Carranza 2400 Saltillo 25280 Coahuila Mexico Autonomous Univ Coahuila Res Ctr Appl Math Campo Redondo S-N Saltillo 25115 Coahuila Mexico Colegio Postgrad Campus PueblaKm 125-5 Carretera Fed Puebla 72760 Mexico Inst Tecnol Saltillo Dept Ingn Ind Blvd Venustiano Carranza 2400 Saltillo 25280 Coahuila Mexico

This paper presents a biased random-key genetic algorithm designed to solve the open vehicle routing problem with capacity and distance constraints. Consider a depot from which vehicles depart to deliver goods demanded by clients. Every client is served by one vehicle that is part of a homogeneous fleet. The vehicles initiate their routes at the depot and finish them after servicing the last client without returning to the depot. The problem's objective function is to minimize the total distance traveled by the vehicles while respecting the capacity and maximum distance constraints. The potential applications in real life scenarios make this problem relevant among other vehicle routing problems. Three sets of benchmark problems from the literature are used to test the proposed algorithm. The obtained results show the algorithm's good performance since the best-known solutions for 16 of the 30 instances were improved.

关键词： Optimization Combinatorial optimization Vehicle routing Open vehicle routing problem biased random key genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

A biased random key genetic algorithm for open dimension nesting problems using no-fit raster

引用

EXPERT SYSTEMS WITH APPLICATIONS 2017年 81卷 358-371页

作者： Mundim, Leandro R. Andretta, Marina de Queiroz, Thiago Alves Univ Sao Paulo Av Trabalhador Sao Carlense 400 BR-13566590 Sao Carlos SP Brazil UFG Inst Math & Technol Campus Catalao BR-75704020 Catalao Go Brazil

We consider two NP-hard open dimension nesting problems for which a set of items has to be packed without overlapping into a two-dimensional bin in order to minimize one or both dimensions of this bin. These problems are faced by real-life applications, such as textile, footwear and automotive industries. Therefore, there is a need for specialized systems to help in a decision making process. Bearing this in mind, we derive new concepts as the no-fit raster, which can be used to check overlapping between any two-dimensional generic-shaped items. We also use a biased random key genetic algorithm to determine the sequence in which items are packed. Once the sequence of items is determined, we propose two heuristics based on bottom-left moves and the no-fit raster concept, which are in turn used to arrange these items into the given bin observing the objective criteria. As far as we know, the problem with two open dimensions is being solved for the first time in the context of nesting problems and we present the first whole quadratic model for this problem. Computational experiments conducted on benchmark instances from the literature (some from the textile industry and others including circles, convex, and non-convex polygons) show the competitiveness of the approaches developed as they were able to calculate the best results for 74.14% of the instances. It can be observed that these results show new directions in terms of solving nesting problems whereby approaches can be coupled in existing intelligent systems to support decision makers in this field. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Nesting problems Open dimension problems No-fit raster Bottom-left biased random key genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

A Hybrid biased random key genetic algorithm for the Quadratic Assignment Problem

引用

INFORMATION PROCESSING LETTERS 2016年第8期116卷 513-520页

作者： Lalla-Ruiz, Eduardo Exposito-Izquierdo, Christopher Melian-Batista, Belen Marcos Moreno-Vega, J. Univ La Laguna Dept Comp & Syst Engn E-38207 San Cristobal la Laguna Spain

The Quadratic Assignment Problem (QAP) is a well-known NP-hard combinatorial optimization problem that has received a lot of attention from the research community since it has many practical applications, such as allocation of facilities, design of electronic devices, etc. In this paper, we propose a hybrid approximate approach for the QAP based upon the framework of the biased random key genetic algorithm. This hybrid approach includes an improvement method to be applied over the best individuals of the population in order to exploit the promising regions found in the search space. In the computational experiments, we evaluate the performance of our approach on widely known instances from the literature. In these experiments, we compare our approach against the best proposals from the related literature and we conclude that our approach is able to report high-quality solutions by means of short computational times. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Quadratic Assignment Problem biased random key genetic algorithm Metaheuristic Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

A biased random key genetic algorithm approach for inventory-based multi-item lot-sizing problem

引用

PROCEEDINGS OF THE INSTITUTION OF MECHANICAL ENGINEERS PART B-JOURNAL OF ENGINEERING MANUFACTURE 2015年第1期229卷 157-171页

作者： Chan, F. T. S. Tibrewal, Rupak Kumar Prakash, Anuj Tiwari, M. K. Hong Kong Polytech Univ Dept Ind & Syst Engn Hong Kong Hong Kong Peoples R China Indian Inst Technol Dept Ind Engn & Management Kharagpur 721302 W Bengal India

In this article, we have explored multi-item capacitated lot-sizing problem by addressing the backlogging and associated high penalty costs incurred. At the same time, penalty cost for exceeding the resource capacity has also been taken into account. Penalty cost related to both backlogging and overutilizing capacity has been included in main objective function. The main objective is to achieve such a solution that minimizes the total cost. The ingredients of total cost are the setup cost, production cost, inventory holding cost and aforementioned both the penalty costs. To solve this computationally complex problem, a less explored algorithm biased random key genetic algorithm has been applied. To the best of our knowledge, this research presents the first application of biased random key genetic algorithm to a lot-sizing problem. To test the effectiveness of proposed algorithm, extensive computational tests are conducted. The encouraging results show that the proposed algorithm is an efficient tool to tackle such complex problems. A comparative study with other existing heuristics shows the supremacy of proposed algorithm in terms of quality of the solution, number of generation and computational time.

关键词： Production planning multi-item capacitated lot-sizing problem inventory control biased random key genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

A biased random key genetic algorithm Applied to Target Set Selection in Viral Marketing

A Biased Random Key Genetic Algorithm Applied to Target Set ...

引用

genetic and Evolutionary Computation Conference (GECCO)

作者： Lopez Serrano, Albert Blum, Christian Artificial Intelligence Res Inst IIIA CSIC Bellaterra Spain

ISBN: (纸本)9781450392372

The Target Set Selection (TSS) problem is an NP-hard combinatorial optimization problem with origins in the field of social networks. There are various problem variants, all dealing with finding a smallest subset of vertices of a graph such that their influence is propagated to all nodes of the graph under a specific diffusion model. Despite the practical relevance of the problem, most existing research efforts have focused on theoretical properties restricted to certain classes of graphs. The richness in terms of theoretical results is in contrast to the scarceness of research aiming at efficiently solving the TSS problem. In this work we propose a biased random key genetic algorithm (BRKGA) for solving the TSS problem in large-scale social networks. We consider the problem in combination with the Linear Threshold diffusion model. The obtained results show that our approach outperforms a recent heuristic from the literature.

关键词： biased random key genetic algorithm target set selection social networks

来源：评论

学校读者我要写书评

暂无评论

A biased random key genetic algorithm applied to the VRPTW with Skill Requirements and Synchronization Constraints

A Biased Random Key Genetic Algorithm applied to the VRPTW w...

引用

genetic and Evolutionary Computation Conference (GECCO)

作者： Kummer, Alberto F. N. Buriol, Luciana S. de Araujo, Olinto C. B. Univ Fed Rio Grande do Sul Porto Alegre RS Brazil Univ Fed Santa Maria Santa Maria RS Brazil

ISBN: (纸本)9781450371285

We applied a biased random key genetic algorithm (BRKGA) to solve the Vehicle Routing Problem with Time Windows and Synchronization Constraints. Additionally, both vehicles and clients are skilled, and each client can require up to two distinct skills to be serviced. On double-skilled clients, the operations of each skill should be performed by different vehicles, either simultaneously or respecting a precedence order. Those requirements introduce nonlinearities on the problem, in the sense that a small change on a single route potentially impacts all the other routes of the solution, making it hard to define an effective local search procedure. To circumvent this difficulty, we approached the problem using a genetic algorithm that evolves the sequence in which the services are inserted into the routes. We assessed the performance of our solution method using instances from the literature of the home health care problem. The genetic algorithm outperformed the previous best-known solutions found by a fix-and-optimize matheuristic by up to 25%, using less than half of computational times reported previously. The BRKGA demonstrated to be able to perform well both in exploration and exploitation in the solution space of the problem.

关键词： Vehicle routing problem with time windows route synchronization constraints biased random key genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

A biased random key genetic algorithm for the Weighted Independent Domination Problem 19

A Biased Random Key Genetic Algorithm for the Weighted Indep...

引用

genetic and Evolutionary Computation Conference (GECCO)

作者： Rodriguez Corominas, Guillem Blum, Christian Blesa, Maria J. Univ Politecn Cataluna Barcelona Spain Artificial Intelligence Res Inst IIIA CSIC Bellaterra Spain

ISBN: (纸本)9781450367486

This work deals with an NP-hard problem in graphs known as the weighted independent domination problem. We propose a biased random key genetic algorithm for solving this problem. The most important part of the proposed algorithm is a decoder that translates any vector of real-values into valid solutions to the tackled problem. The experimental results, in comparison to a state-of-the-art population-based iterated greedy algorithm from the literature, show that our proposed approach has advantages over the state-of-the-art algorithm in the context of the more dense graphs in which edges have higher weights than vertices.

关键词： biased random key genetic algorithm weighted independent domination

来源：评论

学校读者我要写书评

暂无评论

Optimizing job shop scheduling with speed-adjustable machines and peak power constraints: A mathematical model and heuristic solutions

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2025年第1期32卷 194-220页

作者： Homayouni, S. Mahdi Fontes, Dalila B. M. M. Constructor Univ Sch Business Social & Decis Sci Campus Ring 1 D-28759 Bremen Germany CESE INESCTEC P-4200465 Porto Portugal LIAAD INESCTEC P-4200465 Porto Portugal Univ Porto Fac Econ P-4200464 Porto Portugal

This paper addresses a job shop scheduling problem with peak power constraints, in which jobs can be processed once or multiple times on either all or a subset of the machines. The latter characteristic provides additional flexibility, nowadays present in many manufacturing systems. The problem is complicated by the need to determine both the operation sequence and starting time as well as the speed at which machines process each operation. Due to the adherence to renewable energy production and its intermittent nature, manufacturing companies need to adopt power-flexible production schedules. The proposed power control strategies, that is, adjusting processing speed and timing to reduce peak power requirements may impact production time (makespan) and energy consumption. Therefore, we propose a bi-objective approach that minimizes both objectives. A linear programming model is developed to provide a formal statement of the problem, which is solved to optimality for small-sized instances. We also proposed a multi-objective biased random key genetic algorithm framework that evolves several populations in parallel. Computational experiments provide decision and policymakers with insights into the implications of imposing or negotiating power consumption limits. Finally, the several trade-off solutions obtained show that as the power limit is lowered, the makespan increases at an increasing rate and a similar trend is observed in energy consumption but only for very small makespan values. Furthermore, peak power demand reductions of about 25% have a limited impact on the minimum makespan value (4-6% increase), while at the same time allowing for a small reduction in energy consumption.

关键词： job shop scheduling problem energy efficiency peak power speed-adjustable machines biased random key genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：