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

A hyper-heuristic based framework for dynamic optimization problems

APPLIED SOFT COMPUTING 2014年 19卷 236-251页

作者： Topcuoglu, Haluk Rahmi Ucar, Abdulvahid Altin, Lokman Marmara Univ Dept Comp Engn TR-34722 Istanbul Turkey

Most of the real world problems have dynamic characteristics, where one or more elements of the underlying model for a given problem including the objective, constraints or even environmental parameters may change over time. Hyper-heuristics are problem-independent meta-heuristic techniques that are automating the process of selecting and generating multiple low-level heuristics to solve static combinatorial optimization problems. In this paper, we present a novel hybrid strategy for applicability of hyper-heuristic techniques on dynamic environments by integrating them with the memory/search algorithm. The memory/search algorithm is an important evolutionary technique that have applied on various dynamic optimization problems. We validate performance of our method by considering both the dynamic generalized assignment problem and the moving peaks benchmark. The former problem is extended from the generalized assignment problem by changing resource consumptions, capacity constraints and costs of jobs over time;and the latter one is a well-known synthetic problem that generates and updates a multidimensional landscape consisting of several peaks. Experimental evaluation performed on various instances of the given two problems validates that our hyper-heuristic integrated framework significantly outperforms the memory/search algorithm. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Dynamic optimization problems Hyper-heuristics generalized assignment problem Moving peaks benchmark Memory search technique

来源：评论

学校读者我要写书评

暂无评论

Decomposition heuristics for robust job-shop scheduling

引用

IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION 1998年第2期14卷 303-313页

作者： Byeon, ES Wu, SD Storer, RH Korea Transport Inst Seoul South Korea Lehigh Univ Mfg Logist Inst Bethlehem PA 18015 USA

In this paper, we present an approach to weighted tardiness job-shop scheduling problems (JSP) using a graph decomposition technique, Our method decomposes a JSP into a series of sub-problems by solving a variant of the generalized assignment problem which we term "VAP." Given a specified assignment cost, VAP assigns operations to mutually exclusive and exhaustive subsets, identifying a partially specified schedule, Compared to a conventional, completely specified schedule, this partial schedule is more robust to shop disturbances, and therefore more useful for planning and control, We have developed assignment heuristics which iteratively update the problem parameters using lower and upper bounds computed from the corresponding schedule, The heuristics are tested on standard test problems. We show that the proposed approach provides a means for extending traditional scheduling capabilities to a much wider spectrum of shop conditions and production scenarios.

关键词： decomposition generalized assignment problem heuristic scheduling pricing structure job shop scheduling weighted tardiness

来源：评论

学校读者我要写书评

暂无评论

Radio resource allocation algorithms for multi-service OFDMA networks: the uniform power loading scenario

引用

TELECOMMUNICATION SYSTEMS 2014年第4期56卷 467-480页

作者： Gotsis, Antonis G. Komnakos, Dimitris I. Vouyioukas, Demosthenes D. Constantinou, Philip Natl Tech Univ Athens ECE Sch Mobile Radiocommun Lab Athens Greece Univ Aegean Dept Informat & Commun Syst Engn Comp & Commun Syst Lab Karlovassi 83200 Samos Island Greece

Adaptive Radio Resource Allocation is essential for guaranteeing high bandwidth and power utilization as well as satisfying heterogeneous Quality-of-Service requests regarding next generation broadband multicarrier wireless access networks like LTE and Mobile WiMAX. A downlink OFDMA single-cell scenario is considered where heterogeneous Constant-Bit-Rate and Best-Effort QoS profiles coexist and the power is uniformly spread over the system bandwidth utilizing a Uniform Power Loading (UPL) scenario. We express this particular QoS provision scenario in mathematical terms, as a variation of the well-known generalized assignment problem answered in the combinatorial optimization field. Based on this concept, we propose two heuristic search algorithms for dynamically allocating subchannels to the competing QoS classes and users which are executed under polynomially-bounded cost. We also propose an Integer Linear Programming model for optimally solving and acquiring a performance upper bound for the same problem at reasonable yet high execution times. Through extensive simulation results we show that the proposed algorithms exhibit high close-to-optimal performance, thus comprising attractive candidates for implementation in modern OFDMA-based systems.

关键词： OFDMA Adaptive subchannel allocation Multi-class QoS Uniform power loading Integer linear programming Heuristic algorithm generalized assignment problem

来源：评论

学校读者我要写书评

暂无评论

Chebyshev center based column generation

引用

DISCRETE APPLIED MATHEMATICS 2011年第18期159卷 2251-2265页

