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

Scheduling deteriorating jobs to minimize makespan

NAVAL RESEARCH LOGISTICS 1998年第5期45卷 511-523页

作者： Kubiak, W van de Velde, S Mem Univ Newfoundland Fac Business Adm St Johns NF A1B 3X5 Canada Erasmus Univ Rotterdam Sch Management NL-3000 DR Rotterdam Netherlands

We consider a single-machine problem of scheduling n independent jobs to minimize makespan, in which the processing time of job J(j) grows by w(j) with each time unit its start is delayed beyond a given common critical date d. This processing time is p(j) if J(j) starts by d. We show that this problem is NP-hard, give a pseudopolynomial algorithm that runs in O(nd Sigma(j=1)(n) P-j) time and O(nd) space, and develop a branch-and-bound algorithm that solves instances with up to 100 jobs in a reasonable amount of time. We also introduce the case of bounded deterioration, where the processing time of a job grows no further if the job starts after a common maximum deterioration date D > d. For this case, we give two pseudopolynomial time algorithms: one runs in O(n(2)d(D - d) Sigma(j=1)(n) p(j)) time and O(nd(D - d)) space, the other runs in O(nd Sigma(j=1)(n) w(j)(Sigma(j=1)(n) p(j))(2)) time and O(nd Sigma(j=1)(n) w(j) Sigma(j=1)(n) p(j)) space. (C) 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 511-523, 1998.

关键词： single-machine scheduling deteriorating jobs NP-hardness dynamic programming pseudopolynomial algorithm branch and bound algorithm

来源：评论

学校读者我要写书评

暂无评论

A new strategy for generating shortest addition sequences

引用

COMPUTING 2011年第3期91卷 285-306页

作者： Bahig, Hatem M. Bahig, Hazem M. Ain Shams Univ Fac Sci Dept Math Div Comp Sci Cairo 11566 Egypt

An addition sequence problem is given a set of numbers X = {n (1), n (2), . . . , n (m) }, what is the minimal number of additions needed to compute all m numbers starting from 1? This problem is NP-complete. In this paper, we present a branch and bound algorithm to generate an addition sequence with a minimal number of elements for a set X by using a new strategy. Then we improve the generation by generalizing some results on addition chains (m = 1) to addition sequences and finding what we will call a presumed upper bound for each n (j) , 1 a parts per thousand currency sign j a parts per thousand currency sign m, in the search tree.

关键词： Addition chains Addition sequences branch and bound algorithm High-performance arithmetic Monomials evaluation Vectorial addition chains

来源：评论

学校读者我要写书评

暂无评论

Fire scheduling for planned artillery attack operations under time-dependent destruction probabilities

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2010年第5期38卷 383-392页

作者： Cha, Young-Ho Kim, Yeong-Dae Korea Adv Inst Sci & Technol Dept Ind Engn Taejon 305701 South Korea

In this paper, we consider the fire scheduling problem (FSP) for field artillery, which is the problem of scheduling operations of firing at given targets with a given set of weapons. We consider a situation in which the number of available weapons is smaller than the number of targets, the targets are assigned to the weapons already, and targets may move and hence the probability that a target is destroyed by a firing attack decreases as time passes. We present a branch and bound algorithm for the FSP with the objective of minimizing total threat of the targets, which is expressed as a function of the destruction probabilities of the targets. Results of computational tests show that the suggested algorithm solves problems of a medium size in a reasonable amount of computation time. (C) 2009 Elsevier Ltd. All rights reserved.

关键词： Military Scheduling branch and bound algorithm

来源：评论

学校读者我要写书评

暂无评论

Greedy-Heuristic-Aided Mixed-Integer Linear Programming Approach for Arrival Scheduling

引用

JOURNAL OF AEROSPACE INFORMATION SYSTEMS 2013年第7期10卷 323-336页

作者： Cao, Yi Rathinam, Sivakumar Sun, Dengfeng Purdue Univ Sch Aeronaut & Astronaut W Lafayette IN 47906 USA Texas A&M Univ College Stn TX 77843 USA

Scheduling arriving aircraft in terminal airspace can be formulated using mixed-integer linear programming and solved by a branch and bound algorithm. Given that the problem is intrinsically nondeterministic polynomial-time hard, success in solving the problem within a reasonable time is not always guaranteed. This paper proposes an efficient optimization approach that calculates the minimum total delay necessary for a conflict-free arrival sequence. Agreedy heuristic is developed to find a feasible solution quickly, which serves as a "hot start" so that the branch and bound algorithm can prune as many search tree nodes as it can. Unnecessary searching is thus saved. The greedy heuristic also provides an estimated upper bound for the maximum delay that guarantees a feasible solution for the mixed-integer linear programming. In addition, it identifies a group of aircraft associated with high delays, which are suspended in the first stage of scheduling and sequenced in the second stage based on available time slots. This tactic decreases the computational difficulty. The proposed approach is validated using arriving traffic in 40 major United States airports. Compared to a standalone mixed-integer linear programming, the greedy-heuristic-aided mixed-integer linear programming yields suboptimal solutions in a more efficient manner, and the compromise of optimality is limited.

