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

branch-and-bound algorithms for scheduling in permutation flowshops to minimize the sum of weighted flowtime/sum of weighted tardiness/sum of weighted flowtime and weighted tardiness/sum of weighted flowtime, weighted tardiness and weighted earliness of jobs

引用

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY 2009年第7期60卷 991-1004页

作者： Madhushini, N. Rajendran, C. Deepa, Y. Indian Inst Technol Dept Management Studies Madras 600036 Tamil Nadu India

The problem of scheduling in permutation flowshops is considered in this paper with the objectives of minimizing the sum of weighted flowtime/sum of weighted tardiness/sum of weighted flowtime and weighted tardiness/sum of weighted flowtime, weighted tardiness and weighted earliness of jobs, with each objective considered separately. Lower bounds on the given objective (corresponding to a node generated in the scheduling tree) are developed by solving an assignment problem. branch-and-bound algorithms are developed to obtain the best permutation sequence in each case. Our algorithm incorporates a job-based lower bound (integrated with machine-based bounds) with respect to the weighted flowtime/weighted tardiness/weighted flowtime and weighted tardiness, and a machine-based lower bound with respect to the weighted earliness of jobs. The proposed algorithms are evaluated by solving many randomly generated problems of different problem sizes. The results of an extensive computational investigation for various problem sizes are presented. In addition, one of the proposed branch-and-bound algorithms is compared with a related existing branch-and-bound algorithm. Journal of the Operational Research Society (2009) 60, 991-1004. doi:10.1057/***.2602642

关键词： flowshop scheduling assignment problem weighted flowtime weighted tardiness weighted earliness branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

COPING WITH ANOMALIES IN PARALLEL branch-and-bound algorithms

引用

IEEE TRANSACTIONS ON COMPUTERS 1986年第6期35卷 568-573页

作者： LI, GJ WAH, BW PURDUE UNIV SCH ELECT ENGNW LAFAYETTEIN 47907

A general technique that can be used to solve a wide variety of discrete optimization problems is the branch-and-bound algorithm. We have adapted and extended branch-and-bound algorithms for parallel processing. The computational efficiency of these algorithms depends on the allowance function, the data structure, and the search strategies. Anomalies owing to parallelism may occur. In this correspondence, anomalies of parallel branch-and-bound algorithms using the same search strategy as the corresponding serial algorithms are studied. Sufficient conditions to guarantee no degradation in performance due to parallelism and necessary conditions for allowing parallelism to have a speedup greater than the number of processors are presented.

关键词： Anomalies approximation branch-and-bound algorithms heuristic search lower-bound test parallel processing

来源：评论

学校读者我要写书评

暂无评论

Hill-climbing and branch-and-bound algorithms for exact and approximate inference in credal networks

引用

INTERNATIONAL JOURNAL OF APPROXIMATE REASONING 2007年第3期44卷 261-280页

作者： Cano, Andres Gomez, Manuel Moral, Serafin Abellan, Joaquin Univ Granada ETS Ingn Informat Dept Comp Sci & Artificial Intelligence E-18071 Granada Spain

This paper proposes two new algorithms for inference in credal networks. These algorithms enable probability intervals to be obtained for the states of a given query variable. The first algorithm is approximate and uses the hill-climbing technique in the Shenoy-Shafer architecture to propagate in join trees;the second is exact and is a modification of Rocha and Cozman's branch-and-bound algorithm, but applied to general directed acyclic graphs, (C) 2006 Elsevier Inc. All rights reserved.

关键词： credal network probability intervals Bayesian networks strong independence hill-climbing branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

Delay Margin Analysis of Uncertain Linear Control Systems Using Probabilistic μ

引用

INTERNATIONAL JOURNAL OF ROBUST AND NONLINEAR CONTROL 2025年第6期35卷 2101-2118页

作者： Somers, F. Roos, C. Biannic, J. -m. Sanfedino, F. Preda, V. Bennani, S. Evain, H. Univ Toulouse DTIS ONERA Toulouse France ISAE SUPAERO Toulouse France ESA-ESTEC Noordwijk Netherlands CNES Toulouse France

Monte Carlo simulations have long been a widely used method in the industry for control system validation. They provide an accurate probability measure for sufficiently frequent phenomena but are often time-consuming and may fail to detect very rare events. Conversely, deterministic techniques such as mu or IQC-based analysis allow fast calculation of worst-case stability margins and performance levels, but in the absence of a probabilistic framework, a control system may be invalidated on the basis of extremely rare events. Probabilistic mu-analysis has therefore been studied since the 1990s to bridge this analysis gap by focusing on rare but nonetheless possible situations that may threaten system integrity. The solution adopted in this paper implements a branch-and-bound algorithm to explore the whole uncertainty domain by dividing it into smaller and smaller subsets. At each step, sufficient conditions involving mu upper bound computations are used to check whether a given requirement-related to the delay margin in the present case-is satisfied or violated on the whole considered subset. Guaranteed bounds on the exact probability of delay margin satisfaction or violation are then obtained, based on the probability distributions of the uncertain parameters. The difficulty here arises from the exponential term e-tau s classically used to represent a delay tau, which cannot be directly translated into the Linear Fractional Representation (LFR) framework imposed by mu-analysis. Two different approaches are proposed and compared in this paper to replace the set of delays e-tau s,tau is an element of[0 phi]. First, an equivalent representation using a rational function with unit gain and phase variations that exactly cover those of the original delays, resulting in an LFR with frequency-dependent uncertainty bounds. Then, Pad & eacute;approximations, whose order is chosen to handle the trade-off between conservatism and complexity. A constructive way to derive minimal

关键词： branch-and-bound algorithms linear fractional representation probabilistic mu-analysis robustness analysis uncertain systems

来源：评论

学校读者我要写书评

暂无评论

Graphics processing unit-accelerated bounding for branch-and-bound applied to a permutation problem using data access optimization

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2014年第16期26卷 2667-2683页

作者： Melab, N. Chakroun, I. Bendjoudi, A. Univ Lille 1 CNRS LIFL INRIA Lille Nord Europe F-59655 Villeneuve Dascq France CERIST Algiers 16030 Algeria

branch-and-bound (B&B) algorithms are attractive methods for solving to optimality combinatorial optimization problems using an implicit enumeration of a dynamically built tree-based search space. Nevertheless, they are time-consuming when dealing with large problem instances. Therefore, pruning tree nodes (subproblems) is traditionally used as a powerful mechanism to reduce the size of the explored search space. Pruning requires to perform the bounding operation, which consists of applying a lower bound function to the subproblems generated during the exploration process. Preliminary experiments performed on the Flow-Shop scheduling problem (FSP) have shown that the bounding operation consumes over 98% of the execution time of the B&B algorithm. In this paper, we investigate the use of graphics processing unit (GPU) computing as a major complementary way to speed up the search. We revisit the design and implementation of the parallel bounding model on GPU accelerators. The proposed approach enables data access optimization. Extensive experiments have been carried out on well-known FSP benchmarks using an Nvidia Tesla C2050 GPU card. Compared to a CPU-based single core execution using an Intel Core i7-970 processor without GPU, speedups higher than 100 times faster are achieved for large problem instances. At an equivalent peak performance, GPU-accelerated B&B is twice faster than its multi-core counterpart. Copyright (c) 2013 John Wiley & Sons, Ltd.

关键词： massively parallel computing GPU computing branch-and-bound algorithms lower bounding flow-shop scheduling

来源：评论

学校读者我要写书评

暂无评论

branch-and-bound processing of ranked queries

引用

INFORMATION SYSTEMS 2007年第3期32卷 424-445页

作者： Tao, Yufei Hristidis, Vagelis Papadias, Dimitris Papakonstantinou, Yannis Hong Kong Univ Sci & Technol Dept Comp Sci Hong Kong Hong Kong Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Florida Int Univ Sch Comp & Informat Sci Miami FL 33199 USA Univ Calif San Diego Dept Comp Sci & Engn La Jolla CA 92093 USA

Despite the importance of ranked queries in numerous applications involving multi-criteria. decision making, they are not efficiently supported by traditional database systems. In this paper, we propose a simple yet powerful technique for processing such queries based on multi-dimensional access methods and branch-and-bound search. The advantages of the proposed methodology are: (i) it is space efficient, requiring only a single index on the given relation (storing each tuple at most once), (ii) it achieves significant (i.e., orders of magnitude) performance gains with respect to the current state-of-the-art, (iii) it can efficiently handle data updates, and (iv) it is applicable to other important variations of ranked search (including the support for non-monotone preference functions), at no extra space overhead. We confirm the superiority of the proposed methods with a detailed experimental study. (C) 2006 Elsevier B.V. All rights reserved.

关键词： databases ranked queries R-tree branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

AN LC branch-AND-bound ALGORITHM FOR THE MODULE ASSIGNMENT PROBLEM

引用

INFORMATION PROCESSING LETTERS 1989年第2期32卷 61-71页

作者： CHERN, MS CHEN, GH LIU, P NATL TAIWAN UNIV DEPT COMP SCI & INFORMAT ENGNTAIPEITAIWAN

Distributed processing has been a subject of recent interest due to the availability of computer networks. Over the past few years it has led to the identification of several challenging problems. One of these is the problem of optimally distributing program modules over a distributed processing system. This paper presents an LC (Least Cost) branch-and-bound algorithm to find an optimal assignment that minimizes the sum of execution costs and communication costs. Experimental results show that, for over half of the randomly generated instances, the saving rates exceed 99%.

关键词： branch-and-bound algorithms module assignment problem distributed processing system

来源：评论

学校读者我要写书评

暂无评论

A branch-AND-bound ALGORITHM FOR THE CAPACITATED VEHICLE-ROUTING PROBLEM ON DIRECTED-GRAPHS

引用

OPERATIONS RESEARCH 1994年第5期42卷 846-859页

作者： FISCHETTI, M TOTH, P VIGO, D UNIV BOLOGNA SCH ENGNDEISI-40126 BOLOGNAITALY

We consider the asymmetric capacitated vehicle routing problem (CVRP), a particular case of the standard asymmetric vehicle routing problem in which only the vehicle capacity constraints are imposed. CVRP is known to be NP-hard and finds practical applications in distribution and scheduling. We describe two new bounding procedures for CVRP, based on the so-called additive approach. Each procedure computes a sequence of nondecreasing lower bounds, obtained by solving different relaxations of CVRP. Effective implementations of the procedures are also outlined which considerably reduce the computational effort. The two procedures are combined into an overall bounding algorithm. A branch-and-bound exact algorithm is then proposed, whose performance is enhanced by means of reduction procedures, dominance criteria, and feasibility checks. Extensive computational results on both real-world and random test problems are presented, showing that the proposed approach favorably compares with previous algorithms from the literature.

关键词： programming algorithms: bounding procedures branch-and-bound algorithms transportation: asymmetric capacitated vehicle routing

来源：评论

学校读者我要写书评

暂无评论

Recasting and optimizing intersection automation as a connected-and-automated-vehicle (CAV) scheduling problem: A sequential branch-and-bound search approach in phase-time-traffic hypernetwork

引用

TRANSPORTATION RESEARCH PART B-METHODOLOGICAL 2017年 105卷 479-506页

作者： Li, Pengfei (Taylor) Zhou, Xuesong Mississippi State Univ Dept Civil & Environm Engn Mississippi State MS 39762 USA Arizona State Univ Sch Sustainable Engn & Built Environm Tempe AZ 85287 USA

It is a common vision that connected and automated vehicles (CAVs) will increasingly appear on the road in the near future and share roads with traditional vehicles. Through sharing real-time locations and receiving guidance from infrastructure, a CAV's arrival and request for green light at intersections can be approximately predicted along their routes. When many CAVs from multiple approaches at intersections place such requests, a central challenge is how to develop an intersection automation policy (IAP) to capture complex traffic dynamics and schedule resources (green lights) to serve both CAV requests (interpreted as request for green lights on a particular signal phase at time t) and traditional vehicles. To represent heterogeneous vehicle movements and dynamic signal timing plans, we first formulate the IAP optimization as a special case of machine scheduling problem using a mixed integer linear programming formulation. Then we develop a novel phase-time-traffic (PTR) hypernetwork model to represent heterogeneous traffic propagation under traffic signal operations. Since the IAP optimization;by nature, is a special sequential decision process, we also develop sequential branch-and-bound search algorithms over time to IAP optimization considering both CAVs and traditional vehicles in the PTR hypernetwork. As the critical part of the branch-and-bound search, special dominance and bounding rules are also developed to reduce the search space and find the exact optimum efficiently. Multiple numerical experiments are conducted to examine the performance of the proposed IAP optimization approach. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Intersection automation policy Traffic signal control Phase-time network branch-and-bound algorithms Automated vehicle Connected vehicle

来源：评论

学校读者我要写书评

暂无评论

A branch-AND-bound METHOD FOR MULTICOMMODITY LOCATION WITH BALANCING REQUIREMENTS

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1993年第3期65卷 368-382页

作者： CRAINIC, TG DELORME, L DEJAX, P UNIV MONTREAL CTR RECH TRANSPORTSMONTREAL H3C 3J7QUEBECCANADA HYDRO QUEBEC IREQVP RECHVARENNESPQCANADA ECOLE CENT PARIS PROD LOGIST LABCHATENAY MALABRYFRANCE

We present a branch-and-bound algorithm for the multicommodity location-allocation problem with balancing requirements. Although the formulation displays a number of characteristics common to classical location models, it also unveils, due to the presence of the balancing requirements, a network flow structure that is most favorable to efficient algorithmic developments. In particular, tight bounds may be efficiently computed by using a reformulation of the weak relaxation of the problem as a minimum cost multicommodity flow problem. We also develop and analyse various branching criteria, and show that the branching rules which form the most efficient branch-and-bound procedure for the present problem are quite different from those used to solve classical location problems. The experimentation has been conducted both on several randomly generated problems and on a large scale application.

关键词： MULTICOMMODITY LOCATION ALLOCATION MODELS EMPTY FLOW BALANCING FLEET MANAGEMENT CONTAINER TRANSPORTATION branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：