作者： Lee, Chungmok Park, Sungsoo Korea Adv Inst Sci & Technol Dept Ind & Syst Engn Taejon 305701 South Korea ETRI IT Convergence Technol Res Lab Taejon 305700 South Korea

The classical column generation approach often shows a very slow convergence. Many different acceleration techniques have been proposed recently to improve the convergence. Here, we briefly survey these methods and propose a novel algorithm based on the Chebyshev center of the dual polyhedron. The Chebyshev center can be obtained by solving a linear program;consequently, the proposed method can be applied with small modifications on the classical column generation procedure. We also show that the performance of our algorithm can be enhanced by introducing proximity parameters which enable the position of the Chebyshev center lobe adjusted. Numerical experiments are conducted on the binpacking, vehicle routing problem with time windows, and the generalized assignment problem. The computational results of these experiments demonstrate the effectiveness of our proposed method. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Stabilized column generation Chebyshev center Binpacking problem Vehicle routing problem generalized assignment problem

来源：评论

学校读者我要写书评

暂无评论

A generalized assignment model for dynamic supply chain capacity planning

引用

NAVAL RESEARCH LOGISTICS 2012年第6期59卷 470-485页

作者： Mazzola, Joseph B. Neebe, Alan W. Univ N Carolina Belk Coll Business Charlotte NC 28223 USA Univ N Carolina Kenan Flagler Business Sch Chapel Hill NC 27599 USA

We consider a generalization of the well-known generalized assignment problem (GAP) over discrete time periods encompassed within a finite planning horizon. The resulting model, MultiGAP, addresses the assignment of tasks to agents within each time period, with the attendant single-period assignment costs and agent-capacity constraint requirements, in conjunction with transition costs arising between any two consecutive periods in which a task is reassigned to a different agent. As is the case for its single-period antecedent, MultiGAP offers a robust tool for modeling a wide range of capacity planning problems occurring within supply chain management. We provide two formulations for MultiGAP and establish that the second (alternative) formulation provides a tighter bound. We define a Lagrangian relaxation-based heuristic as well as a branch-and-bound algorithm for MultiGAP. Computational experience with the heuristic and branch-and-bound algorithm on over 2500 test problems is reported. The Lagrangian heuristic consistently generates high-quality and in many cases near-optimal solutions. The branch-and-bound algorithm is also seen to constitute an effective means for solving to optimality MultiGAP problems of reasonable size. (c) 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012

关键词： capacity planning generalized assignment problem supply chain management algorithm heuristic

来源：评论

学校读者我要写书评

暂无评论

Truck scheduling for solid waste collection in the City of Porto Alegre, Brazil

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2008年第6期36卷 1133-1149页

作者： Li, Jinc-Quan Borenstein, Denis Mirchandania, Pitu B. Univ Fed Rio Grande do Sul Sch Management BR-90010460 Porto Alegre RS Brazil Univ Arizona Tucson AZ 85721 USA

This paper considers a truck scheduling problem in the context of solid waste collection in the City of Porto Alegre, Brazil. The problem consists of designing "good" daily truck schedules over a set of previously defined collection trips, on which the trucks collect solid waste in fixed routes and empty loads in one of several operational recycling facilities in the system. These facilities are managed by cooperatives whose members are poor and not part of the mainstream economy. The main objective is to minimize the total operating and fixed truck costs. We show that the problem can be modeled as a special case of the single-depot vehicle scheduling problem, which is polynomially solvable. However, due to the social benefits of the solid waste program, it is desirable to obtain balanced assignments of collection trips unloading their cargo at the recycling facilities. We prove that the truck scheduling problem considering balanced unloading is NP-hard. A heuristic approach, incorporating an auction algorithm and a dynamic penalty method, is designed to acquire a good solution. Finally, computational experiments are conducted on real data. The results show that the heuristic approach simultaneously reduces total costs and balances the number of trips assigned to each recycling facility. (C) 2006 Elsevier Ltd. All rights reserved.

关键词： vehicle scheduling solid waste collection generalized assignment problem operations management

来源：评论

学校读者我要写书评

暂无评论

The server reassignment problem for load balancing in structured P2P systems

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2008年第2期19卷 234-246页

作者： Chen, Chyouhwa Tsai, Kun-Cheng Natl Taiwan Univ Sci & Technol Dept Comp Sci & Informat Engn Taipei 106 Taiwan Inst Informat Ind Taipei 116 Taiwan

