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

polynomial algorithms for a two-class multiprocessor scheduling problem in mobile telecommunications systems

JOURNAL OF SCHEDULING 2005年第3期8卷 255-273页

作者： Detti, P Agnetis, A Ciaschetti, G Univ Siena Dipartimento Ingn Informaz I-53100 Siena Italy

In Universal Mobile Telecommunications Systems radio access, information packets of different services and users are sent across the air interface organized into radio frames. A radio frame is divided into a fixed number of time slots, different packets can share the same time slot and exactly one slot must be assigned to each packet. The packets of different services have divisible sizes and the slot capacity is limited. Quality of Service requirements set time intervals within which each packet must be scheduled. In this work, we address the problem of scheduling packets related to two different services to the time slots of a radio frame. The problem is a variant of the High-Multiplicity Multiprocessor Scheduling Problem in which there are two classes of jobs with divisible sizes, and the jobs must satisfy assignment restrictions. Two polynomial-time scheduling algorithms, maximizing the number of scheduled packets, and the weighted throughput, are provided.

关键词： multiprocessor scheduling polynomial algorithms high-multiplicity

来源：评论

学校读者我要写书评

暂无评论

polynomial algorithms for single machine scheduling problems with financial constraints

引用

OPERATIONS RESEARCH LETTERS 1997年第1期21卷 39-42页

作者： Xie, JX Tsing Hua Univ Dept Appl Math Beijing 100084 Peoples R China

This paper deals with the single machine scheduling problem with multiple financial resource constraints. It is shown that the problem can be reduced to the two machine flow shop scheduling problem if the financial resources arrive uniformly over time, and it is also shown that the LPT (Largest Processing Time) rule generates an optimal solution to the problem if the financial resources are consumed uniformly by all the jobs. Hence there exist polynomial algorithms for these two special cases of the problem. (C) 1997 Elsevier Science B.V.

关键词： single machine scheduling financial constraints polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

polynomial algorithms FOR A CLASS OF DISCRETE MINMAX LINEAR-PROGRAMMING PROBLEMS

引用

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY 1995年第4期46卷 499-506页

作者： PUNNEN, AP NAIR, KPK UNIV NEW BRUNSWICK FAC ADMFREDERICTONNB E3B 5A3CANADA

We consider the problem of obtaining integer solutions to a minmax linear programming problem. Although this general problem is NP-complete, it is shown that a restricted version of this problem can be solved in polynomial time. For this restricted class of problems two polynomial time algorithms are suggested, one of which is strongly polynomial whenever its continuous analogue and an associated linear programming problem can be solved by a strongly polynomial algorithm. Our algorithms can also be used to obtain integer solutions for the minmax transportation problem with an inequality budget constraint. The equality constrained version of this problem is shown to be NP-complete. We also provide some new insights into the solution procedures for the continuous minmax linear programming problem.

关键词： INTEGER PROGRAMMING MINIMAX PROBLEMS polynomial algorithms TRANSPORTATION PROBLEM

来源：评论

学校读者我要写书评

暂无评论

polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion

引用

DISCRETE APPLIED MATHEMATICS 2002年第1-3期120卷 13-23页

作者： Bauer, D Broersma, HJ Morgana, A Schmeichel, E Univ Twente Fac Math Sci NL-7500 AE Enschede Netherlands Stevens Inst Technol Dept Math Sci Hoboken NJ 07030 USA Univ Roma La Sapienza Dipartimento Matemat G Castelnuovo I-00185 Rome Italy San Jose State Univ Dept Math & Comp Sci San Jose CA 95192 USA

