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

An exact algorithm for the precedence-constrained single-machine scheduling problem

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2013年第2期229卷 345-352页

作者： Tanaka, Shunji Sato, Shun Kyoto Univ Dept Elect Engn Nishikyo Ku Kyoto 6158510 Japan

This study proposes an efficient exact algorithm for the precedence-constrained single-machine scheduling problem to minimize total job completion cost where machine idle time is forbidden. The proposed algorithm is based on the SSDP (Successive Sublimation Dynamic Programming) method and is an extension of the authors' previous algorithms for the problem without precedence constraints. In this method, a lower bound is computed by solving a Lagrangian relaxation of the original problem via dynamic programming and then it is improved successively by adding constraints to the relaxation until the gap between the lower and upper bounds vanishes. Numerical experiments will show that the algorithm can solve all instances with up to 50 jobs of the precedence-constrained total weighted tardiness and total weighted earliness-tardiness problems, and most instances with 100 jobs of the former problem. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Scheduling Single-machine Precedence constraints exact algorithm Lagrangian relaxation Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for minimum distortion embedding

引用

THEORETICAL COMPUTER SCIENCE 2011年第29期412卷 3530-3536页

作者： Fomin, Fedor V. Lokshtanov, Daniel Saurabh, Saket Univ Bergen Dept Informat N-5020 Bergen Norway Univ Calif San Diego Dept Comp Sci & Engn San Diego CA 92103 USA Inst Math Sci Chennai 600113 Tamil Nadu India

Let G be an unweighted connected graph on n vertices. We show that an embedding of the shortest path metric of G into the line with minimum distortion can be found in time 5(n+0(n)). This is the first algorithm breaki... 详细信息

关键词： exact algorithm Metric embedding Distortion

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for maximum lifetime data gathering tree without aggregation in wireless sensor networks

引用

WIRELESS NETWORKS 2015年第1期21卷 281-295页

作者： Zhu, Xiaojun Wu, Xiaobing Chen, Guihai Nanjing Univ Aeronaut & Astronaut Coll Comp Sci & Technol Nanjing 210016 Jiangsu Peoples R China Nanjing Univ State Key Lab Novel Software Technol Nanjing 210023 Jiangsu Peoples R China Shanghai Jiao Tong Univ Shanghai Key Lab Scalable Comp & Syst Shanghai 200240 Peoples R China

In wireless sensor networks, maximizing the lifetime of a data gathering tree without aggregation has been proved to be NP-complete. In this paper, we prove that, unless P = NP, no polynomial-time algorithm can approximate the problem with a factor strictly greater than 2/3. The result even holds in the special case where all sensors have the same initial energy. Existing works for the problem focus on approximation algorithms, but these algorithms only find sub-optimal spanning trees and none of them can guarantee to find an optimal tree. We propose the first non-trivial exact algorithm to find an optimal spanning tree. Due to the NP-hardness nature of the problem, this proposed algorithm runs in exponential time in the worst case, but the consumed time is much less than enumerating all spanning trees. This is done by several techniques for speeding up the search. Featured techniques include how to grow the initial spanning tree and how to divide the problem into subproblems. The algorithm can handle small networks and be used as a benchmark for evaluating approximation algorithms.

关键词： Wireless sensor networks Data gathering tree Maximum lifetime exact algorithm Inapproximability

来源：评论

学校读者我要写书评

暂无评论

On the complexity of exact algorithm for L(2,1)-labeling of graphs

引用

INFORMATION PROCESSING LETTERS 2011年第14期111卷 697-701页

作者： Junosza-Szaniawski, Konstanty Rzazewski, Pawel Warsaw Univ Technol Fac Math & Informat Sci PL-00661 Warsaw Poland