关键词： Mixed Integer Linear Programming branch and bound algorithm Airspace Ronald Reagan Washington National Airport Estimated Time of Arrival Aircraft Situation Display to Industry Traffic Management Advisor Standard Terminal Arrival Route Center TRACON Automation System Wingtip Vortices

来源：评论

学校读者我要写书评

暂无评论

Maximization of the ratio of two convex quadratic functions over a polytope

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2001年第1期20卷 43-60页

作者： Gotoh, JY Konno, H Univ Tsukuba Inst Policy & Planning Sci Tsukuba Ibaraki 305 Japan Chuo Univ Dept Ind & Syst Engn Tokyo 112 Japan

In this paper, we will develop an algorithm for solving a quadratic fractional programming problem which was recently introduced by Lo and MacKinlay to construct a maximal predictability portfolio, a new approach in portfolio analysis. The objective function of this problem is defined by the ratio of two convex quadratic functions, which is a typical global optimization problem with multiple local optima. We will show that a well-designed branch-and-bound algorithm using (i) Dinkelbach's parametric strategy, (ii) linear overestimating function and (iii) omega -subdivision strategy can solve problems of practical size in an efficient way. This algorithm is particularly efficient for Lo-MacKinlay's problem where the associated nonconvex quadratic programming problem has low rank nonconcave property.

关键词： fractional programming Dinkebach's approach branch and bound algorithm global optimization maximizing predictability portfolio

来源：评论

学校读者我要写书评

暂无评论

Efficient Global algorithms for Transmit Beamforming Design in ISAC Systems

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2024年 72卷 4493-4508页

作者： Wu, Jiageng Wang, Zhiguo Liu, Ya-Feng Liu, Fan Jilin Univ Sch Math Changchun 130012 Peoples R China Sichuan Univ Coll Math Chengdu 610064 Sichuan Peoples R China Chinese Acad Sci Acad Math & Syst Sci Inst Computat Math & Sci Engn Comp State Key Lab Sci & Engn Comp Beijing 100190 Peoples R China Southeast Univ Natl Mobile Commun Res Lab Nanjing 210096 Peoples R China

In this paper, we propose a MIMO transmit beamforming optimization model for joint radar sensing and multiuser communications, where the design of the beamformers is formulated as an optimization problem whose objective is a weighted combination of the sum rate and the CramerRao bound, subject to the transmit power budget. Obtaining the global solution for the formulated nonconvex problem is a challenging task, since the sum-rate maximization problem itself (even without considering the sensing metric) is known to be NP-hard. The main contributions of this paper are threefold. Firstly, we derive an optimal closed-form solution to the formulated problem in the single-user case and the multi-user case where the channel vectors of different users are orthogonal. Secondly, for the general multi-user case, we propose a novel branch and bound (B&B) algorithm based on the McCormick envelope relaxation. The proposed algorithm is guaranteed to find the globally optimal solution to the formulated problem. Thirdly, we design a graph neural network (GNN) based pruning policy to determine irrelevant nodes that can be directly pruned in the proposed B&B algorithm, thereby significantly reducing the number of unnecessary enumerations therein and improving its computational efficiency. Simulation results show the efficiency of the proposed vanilla and GNN-based accelerated B&B algorithms.

关键词： branch and bound algorithm McCormick envelope relaxation global optimality transmit beamforming sum-rate maximization.

来源：评论

学校读者我要写书评

暂无评论

Iterative coloring extension of a maximum clique

引用

NAVAL RESEARCH LOGISTICS 2001年第6期48卷 518-550页

作者： Caramia, M Dell'Olmo, P Univ Roma Tor Vergata Dipartimento Informat Sistemi & Prod I-00133 Rome Italy Univ Roma La Sapienza Dipartimento Stat Probabil & Stat Applicate I-00185 Rome Italy

In this paper we present an improved branch and bound algorithm for the vertex coloring problem. The idea is to try to extend the coloring of a maximum clique to its adjacent vertices. If this succeeds. its successive neighbors are considered;in case of failure (i.e., in the case the initial colors are not sufficient), working on the subgraph induced by the maximum clique and its neighborhood, the lower bound is improved by seeking for an optimal coloring of this subgraph by branch and bound. The process is repeated iteratively until the whole graph is examined. The iterative scheme exploits a further lower bound obtained by integrating a simple algorithm into the maximum clique search, and a new method to compute upper bounds on subgraphs. Furthermore, a new branching rule and a method for the selection of the initial maximum clique are presented. Extensive computational results and comparisons with existing exact coloring algorithms on random graphs and benchmarks are given. (C) 2001 John Wiley & Sons, Inc.

关键词： branch and bound algorithm combinatorial optimization exact coloring lower bound maximum clique

来源：评论

学校读者我要写书评

暂无评论

Optimal asset management strategies for mixed transit fleet

引用

TRANSPORTATION RESEARCH PART A-POLICY AND PRACTICE 2018年第Nov.期117卷 103-116页

