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

Preemptive scheduling on uniform machines to minimize mean flow time

COMPUTERS & OPERATIONS RESEARCH 2009年第10期36卷 2816-2821页

作者： Kravchenko, Svetlana A. Werner, Frank Otto VonGuericke Univ Magdegurg Fak Math D-39106 Magdeburg Germany United Inst Informat Problems Minsk 220012 BELARUS

A set of jobs has to be scheduled on parallel uniform machines. Each machine can handle at most one job at a time. Each job becomes available for processing at its release date. All jobs have the same execution requirement, and each machine has a known speed. The processing of any job may be interrupted arbitrarily often and resumed later on any machine. We want to find a schedule that minimizes the sum of completion times, i.e., we consider problem Q vertical bar r(j),p(j) = p, pmtn vertical bar Sigma C-j whose complexity status was open. in this paper, we give a polynomial algorithm for the above problem. The algorithm is based on a reduction of the scheduling problem to a linear program. The crucial condition for implementing the proposed reduction is the known order of job completion times. (C) 2008 Elsevier Ltd. All rights reserved.

关键词： Parallel uniform machines Linear programming Maximum flow polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

Location problems with continuous demand and unreliable facilities: Applications of families of incremental Voronoi diagrams

引用

DISCRETE APPLIED MATHEMATICS 2021年 300卷 36-55页

作者： Averbakh, Igor Berman, Oded Kalcsics, Jorg Krass, Dmitry Univ Toronto Scarborough Dept Management 1265 Mil Trail Toronto ON M1C 1A4 Canada Univ Toronto Rotman Sch Management 105 St George St St George ON M5E 3E6 Canada Univ Edinburgh Sch Math Peter Guthrie Tait Rd Edinburgh EH9 3FD Midlothian Scotland

We consider conditional facility location problems with unreliable facilities that can fail with known probabilities. The demand is uniformly distributed over a convex polygon in the rectilinear plane where a number of facilities are already present, and it is required to optimally locate another facility. We analyze properties of the exponential family of incremental Voronoi diagrams associated with possible realizations of the set of operational facilities, and, based on this analysis, present polynomial algorithms for three conditional location problems. The approach can be extended to various other conditional location problems with continuous demand and unreliable facilities, under different probabilistic models including ones with correlated facility failures. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Reliable facility location Continuous location Voronoi diagram polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

Weak Coverage of a Rectangular Barrier

引用

algorithmICA 2020年第4期82卷 721-746页

作者： Dobrev, Stefan Kranakis, Evangelos Krizanc, Danny Lafond, Manuel Manuch, Jan Narayanan, Lata Opatrny, Jaroslav Stacho, Ladislav Slovak Acad Sci Inst Math Bratislava Slovakia Carleton Univ Sch Comp Sci Ottawa ON Canada Wesleyan Univ Dept Math & Comp Sci Middletown CT USA Univ Ottawa Dept Math & Stat Ottawa ON Canada Univ British Columbia Dept Comp Sci Vancouver BC Canada Concordia Univ Dept Comp Sci & Software Engn Montreal PQ Canada Simon Fraser Univ Dept Math Burnaby BC Canada

Assume n wireless mobile sensors are initially dispersed in an ad hoc manner in a rectangular region. Each sensor can monitor a circular area of specific diameter around its position, called the sensor diameter. Sensors are required to move to final locations so that they can there detect any intruder crossing the region in a direction parallel to the sides of the rectangle, and thus provide weak barrier coverage of the region. We study three optimization problems related to the movement of sensors to achieve weak barrier coverage: minimizing the number of sensors moved (MinNum), minimizing the average distance moved by the sensors (MinSum), and minimizing the maximum distance moved by any sensor (MinMax). We give an O(n(3/2)) time algorithm for the MinNum problem for sensors of diameter 1 that are initially placed at integer positions;in contrast the problem is shown to be NP-complete even for sensors of diameter 2 that are initially placed at integer positions. We show that the MinSum problem is solvable in O(n log n) time for theManhattan metric and sensors of identical diameter (homogeneous sensors) in arbitrary initial positions, while it is NP-complete for heterogeneous sensors. Finally, we prove that even very restricted homogeneous versions of the MinMax problem are NP-complete.

关键词： Barrier coverage Mobile sensors Optimizing sensor movements polynomial algorithm NP-complete problem

来源：评论

学校读者我要写书评

暂无评论

Preemptive versus nonpreemptive scheduling of biprocessor tasks on dedicated processors

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1996年第2期94卷 242-251页

