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

Parallel machine scheduling with a deteriorating maintenance activity and total absolute differences penalties

APPLIED MATHEMATICS AND COMPUTATION 2011年第20期217卷 8093-8099页

作者： Wang, Ji-Bo Wei, Cai-Min Shenyang Aerosp Univ Sch Sci Shenyang 110136 Peoples R China Shantou Univ Dept Math Shantou 515063 Peoples R China

In this paper we consider identical parallel machines scheduling problems with a deteriorating maintenance activity. In this model, each machine has a deteriorating maintenance activity, that is, delaying the maintenance increases the time required to perform it. We need to make a decision on when to schedule the rate-modifying activities and the sequence of jobs to minimize some objective function. We concentrate on two goals separately, namely, minimizing the total absolute differences in completion times (TADC) and the total absolute differences in waiting times (TADW). We show that the problems remain polynomially solvable under the proposed model. (C) 2011 Elsevier Inc. All rights reserved.

关键词： Scheduling Parallel machine Maintenance activity polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

An efficient and versatile algorithm for computing the covariance function of an ARMA process

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 1998年第6期46卷 1591-1600页

作者： Soderstrom, T Jezek, J Kucera, V Uppsala Univ Dept Technol Syst & Control Grp Uppsala Sweden Acad Sci Czech Republ Inst Informat Theory & Automat CR-18208 Prague Czech Republic

Computation of an ARMA covariance function is a common ingredient in analysis and synthesis of various problems in stochastic control, estimation, and signal processing, Several approaches can be used for this purpose. In this paper, we present an algorithm based on simple polynomial calculations. Compared with alternative strategies, it has small computational load, shows good numerical robustness, and can be extended to handle multivariable ARMA processes, even with complex-valued coefficients.

关键词： ARMA process covariance function numerical algorithm numerical robustness polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

An iterative algorithm for two level hierarchical time minimization transportation problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2015年第3期246卷 700-707页

作者： Sharma, Anuj Verma, Vanita Kaur, Prabhjot Dahiya, Kalpana Panjab Univ Dept Comp Sci & Applicat Chandigarh 160014 India Panjab Univ Dept Math Chandigarh 160014 India Panjab Univ Univ Inst Engn & Technol Chandigarh 160014 India

This paper discusses a two level hierarchical time minimization transportation problem, in which the whole set of source-destination links consists of two disjoint partitions namely Level-I and Level-II links. Some quantity of a homogeneous product is first shipped from sources to destinations by Level-I decision makers using only Level-I links, and on its completion the Level-II decision maker transports the remaining quantity of the product in an optimal fashion using only Level-II links. The objective is to find that feasible solution for Level-I decision corresponding to which the optimal feasible solution for Level-II decision maker is such that the sum of shipment times in Level-I and Level-Ills minimum. A polynomial time iterative algorithm is proposed to solve the two level hierarchical time minimization transportation problem. At each iteration a lexicographic optimal solution of a restricted version of a related standard time minimization transportation problem is examined to generate a pair of Level-I and Level-II shipment times and finally the global optimal solution is obtained by selecting the best out of these generated pairs. Numerical illustration is included in support of theory. (C) 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.

关键词： Global optimization Concave minimization Transportation problem Hierarchical optimization polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

Maximizing the number of mixed packages subject to variety constraints

引用

COMPUTERS & OPERATIONS RESEARCH 1999年第13期26卷 1323-1333页

作者： Robb, DJ Trietsch, D Univ Auckland Dept Management Sci & Informat Syst Auckland New Zealand

We develop a polynomial-time algorithm to optimise a variant of the one-dimensional bin-packing problem with side constraints. We also develop a pseudo-polynomial procedure to actually implement that optimal solution. The specific application is the allocation of excess of a population of various types of cards (e.g., left over from a previous selling season) to fixed-sized "variety packs" which guarantee a given level of variety (i.e., no more than k of any type of card). Some card types with large numbers (perhaps the most unpopular from the previous season) may have to be discarded to preserve the variety constraint. The method developed employs a test for feasibility of a given number of packs and includes a simple allocation procedure. A numerical example is provided along with (worst-case) complexity calculations. In addition, we solve a practical problem in which an organisation marketing Christmas cards sought to determine the impact of pack size and variety level on the level of unallocated cards. Scope and purpose Organisations involved in the stocking and sale of seasonal "style" items such as greeting cards, may periodically face excess stock of various items (e.g., from previous seasons), and may decide to market the items in packs guaranteed to contain a certain degree of variety. Our objective in this paper is to show how to maximise the number of card packs that can be formed from an assortment of excess stock, where there is a marketing-based variety constraint restricting the number of each type of card in each pack. The solution procedure developed is intuitively appealing and can be easily implemented on a spreadsheet. In addition to presenting a numerical example, we provide results from the application and implementation of the method in the card sales operations of a charitable organisation. The method could also have broader application in other settings where variety is sought - such as in groups or teams. (C) 1999 Elsevier Science Ltd. All