作者： Ngo, Huan Hoang Shah, Rohan Mishra, Sabyasachee Univ Memphis Dept Civil Engn 104 Engn Sci Bldg Memphis TN 38152 USA CDM Smith Inc Transportat Serv Grp 9430 Res BlvdSuite 1-200 Austin TX 78759 USA

Transit agencies require equitable and optimal allocation of funds among transit agencies for not just regular operations and maintenance, but also for asset management including purchase of new buses and rehabilitation of aging fleet. The paper proposes a hierarchical structure of resource allocation where federal funding is routed through the state, and ultimately to local transit agencies. The framework encompasses multiple dimensions such as selection of different improvement program options (rehabilitation, remanufacturing, and replacement) of a mixed transit fleet spread over a temporally continuous planning period. It leverages optimization models for capital allocation among transit agencies in the state. Four sub-models are developed-two maximizing passenger miles traveled, and the other two maximizing the total fleet wide remaining life, all under agency-specific budget, capacity and policy constraints, and planning objectives. They are applied on real-world data from set of transit agencies spread across the state of Tennessee, containing a heterogenous fleet of 254 total buses at various levels of aging. Results indicate that by application of the framework, an average 40 percent additional mileage is generated through the planning period with the same levels of fleet size, with nearly 30 percent of the fleet receiving some form of improvement treatment per year.

关键词： Optimal resource allocation Transit asset management Rehabilitation and replacement Integer programming branch and bound algorithm

来源：评论

学校读者我要写书评

暂无评论

QoS-Aware Power Management in LTE-A Networks Under Heterogeneous Traffics

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2018年第1期67卷 674-688页

作者： Ozcevik, Muge Erel Secinti, Gokhan Canberk, Berk Istanbul Tech Univ Dept Comp Engn TR-34469 Istanbul Turkey Northeastern Univ Dept Elect & Comp Engn Boston MA 02115 USA

In 3GPP LTE-A releases v.8 and beyond, the plug and play nature of the eNodeBs lets a dense deployment of eNodeBs, thus, causing over-provisioned network infrastructure. Here, while most of the recent studies aim to optimize power consumption on a single traffic type, we provide a novel framework that corresponds both power adjustment and quality of users (QoS) requirements of end-users with multitraffic types. In this manner, we propose a novel energy efficiency coefficient (EEC) considering QoS and channel utilization while reducing power consumption. Moreover, our proposed resource auction module assigns resource blocks to low-utilized cellular networks. Furthermore, the traffic types are modeled with a queuing theoretic approach. We also define an optimization problem that employs novel EEC parameters to determine new power levels (8-levels) for eNodeBs' configurations with less power consumption. To solve this optimization problem, we introduce a novel heuristic called "Multi Level branch and bound algorithm" (MLBB). MLBB algorithm contains two nested branch and bound algorithms that manipulates end-users differently. Consequently, our proposed methodology serves end-users with 67% better QoS than the conventional mechanisms.

关键词： branch and bound algorithm energy efficiency heterogeneous traffic LTE-A power consumption

来源：评论

学校读者我要写书评

暂无评论

Security Vulnerabilities and Protection algorithms for Backpressure-Based Traffic Signal Control at an Isolated Intersection

引用

IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 2022年第7期23卷 6406-6417页

作者： Yen, Chia-Cheng Ghosal, Dipak Zhang, Michael Chuah, Chen-Nee Univ Calif Davis Dept Comp Sci Davis CA 95616 USA Univ Calif Davis Dept Civil & Environm Engn Davis CA 95616 USA Univ Calif Davis Dept Elect & Comp Engn Davis CA 95616 USA

There is an increasing trend in the use of wireless communication along with new traffic signal control (TSC) algorithms to leverage and accommodate connected and autonomous vehicles. However, this development has increased the potential for cyber-attacks on TSC that can undermine the benefits of these new algorithms. An advanced persistent adversary can learn the behavior of TSC algorithms and launch attacks to preferentially get green time and/or to create traffic congestion in one intersection which can spread to the entire network. In this paper, we consider backpressure-based (BP-based) TSC algorithms and compare their performance under two misinformation attacks 1) time spoofing attack in which vehicles alter their arrival times at the intersection and 2) ghost vehicle attack in which vehicles disconnect the wireless communication and thereby hide from the TSC. We show that these misinformation can influence the signal phases determined by BP-based TSC algorithms. We consider an adversary that determines a set of arriving vehicles to be attack vehicles from many candidate sets (attack strategies) in order to maximize the number of disrupted signal phases. We show that by formulating the problem as a 0/1 Knapsack problem, the adversary can explore the space of attack strategies and determine the optimal strategy that maximally compromises the performance in terms of average delay and fairness. We propose two protection algorithms, namely, auction-based (APA) and hybrid-based (HPA) algorithms and show that they are able to mitigate the impacts of the misinformation attacks.

关键词： Traffic signal control backpressure-based scheduling algorithm time spoofing attack ghost vehicle attack 0/1 Knapsack problem branch and bound algorithm counter-measure delay distribution fairness simulation analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：