作者： Kubale, M GDANSK TECH UNIV DEPT FDN INFORMATNARUTOWICZA 11-12PL-80952 GDANSKPOLAND

This paper investigates the computational complexity of preemptive and nonpreemptive scheduling of biprocessor tasks on dedicated processors in general and some of its special cases. We consider two criteria of optimality: the schedule length and sum of task completion times. In addition, we analyze the complexity of these problems when precedence constraints are involved. We show that in general all these problems are NP-hard in the strong sense.

关键词： biprocessor task edge coloring makespan NP-completeness polynomial algorithm precedence constraints total completion time

来源：评论

学校读者我要写书评

暂无评论

The complexity of finding arc-disjoint branching flows

引用

DISCRETE APPLIED MATHEMATICS 2016年 209卷 16-26页

作者： Bang-Jensen, J. Havet, Frederic Yeo, Anders Univ Southern Denmark Dept Math & Comp Sci DK-5230 Odense Denmark UNSA CNRS I3S Project Coati Sophia Antipolis France INRIA Sophia Antipolis France Singapore Univ Technol & Design Engn Syst & Design 20 Dover Dr Singapore 138682 Singapore Univ Johannesburg Dept Math ZA-2006 Auckland Pk South Africa

The concept of arc-disjoint flows in networks was recently introduced in Bang-Jensen and Bessy (2014). This is a very general framework within which many well-known and important problems can be formulated. In particular, the existence of arc-disjoint branching flows, that is, flows which send one unit of flow from a given source s to all other vertices, generalizes the concept of arc-disjoint out-branchings (spanning out-trees) in a digraph. A pair of out-branchings B-s,1(+), B-s,2(+) from a roots in a digraph D = (V, A) on n vertices corresponds to arc-disjoint branching flows x(1), x(2) (the arcs carrying flow in x(i) are those used in B-s,i(+) = 1, 2) in the network that we obtain from D by giving all arcs capacity n - 1. It is then a natural question to ask how much we can lower the capacities on the arcs and still have, say, two arc-disjoint branching flows from the given root s. We prove that for every fixed integer k >= 2 it is an NP-complete problem to decide whether a network N = (V, A, u) where u(ij) = k for every arc ij has two arc-disjoint branching flows rooted at s. a polynomial problem to decide whether a network N = (V, A, u) on n vertices and u(ij) = n - k for every arc ij has two arc-disjoint branching flows rooted at s. The algorithm for the later result generalizes the polynomial algorithm, due to Lovasz, for deciding whether a given input digraph has two arc-disjoint out-branchings rooted at a given vertex. Finally we prove that under the so-called Exponential Time Hypothesis (ETH), for every epsilon > 0 and for every k(n) with (log(n))(1+epsilon) <= k(n) <= n/2 (and for every large i we have k(n) = i for some n) there is no polynomial algorithm for deciding whether a given digraph contains two arc-disjoint branching flows from the same root so that no arc carries flow larger than n - k(n). (C) 2015 Elsevier B.V. All rights reserved.

关键词： Disjoint branchings Branching flow polynomial algorithm NP-complete

来源：评论

学校读者我要写书评

暂无评论

Spanning k-arc-strong subdigraphs with few arcs in k-arc-strong tournaments

引用

JOURNAL OF GRAPH THEORY 2004年第4期46卷 265-284页

作者： Bang-Jensen, J Huang, J Yeo, A Univ So Denmark Dept Math & Comp Sci DK-5230 Odense Denmark Univ Victoria Dept Math & Stat Victoria BC V8W 3P4 Canada Univ London Royal Holloway & Bedford New Coll Dept Comp Sci Egham TW20 0EX Surrey England

Given a k-arc-strong tournament T, we estimate the minimum number of arcs possible in a k-arc-strong spanning subdigraph of T We give a construction which shows that for each k greater than or equal to 2, there are tournaments Ton n vertices such that every k-arc-strong spanning subdigraph of T contains at least nk + (k(k-1))/(2) arcs. In fact, the tournaments in our construction have the property that every spanning subdigraph with minimum in- and out-degree at least k has nk + (k(k-1))/(2) arcs. This is best possible since it can be shown that every k-arc-strong tournament contains a spanning subdigraph with minimum in- and out-degree at least k and no more than nk + (k(k-1))/(2) arcs. As our main result we prove that every k-arc-strong tournament contains a spanning k-arc-strong subdigraph with no more than nk + 136k(2) arcs. We conjecture that for every k-arc-strong tournament T, the minimum number of arcs in a k-arc-strong spanning subdigraph of T is equal to the minimum number of arcs in a spanning subdigraph of T with the property that every vertex has in- and out-degree at least k. We also discuss the implications of our results on related problems and conjectures. (C) 2004 Wiley Periodicals, Inc.