关键词： bin packing polynomial algorithm pseudo-polynomial style goods seasonal products

来源：评论

学校读者我要写书评

暂无评论

Degree-constrained decompositions of graphs: Bounded treewidth and planarity

引用

THEORETICAL COMPUTER SCIENCE 2006年第3期355卷 389-395页

作者： Bazgan, C Tuza, Z Vanderpooten, D Univ Paris 09 LAMSADE F-75775 Paris 16 France Hungarian Acad Sci Inst Comp & Automat H-1111 Budapest Hungary Univ Veszprem Dept Comp Sci H-8201 Veszprem Hungary

We study the problem of decomposing the vertex set V of a graph into two nonempty parts V-1, V-2 which induce subgraphs where each vertex nu is an element of V-1 has degree at least a (nu) inside nu(1) and each nu is an element of V-2 has degree at least b(nu) inside V-2. We give a polynomial-time algorithm for graphs with bounded treewidth which decides if a graph admits a decomposition, and gives such a decomposition if it exists. This result and its variants are then applied to designing polynomial-time approximation schemes for planar graphs where a decomposition does not necessarily exist but the local degree conditions should be met for as many vertices as possible. (c) 2006 Elsevier B.V. All rights reserved.

关键词： graph decomposition treewidth planar graph polynomial algorithm PTAS

来源：评论

学校读者我要写书评

暂无评论

Complexity of large-update interior point algorithm for P_*(κ) linear complementarity problems

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 2007年第6期53卷 948-960页

作者： Cho, G. M. Kim, M. K. Lee, Y. H. Dongseo Univ Dept Multimedia Engn Pusan South Korea Pusan Natl Univ Dept Math Pusan South Korea

In this paper we propose a new large-update primal-dual interior point algorithm for P-*(K) linear complementarity problems (LCPs). We extend Bai et al.'s primal-dual interior point algorithm for linear optimization (LO) problems to P-*(K) LCPs with generalized kernel functions. New search directions and proximity functions are proposed based on a simple kernel function which is neither a logarithmic barrier nor a self-regular. We show that if a strictly feasible starting point is available, then the new large-update primal-dual interior point algorithms for solving P-* (kappa) LCPs have O ((1 + 2 kappa)n log n mu(0)/epsilon) polynomial complexity which is similar to the polynomial complexity obtained for LO and give a simple complexity analysis. This proximity function has not been used in the complexity analysis of interior point method (IPM) for P-* (K) LCPs before. (c) 2007 Elsevier Ltd. All rights reserved.

关键词： primal-dual interior point method kernel function complexity polynomial algorithm large-update linear complementarity problem

来源：评论

学校读者我要写书评

暂无评论

Open shop problem with zero-one time operations and integer release date deadline intervals

引用

DISCRETE APPLIED MATHEMATICS 1997年第1-3期76卷 213-223页

作者： Kubale, M Department of Foundations of Informatics Technical University of Gdańsk Narutowicza 11/12 80-952 Gdańsk Poland

We study the problem of constructing a minimum makespan schedule for the n-job m-machine open shop with zero-one time operations and integer release dates and deadlines. The general scheduling problem is shown to be NP-complete. Two polynomial-time algorithms are given for the following special cases: (1) all possible mn operations have unit execution time, and (2) at most m+n operations have unit execution time. Next, the second algorithm is generalized to bounded cyclicity graphs. All the algorithms are capable of minimizing not only makespan but maximum lateness and maximum tardiness as well.

关键词： bipartite graph deadline edge-coloring NP-completeness open-shop polynomial algorithm release date scheduling

来源：评论

学校读者我要写书评

暂无评论

Good acyclic orientations of 4-regular 4-connected graphs

引用

JOURNAL OF GRAPH THEORY 2022年第4期100卷 698-720页

作者： Bang-Jensen, Jorgen Kriesell, Matthias Univ Southern Denmark Dept Math & Comp Sci DK-5230 Odense Denmark Tech Univ Ilmenau Dept Math Ilmenau Germany