A number of results in hamiltonian graph theory are of the form "P-1 implies P-2", where P-1 is a property of graphs that is NP-hard and P-2 is a cycle structure property of graphs that is also NP-hard. An example of such a theorem is the well-known Chvatal-Erdos Theorem, which states that every graph G with alpha less than or equal to kappa is hantiltonian. Here kappa is the vertex connectivity of G and alpha is the cardinality of a largest set of independent vertices of G. In another paper Chvatal points out that the proof of this result is in fact a polynomial time construction that either produces a Hamilton cycle or a set of more than kappa independent vertices. In this note we point out that other theorems in hamiltonian graph theory have a similar character. In particular, we present a constructive proof of a well-known theorem of Jung (Ann. Discrete Math. 3 (1978) 129) for graphs on 16 or more vertices. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： hamiltonian graphs toughness complexity NP-hardness polynomial algorithms constructive proofs

来源：评论

学校读者我要写书评

暂无评论

polynomial algorithms FOR A CLASS OF LINEAR-PROGRAMS

引用

MATHEMATICAL PROGRAMMING 1981年第2期21卷 121-136页

作者： MAURRAS, JF TRUEMPER, K AKGUL, M UNIV TEXAS DALLASTX 75230 UNIV WATERLOO WATERLOO N2L 3G1ONTARIOCANADA

This paper describes several algorithms for solution of linear programs. The algorithms are polynomial when the problem data satisfy certain conditions.

关键词： Linear Programming polynomial algorithms Total Unimodularity

来源：评论

学校读者我要写书评

暂无评论

polynomial algorithms for guillotine cutting of a rectangle into small rectangles of two kinds

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2008年第1期185卷 105-121页

作者： Arslanov, M. Z. Ashigaliev, D. U. Ismail, E. E. Suleiman Demirel Univ Inst Problems Informat & Control Alma Ata 050010 Kazakhstan

In this paper the problem of optimally guillotine cutting a rectangle (A, B) into small rectangles of two kinds is considered. Rectangles of the first kind (c,a(i)), i is an element of I have the same width, and their heights can be various. Rectangles of the second kind (b(j),d), j is an element of J have the same height, and their widths can be various. The number of occurrences of each small rectangle in a cutting pattern is not restricted. Similar problems often appear in the furniture industry. This cutting problem is reduced to the shortest path problem in a special rectangular grid, for which a linear time algorithm is suggested. This approach generalizes the approach of [E. Girlich, A.G. Tarnowski, On polynomial solvability of two multiprocessor scheduling problems, Mathematical Methods of Operations Research 50 (1999) 27-51;A.G. Tarnowski, Advanced polynomial time algorithm for guillotine generalized pallet loading problem, in: The International Scientific Collection: Decision Making Under Conditions of Uncertainty (Cutting-Packing Problems), Ufa State Aviation Technical University, 1997, pp. 93-124] and allows us to construct polynomial algorithms for the guillotine cutting problem considered with a fixed number of small rectangles of two kinds. (c) 2007 Elsevier B.V. All rights reserved.

关键词： cutting shortest path problem polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

polynomial algorithms for solving the quadratic assignment problem on networks

引用

COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS 2010年第11期50卷 1948-1955页

作者： Zabudskii, G. G. Lagzdin, A. Yu. Russian Acad Sci Omsk Branch Sobolev Inst Math Siberian Branch Omsk 644099 Russia

polynomial algorithms for solving the quadratic assignment problem on special types of networks are proposed. The structure of the links between the objects to be located is represented by a graph.

关键词： quadratic assignment problem facility location problem polynomial algorithms graphs networks

来源：评论

学校读者我要写书评

暂无评论

polynomial algorithms FOR ITEM MATCHING

引用

APPLIED PSYCHOLOGICAL MEASUREMENT 1992年第4期16卷 365-371页

作者： ARMSTRONG, RD JONES, DH RUTGERS UNIV GRAD SCH MANAGEMENTNEWARKNJ 07102 USA

To estimate test reliability and to create parallel tests, test items frequently are matched. Items can be matched by splitting tests into parallel test halves, by creating T splits, or by matching a desired test form. Problems often occur. algorithms are presented to solve these problems. The algorithms are based on optimization theory in networks (graphs) and have polynomial complexity. Computational results from solving sample problems with several hundred decision variables are reported.