关键词： tournament connectivity minimum strong spanning subdigraph certificates for connectivity polynomial algorithm MSSS problem MEG problem

来源：评论

学校读者我要写书评

暂无评论

REFINED STUDY ON STRUCTURAL CONTROLLABILITY OF DESCRIPTOR SYSTEMS BY MEANS OF MATROIDS

引用

SIAM JOURNAL ON CONTROL AND OPTIMIZATION 1987年第4期25卷 967-989页

作者： MUROTA, K UNIV TSUKUBA INST SOCIOECON PLANNINGSAKURAIBARAKI 305JAPAN

For a dynamical system described in the descriptor form ${{Fd{\bf x}} / {dt = A{\bf x} + B{\bf u}}}$, where the coefficients are classified into generic parameters and fixed constants, the structural controllability is investigated under a physically reasonable assumption that can be justified by the dimensional analysis. A necessary and sufficient condition for the structural controllability is given in matroid-theoretic terms; the condition can be tested by efficient algorithms for the matroid union/intersection problem.

关键词： 93 93B05 93B25 15 05C50 structural controllability descriptor form matroid algebraic independence polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

Matrix semigroups with constant spectral radius

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2017年 513卷 376-408页

作者： Protasov, V. Yu. Voynov, A. S. Moscow MV Lomonosov State Univ Dept Mech & Math Moscow Russia Natl Res Univ Higher Sch Econ Fac Comp Sci Moscow Russia

Multiplicative matrix semigroups with constant spectral radius (c.s.r.) are studied and applied to several problems of algebra, combinatorics, functional equations, and dynamical systems. We show that all such semigroups are characterized by means of irreducible ones. Each irreducible c.s.r. semigroup defines walks on Euclidean sphere, all its nonsingular elements are similar (in the same basis) to orthogonal. We classify all nonnegative c.s.r. semigroups and arbitrary low-dimensional semigroups. For higher dimensions, we describe five classes and leave an open problem on completeness of that list. The problem of algorithmic recognition of c.s.r. property is proved to be polynomially solvable for irreducible semigroups and undecidable for reducible ones. (C) 2016 Elsevier Inc. All rights reserved.

关键词： Multiplicative semigroup Spectral radius Joint spectral characteristics Convex body Ellipsoid polynomial algorithm Finite matrix group Linear switching systems Fractal curves

来源：评论

学校读者我要写书评

暂无评论

Some single-machine scheduling problems with the extended sum-of-processing-time-based aging effect

引用

INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY 2012年第1-4期59卷 299-309页

作者： Rudek, Radoslaw Wroclaw Univ Econ PL-53345 Wroclaw Poland

In this paper, we analyze some single machine scheduling problems with the aging effect. We extend the sum-of-processing-time-based aging model such that the fatigue caused by each job to the machine is equal to a non-increasing function dependent on the normal processing time of a job and the aging effect is job dependent. Although the proposed model is more general and describes more precisely the real-life settings, we show that the special cases of the maximum completion time and the maximum lateness minimization problems with this model are still polynomially solvable. However, we prove the maximum completion time minimization problem with the sum-of-processing-time-based aging model is strongly NP-hard if some jobs have deadlines and constant processing times. On this basis, we show that the maximum lateness minimization problem with this aging model is also strongly NP-hard.

关键词： Scheduling Deteriorating Aging effect Computational complexity polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

Augmenting edge-connectivity over the entire range in (O)over-tilde(nm) time

引用

JOURNAL OF algorithmS 1999年第2期30卷 253-301页

作者： Nagamochi, H Ibaraki, T Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto 6068501 Japan

For a given undirected graph G = (V, E, c(G)) with edges weighted by nonnegative reals c(G): E --> R+, let Lambda(G)(k) stand for the minimum amount of weights which needs to be added to make G k-edge-connected, and let G*(k) be the resulting graph obtained from G. This paper first shows that function Lambda(G) over the entire range k is an element of [0, + infinity] can be computed in O(nm + n(2) log n) time, and then shows that all G*(k) in the entire range can be obtained from O(n log n) weighted cycles, and such cycles can be computed in O(nm + n(2) log n) time, where n and m are the numbers of vertices and edges, respectively. (C) 1999 Academic Press.

关键词： edge-connectivity minimum cuts graph augmentation polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：