An st-ordering of a graph G=(V,E) is an ordering v(1),v(2), horizontal ellipsis ,v(n) of its vertex set such that s = v(1),t = v(n) and every vertex vi with i=2,3, horizontal ellipsis ,n-1 has both a lower numbered and a higher numbered neighbor. Such orderings have played an important role in algorithms for planarity testing. It is well-known that every 2-connected graph has an st-ordering for every choice of distinct vertices s,t. An st-ordering of a graph G corresponds directly to a so-called bipolar orientation of G, that is, an acyclic orientation D of G in which s is the unique source and t is the unique sink. Clearly every bipolar orientation of a graph has an out-branching rooted at the source vertex and an in-branching rooted at the sink vertex. In this paper, we study graphs which admit a bipolar orientation that contains an out-branching and in-branching which are arc-disjoint (such an orientation is called good). A 2T-graph is a graph whose edge set can be decomposed into two edge-disjoint spanning trees. Clearly a graph has a good orientation if and only if it contains a spanning 2T-graph with a good orientation, implying that 2T-graphs play a central role. It is a well-known result due to Tutte and Nash-Williams, respectively, that every 4-edge-connected graph contains a spanning 2T-graph. Vertex-minimal 2T-graphs with at least two vertices, also known as generic circuits, play an important role in rigidity theory for graphs. Recently with Bessy and Huang we proved that every generic circuit has a good orientation. In fact, we may specify the roots of the two branchings arbitrarily as long as they are distinct. Using this, several results on good orientations of 2T-graphs were obtained. It is an open problem whether there exists a polynomial algorithm for deciding whether a given 2T-graph has a good orientation. Complex constructions of 2T-graphs with no good orientation were given in work by Bang-Jensen, Bessy, Huang and Kriesell (2021) indicating tha

关键词： 2T-graph 4-regular graph acyclic orientations edge-disjoint spanning trees generic circuit in-branching out-branching polynomial algorithm st-ordering

来源：评论

学校读者我要写书评

暂无评论

DAG-Width and Circumference of Digraphs

引用

JOURNAL OF GRAPH THEORY 2016年第2期82卷 194-206页

作者： Bang-Jensen, Jorgen Larsen, Tilde My Univ Southern Denmark Dept Math & Comp Sci Odense Denmark

We prove that every digraph of circumference l has DAG-width at most l. This is best possible and solves a recent conjecture from S. Kintali (ArXiv:1401.2662v1 [***], January 2014).(1) As a consequence of this result we deduce that the k-linkage problem is polynomially solvable for every fixed k in the class of digraphs with bounded circumference. This answers a question posed in J. Bang-Jensen, F. Havet, and A. K. Maia (Theor Comput Sci 562 (2014), 283-303). We also prove that the weak k-linkage problem (where we ask for arc-disjoint paths) is polynomially solvable for every fixed k in the class of digraphs with circumference 2 as well as for digraphs with a bounded number of disjoint cycles each of length at least 3. The case of bounded circumference digraphs is still open. Finally, we prove that the minimum spanning strong subdigraph problem is NP-hard on digraphs of DAG-width at most 5.

关键词： DAG-width k-linkage problem bounded cycle length polynomial algorithm cops-and-robbers game

来源：评论

学校读者我要写书评

暂无评论

Quasi-hamiltonian paths in semicomplete multipartite digraphs

引用

DISCRETE APPLIED MATHEMATICS 2013年第7-8期161卷 889-898页

作者： Bang-Jensen, Jorgen Maddaloni, Alessandro Simonsen, Sven Univ Southern Denmark Dept Math & Comp Sci DK-5230 Odense Denmark

A quasi-hamiltonian path in a semicomplete multipartite digraph D is a path which visits each maximal independent set (also called a partite set) of D at least once. This is a generalization of a hamiltonian path in a tournament. In this paper we investigate the complexity of finding a quasi-hamiltonian path, in a given semicomplete multipartite digraph, from a prescribed vertex x to a prescribed vertex y as well as the complexity of finding a quasi-hamiltonian path whose end vertices belong to a given set of two vertices {x, y}. While both of these problems are polynomially solvable for semicomplete digraphs (here all maximal independent sets have size one), we prove that the first problem is NP-complete and describe a polynomial algorithm for the latter problem. (C) 2012 Elsevier B.V. All rights reserved.

关键词： polynomial algorithm NP-complete Semicomplete multipartite digraph Extended semicomplete digraph Multipartite tournament Quasi-hamiltonian path

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：