L(2, 1)-labeling is a graph coloring model inspired by a frequency assignment in telecommunication. It asks for such a labeling of vertices with nonnegative integers that adjacent vertices get labels that differ by at least 2 and vertices in distance 2 get different labels. It is known that for any k >= 4 it is NP-complete to determine if a graph has a L(2, 1)-labeling with no label greater than k. In this paper we present a new bound on complexity of an algorithm for finding an optimal L(2, 1)-labeling (i.e. an L(2, 1)-labeling in which the largest label is the least possible). We improve the upper complexity bound of the algorithm from O*(3.5616(n)) to O*(3.2361(n)). Moreover, we establish a lower complexity bound of the presented algorithm, which is Omega*(3.0739(n)). (C) 2011 Elsevier B.V. All rights reserved.

关键词： Analysis of algorithms Combinatorial problems Graph algorithms L(2,1)-labeling Graph coloring model exact algorithm

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for single-machine scheduling without machine idle time

引用

JOURNAL OF SCHEDULING 2009年第6期12卷 575-593页

作者： Tanaka, Shunji Fujikuma, Shuji Araki, Mituhiko Kyoto Univ Grad Sch Elect Engn Nishikyo Ku Kyoto 6158510 Japan Matsue Coll Technol Matsue Shimane 6908518 Japan

This study proposes an exact algorithm for the general single-machine scheduling problem without machine idle time to minimize the total job completion cost. Our algorithm is based on the Successive Sublimation Dynamic Programming (SSDP) method. Its major drawback is heavy memory usage to store dynamic programming states, although unnecessary states are eliminated in the course of the algorithm. To reduce both memory usage and computational efforts, several improvements to the previous algorithm based on the SSDP method are proposed. Numerical experiments show that our algorithm can optimally solve 300 jobs instances of the total weighted tardiness problem and the total weighted earliness-tardiness problem, and that it outperforms the previous algorithms specialized for these problems.

关键词： Single-machine scheduling exact algorithm Time-indexed formulation Lagrangian relaxation Successive sublimation dynamic programming method

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for vehicle routing and scheduling problem of free pickup and delivery service in flight ticket sales companies based on set-partitioning model

引用

JOURNAL OF INTELLIGENT MANUFACTURING 2011年第5期22卷 789-799页

作者： Dong, Gang Tang, Jiafu Lai, Kin Keung Kong, Yuan City Univ Hong Kong Dept Management Sci Kowloon Hong Kong Peoples R China Northeastern Univ Inst Syst Engn Shenyang Peoples R China

This paper addresses a vehicle routing and scheduling problem arising in Flight Ticket Sales Companies for the service of free pickup and delivery of airline passengers to the airport. The problem is formulated under the framework of Vehicle Routing Problem with Time Windows (VRPTW), with the objective of minimizing the total operational costs, i.e. fixed start-up costs and variable traveling costs. A 0-1 mixed integer programming model is presented, in which service quality is factored in constraints by introducing passenger satisfaction degree functions that limit time deviations between actual and desired delivery times. The problem addressed in this paper has two distinctive characteristics-small vehicle capacities and tight delivery time windows. An exact algorithm based on the set-partitioning model, concerning both characteristics, is developed. In the first phase of the algorithm the entire candidate set of best feasible routes is generated, and then the optimal solution is obtained by solving the set-partitioning model in the second phase. Finally, we use four actual instances to illustrate application of the proposed algorithm. Moreover, the proposed algorithm is applied to a random instance containing more orders to verify the general effectiveness of the proposed algorithm even if the number of passengers increases in future.

关键词： Routing and scheduling Free pickup and delivery service Flight ticket sales company exact algorithm Set-partitioning model

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for a multicommodity min-cost flow over time problem

引用

Electronic Notes in Discrete Mathematics 2018年 64卷 125-134页

作者： Grande, Enrico Nicosia, Gaia Pacifici, Andrea Roselli, Vincenzo Axioma Inc. London United Kingdom Dipartimento di Ingegneria Università Roma Tre Roma Italy Dipartimento di Ingegneria Civile e Ingegneria Informatica Università di Roma Tor Vergata Roma Italy Dipartimento di Ingegneria Università Roma Tre Roma Italy