关键词： BRANCH-AND-BOUND ALGORITHM CLASSICAL TEST THEORY COMPLEXITY ITEM MATCHING NONDETERMINISTIC polynomial COMPLETE PARALLEL TESTS polynomial algorithms TEST CONSTRUCTION

来源：评论

学校读者我要写书评

暂无评论

polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract)

Polynomial algorithms for partitioning problems on graphs wi...

引用

2001 Operating Section Proceedings, American Gas Association

作者： Kobler, Daniel Rotics, Udi Fields Institute for Research in Mathematical Sciences 222 College Street Toronto ON M5T 3J1 Canada Department of Computer Science University of Toronto Toronto ON M5S 3J4 Canada

ISBN: (纸本)0898714907

We consider three graph partitioning problems, both from the vertices and the edges point of view. These problems are dominating set, list-q-coloring with costs (fixed number of colors q) and coloring with non-fixed number of colors. They are all known to be NP-hard in general. We show that all these problems (except edge-coloring) can be solved in polynomial time on graphs with cligue-width bounded by some constant k, if the k-expression of the input graph is also given. In particular, we present the first polynomial algorithms (on these classes) for chromatic number, edge-dominating set and list-q-coloring with costs (fixed number of colors q, both vertex and edge versions). Since these classes of graphs include classes like P4-sparse graphs, distance hereditary graphs and graphs with bounded treewidth, our algorithms also apply to these graphs. Copyright © 2009 ACM, Inc.

关键词： Clique-width Coloring Dominating set Edge-coloring Edge-dominating set polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

Common Due-Window Problem: polynomial algorithms for a Given Processing Sequence

Common Due-Window Problem: Polynomial Algorithms for a Given...

引用

2014 IEEE Symposium on Computational Intelligence in Production and Logistics Systems (CIPLS)

作者： Awasthi, Abhishek Laessig, Joerg Kramer, Oliver Weise, Thomas Univ Appl Sci Dept Comp Sci Gorlitz Germany Carl von Ossietzky Univ Oldenburg Dept Comp Sci Oldenburg Germany Univ Sci & Technol China Sch Comp Sci & Technol Hefei Anhui Peoples R China

ISBN: (纸本)9781479945009

The paper considers the Common Due-Window (CDW) problem where a single machine processes a certain number of jobs against a common due-window. Each job possesses different processing times but different and asymmetric earliness and tardiness penalties. The objective of the problem is to find the processing sequence of jobs, their completion times and the position of the given due-window to minimize the total penalty incurred due to tardiness and earliness of the jobs. This work presents exact polynomial algorithms for optimizing a given job sequence for a single machine with the run-time complexity of O(n(2)), where n is the number of jobs. We also provide an O (n) algorithm for optimizing the CDW with unit processing times. The algorithms take a sequence consisting of all the jobs (J(i,i) = 1, 2, ..., n) as input and return the optimal completion times, which offers the minimum possible total penalty for the sequence. Furthermore, we implement our polynomial algorithms in conjunction with Simulated Annealing (SA) to obtain the best processing sequence. We compare our results with that of Biskup and Feldmann [1] for different due-window lengths.

关键词： computational complexity minimisation simulated annealing single machine scheduling CDW optimization CDW problem O(n) algorithm O(n2) run-time complexity SA common due-window problem different-asymmetric earliness penalties different-asymmetric tardiness penalties due-window lengths job processing sequence job processing times optimal completion times polynomial algorithms single machine process total penalty minimization unit processing times Educational institutions Job shop scheduling Optimal scheduling polynomials Schedules Silicon simulated annealing polynomial processing time single machine scheduling Optimal scheduling Job shop scheduling complexity classes Educational institutions jobs job sequence Silicon Tardiness algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：