Application-layer peer-to-peer (P2P) networks are considered to be the most important development for next-generation Internet infrastructure. For these systems to be effective, load balancing among the peers is critical. Most structured P2P systems rely on ID-space partitioning schemes to solve the load imbalance problem and have been known to result in an imbalance factor of circle minus (log N) in the zone sizes. This paper makes two contributions. First, we propose addressing the virtual-server-based load balancing problem systematically using an optimization-based approach and derive an effective algorithm to rearrange loads among the peers. We demonstrate the superior performance of our proposal in general and its advantages over previous strategies in particular. We also explore other important issues vital to the performance in the virtual server framework, such as the effect of the number of directories employed in the system and the performance ramification of user registration strategies. Second, and perhaps more significantly, we systematically characterize the effect of heterogeneity on load balancing algorithm performance and the conditions in which heterogeneity may be easy or hard to deal with based on an extensive study of a wide spectrum of load and capacity scenarios.

关键词： distributed hash table load balance local search structured peer-to-peer system generalized assignment problem

来源：评论

学校读者我要写书评

暂无评论

An implementation of exact knapsack separation

引用

JOURNAL OF GLOBAL OPTIMIZATION 2016年第1期66卷 127-150页

作者： Vasilyev, Igor Boccia, Maurizio Hanafi, Said Russian Acad Sci Siberian Branch Inst Syst Dynam & Control Theory Lermontov Srt 134 Irkutsk 664033 Russia Univ Sannio Dipartimento Ingn Viale Traiano I-82100 Benevento Italy Univ Valenciennes LAMIH UMR 8530 CNRSLe Mont Houy ISTV2 F-59313 Valenciennes 9 France

Cutting planes have been used with great success for solving mixed integer programs. In recent decades, many contributions have led to successive improvements in branch-and-cut methods which incorporate cutting planes in branch and bound algorithm. Using advances that have taken place over the years on 0-1 knapsack problem, we investigate an efficient approach for 0-1 programs with knapsack constraints as local structure. Our approach is based on an efficient implementation of knapsack separation problem which consists of the four phases: preprocessing, row generation, controlling numerical errors and sequential lifting. This approach can be used independently to improve formulations with cutting planes generated or incorporated in branch and cut to solve a problem. We show that this approach allows us to efficiently solve large-scale instances of generalized assignment problem, multilevel generalized assignment problem, capacitated -median problem and capacitated network location problem to optimality.

关键词： Knapsack problem Cutting plane Exact separation generalized assignment problem Multilevel generalized assignment problem Capacitated p-median problem Capacitated network location problem

来源：评论

学校读者我要写书评

暂无评论

Migration-Aware Network Services With Edge Computing

引用

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT 2022年第2期19卷 1458-1471页

作者： Mukhopadhyay, Atri Iosifidis, George Ruffini, Marco Trinity Coll Dublin CONNECT Ctr Sch Comp Sci & Stat Dublin 2 Dublin D02 PN40 Ireland Delft Univ Technol Dept Software Technol NL-2600 AA Delft Netherlands

The development of Multi-access edge computing (MEC) has resulted from the requirement for supporting next generation mobile services, which need high capacity, high reliability and low latency. The key issue in such MEC architectures is to decide which edge nodes will be employed for serving the needs of the different end users. Here, we take a fresh look into this problem by focusing on the minimization of migration events rather than focusing on maximizing usage of resources. This is important because service migrations can create significant service downtime to applications that need low latency and high reliability, in addition to increasing traffic congestion in the underlying network. This paper introduces a priority induced service migration minimization (PrISMM) algorithm, which aims at minimizing service migration for both high and low priority services, through the use of Markov decision process, learning automata and combinatorial optimization. We carry out extensive simulations and produce results showing its effectiveness in reducing the mean service downtime of lower priority services and the mean admission time of the higher priority services.

关键词： Servers Resource management Passive optical networks Task analysis Minimization Markov processes Costs generalized assignment problem learning automata markov decision process multi-access edge computing service migration

来源：评论

学校读者我要写书评

暂无评论

Knapsack problems with sigmoid utilities: Approximation algorithms via hybrid optimization

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2014年第2期236卷 488-498页

作者： Srivastava, Vaibhav Bullo, Francesco Princeton Univ Mech & Aerosp Engn Dept Princeton NJ 08544 USA Univ Calif Santa Barbara Ctr Control Dynam Syst & Computat Santa Barbara CA 93106 USA

We study a class of non-convex optimization problems involving sigmoid functions. We show that sigmoid functions impart a combinatorial element to the optimization variables and make the global optimization computationally hard. We formulate versions of the knapsack problem, the generalized assignment problem and the bin-packing problem with sigmoid utilities. We merge approximation algorithms from discrete optimization with algorithms from continuous optimization to develop approximation algorithms for these NP-hard problems with sigmoid utilities. (c) 2013 Elsevier B.V. All rights reserved.

关键词： Sigmoid utility/S-curve Knapsack problem generalized assignment problem Bin-packing problem Multi-choice knapsack problem Human attention allocation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：