Flows over time problems consider finding optimal dynamic flows over a network where capacities and transit times on arcs are given. In this paper we study a multicommodity flow over time problem in which no storage of flow at nodes is allowed and solutions are restricted to loopless flow-paths. We propose an exact algorithm based on a column generation approach for a path-based linear programming model and present the results of a preliminary computational study. © 2018 Elsevier B.V.

关键词： column generation exact algorithm flows over time linear programming multicommodity flow

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for a core/periphery bipartitioning problem

引用

SOCIAL NETWORKS 2011年第1期33卷 12-19页

作者： Brusco, Michael Florida State Univ Coll Business Dept Mkt Tallahassee FL 32306 USA

The discrete optimization problem associated with partitioning a set of actors into core and periphery subsets has typically been approached using approximate procedures such as exchange heuristics, genetic algorithms, and simulated annealing. Although these procedures are effective and scalable for large networks, they do not guarantee an optimal bipartition. In this paper, an exact algorithm is presented for a core/periphery bipartitioning problem. Unlike the approximate procedures in the extant literature, this new algorithm, which is based on the principles of branch-and-bound programming, affords a guarantee of an optimal bipartition. Computational results for empirical and simulated data sets reveal that the proposed algorithm is extremely efficient for networks with 40 or fewer actors, and is often scalable for networks with up to 60 actors. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Core/periphery Bipartition exact algorithm Branch-and-bound

来源：评论

学校读者我要写书评

暂无评论

An Approach to Study the range of perturbations in exact algorithm on Microwave Tomography of Biological targets with different BeamWidth 3

An Approach to Study the range of perturbations in Exact Alg...

引用

THIRD INTERNATIONAL CONFERENCE ON COMPUTER, COMMUNICATION, CONTROL AND INFORMATION TECHNOLOGY (C3IT)

作者： Purkait, Kabita Mondal, Subijit Bose, Subhra Narayan Roy, Rounak Halder, Shuvankar Adhikary, Kalyan Kalyani Govt Engn Coll Dept Elect & Commun Engn Kalyani W Bengal India Mordern Inst Engn & Technol Dept Elect & Commun Engn Kalyani W Bengal India

ISBN: (纸本)9781479944453

In this paper, a study of existing exact algorithm on microwave tomography of high contrast biological model for different sets of transmitting beamwidth has been proposed. Quantitative results of reconstructed images of normal semi human sized numerical model are also presented to exhibit the range of perturbations of complex permittivity of biological tissues can be adapted by the algorithm. The aforesaid algorithm is also applied to detect the diseased portion of the numerical model. A priori information helps to detect precisely the diseased portion after its preliminary detection by the algorithm has been suggested here with the help of a percentage average error.

关键词： Complex Permittivity exact algorithm Imaging Perturbation Tomography

来源：评论

学校读者我要写书评

暂无评论

AN exact algorithm FOR THE FULL TRUCKLOAD PICK-UP AND DELIVERY PROBLEM WITH TIME WINDOWS: CONCEPT AND IMPLEMENTATION DETAILS

AN EXACT ALGORITHM FOR THE FULL TRUCKLOAD PICK-UP AND DELIVE...

引用

25th European Simulation and Modelling Conference (ESM 2011)

作者： Janssens, Gerrit K. Braekers, Kris Univ Hasselt Hasselt Univ Transportat Res Inst IMOB B-3590 Diepenbeek Belgium

ISBN: (纸本)9789077381663

Intermodal goods transport is characterized by a main transport by rail, barge or seaborne vessel, preceded and followed by short in time but expensive road transport. Many times trucks pick-up or deliver a single container which leads to a full truckload vehicle routing problem in terms of economically efficient transport services. Time windows induced by the customer or due to external situations increase the complexity of an efficient planning by a logistics provider. An exact algorithm for this type of pick-up and delivery problem is developed and the details of its implementation are explained. A set partitioning problem is automatically generated and solved by means of the Lingo software.

关键词： exact algorithm full truckload pick-up and delivery set partitioning

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：