共查询到20条相似文献,搜索用时 15 毫秒
1.
LetP={v
1,...,v
n
} be a set ofn jobs to be executed on a set ofm identical machines. In many instances of scheduling problems, if a jobv
i
has to be executed before the jobv
j
and both jobs are to be executed on different machines, some sort of information exchange has to take place between the machines executing them. The time it takes for this exchange of information is called a communication delay.In this paper we give anO(n) algorithm to find an optimal scheduling with communication delays when the number of machines is not limited and the precedence constraints on the jobs form a tree. 相似文献
2.
Natalia V. Shakhlevich 《Discrete Applied Mathematics》2006,154(15):2178-2199
This paper considers single machine scheduling problems in which the job processing times and/or their release dates are controllable. Possible changes to the controllable parameters are either individual or done by controlling the relevant processing or release rate. The objective is to minimize the sum of the makespan plus the cost for changing the parameters. For the problems of this type, we provide a number of polynomial-time algorithms and give a fairly complete complexity classification. 相似文献
3.
In this paper, consistent algebraic L-domains are considered. One algebraic and two topological characterization theorems
for their directed completions are given. It is proved that eliminating a set of maximal elements with empty interior from
an algebraic L-domain results a consistent algebraic L-domain whose directed completion is just the given algebraic L-domain
up to isomorphism. It is also proved that the category CALDOM of consistent algebraic L-domains and Scott continuous maps is Cartesian closed and has the category ALDOM of algebraic L-domains and Scott continuous maps as a full reflective subcategory.
Received January 8, 2005; accepted in final form June 15, 2005. 相似文献
4.
In this paper, we present new interval oscillation criteria related to integral averaging technique for second order partial differential equations with delays that are different from most known ones in the sense that they are based on the information only on a sequence of subintervals of [t0,∞), rather than on whole half-line. Our results are sharper than some previous results and handles the cases which are not covered by known criteria. 相似文献
5.
A BLACK-SCHOLES FORMULA FOR OPTION PRICING WITH DIVIDENDS 总被引:2,自引:0,他引:2
XuWENSHENG WUZHEN 《高校应用数学学报(英文版)》1996,11(2):159-164
Abstract. We obtain a Black-Scholes formula for the arbitrage-free pricing of Eu-ropean Call options with constant coefficients when the underlylng stock generatesdividends. To hedge the Call option, we will always borrow money from bank. We seethe influence of the dividend term on the option pricing via the comparison theoremof BSDE(backward stochastic di~erential equation [5], [7]). We also consider the option pricing problem in terms of the borrowing rate R whichis not equal to the interest rate r. The corresponding Black-Sdxoles formula is given.We notice that it is in fact the borrowing rate that plays the role in the pricing formula. 相似文献
6.
Luoshan Xu 《Topology and its Applications》2006,153(11):1886-1894
In this paper, posets which may not be dcpos are considered. The concept of embedded bases for posets is introduced. Characterizations of continuity of posets in terms of embedded bases and Scott topology are given. The main results are:
- (1)
- A poset is continuous iff it is an embedded basis for a dcpo up to an isomorphism;
- (2)
- A poset is continuous iff its Scott topology is completely distributive;
- (3)
- A topological T0 space is a continuous poset equipped with the Scott topology in the specialization order iff its topology is completely distributive and coarser than or equal to the Scott topology;
- (4)
- A topological T1 space is a discrete space iff its topology is completely distributive.
7.
A. Sedeño-Noda D. Alcaide López de PabloC. González-Martín 《European Journal of Operational Research》2009
This paper deals with several bicriteria open-shop scheduling problems where jobs are pre-emptable and their corresponding time-windows must be strictly respected. The criteria are a performance cost and the makespan. Network flow approaches are used in a lexmin procedure with a bounded makespan and the considered bicriteria problems are solved. Finally, the computational complexity of the algorithm and a numerical example are reported. 相似文献
8.
J. D. Farley 《Algebra Universalis》1996,36(1):8-45
It is shown that Aut(L
Q
) is naturally isomorphic to Aut(L) × Aut(Q) whenL is a directly and exponentially indecomposable lattice,Q a non-empty connected poset, and one of the following holds:Q is arbitrary butL is ajm-lattice,Q is finitely factorable and L is complete with a join-dense subset of completely join-irreducible elements, orL is arbitrary butQ is finite. A problem of Jónsson and McKenzie is thereby solved. Sharp conditions are found guaranteeing the injectivity of the natural mapv
P,Q
from Aut(P) × Aut(Q) to Aut(P
Q
)P andQ posets), correcting misstatements made by previous authors. It is proven that, for a bounded posetP and arbitraryQ, the Dedekind-MacNeille completion ofP
Q
,DM(P
Q
), is isomorphic toDM(P)Q. This isomorphism is used to prove that the natural mapv
P,Q
is an isomorphism ifv
DM(P),Q is, reducing a poset problem to a more tractable lattice problem.Presented by B. Jonsson.The author would like to thank his supervisor, Dr. H. A. Priestley, for her direction and advice as well as his undergraduate supervisor, Prof. Garrett Birkhoff, and Dr. P. M. Neumann for comments regarding the paper. This material is based upon work supported under a (U.S.) National Science Foundation Graduate Research Fellowship and a Marshall Aid Commemoration Commission Scholarship. 相似文献
9.
An algorithm is presented to draw Hasse-diagrams of partially ordered sets (orders). It uses two heuristic principles to generate good pictures for a wide range of orders. These two principles are (i) The total length of all edges of the diagram should be small (with the vertices kept at a minimal distance) and (ii) the vertices are constrained to coincide with the grid points of a given rectangular planar grid. The benefits are quite straightforward sine (i) using less ink means less confusion and (ii) the restriction to grid points tends to keep the number of different slopes small. Since the program was conceived as a readily usable tool (with the emphasis on results rather than on perfection), we are well aware of the fact that it will lend itself easily to improvements in many aspects. 相似文献
10.
Alexander V. Rezounenko 《Nonlinear Analysis: Theory, Methods & Applications》2010,73(6):1707-516
We investigate a class of non-linear partial differential equations with discrete state-dependent delays. The existence and uniqueness of strong solutions for initial functions from a Banach space are proved. To get the well-posed initial value problem we restrict our study to a smaller metric space, construct the dynamical system and prove the existence of a compact global attractor. 相似文献
11.
This paper deals with the existence of travelling wave fronts in reaction-diffusion systems with spatio-temporal delays. Our approach is to use monotone iterations and a nonstandard ordering for the set of profiles of the corresponding wave system. New iterative techniques are established for a class of integral operators when the reaction term satisfies different monotonicity conditions. Following this, the existence of travelling wave fronts for reaction-diffusion systems with spatio-temporal delays is established. Finally, we apply the main results to a single-species diffusive model with spatio-temporal delay and obtain some existence criteria of travelling wave fronts by choosing different kernels. 相似文献
12.
A new homomorphism between two partially ordered sets (the III-homomorphism) and a new congruence on a poset (the III-congruence) are introduced. Some properties of these homomorphisms and congruences and their relationship to the other known homomorphisms and congruences on posets are investigated. In contrast to total algebras, there are many different ways to introduce these notions. It is usually required that the respective notions should coincide with the usual definitions whenever lattices or semilattices are treated. The present paper presents an approach which in some sense completes the hierarchy of definitions so far used. 相似文献
13.
Roberto Montemanni 《Journal of Mathematical Modelling and Algorithms》2007,6(2):287-296
We consider a version of the total flow time single machine scheduling problem where uncertainty about processing times is
taken into account. Namely an interval of equally possible processing times is considered for each job, and optimization is
carried out according to a robustness criterion. We propose the first mixed integer linear programming formulation for the
resulting optimization problem and we explain how some known preprocessing rules can be translated into valid inequalities
for this formulation. Computational results are finally presented.
Work funded by the Swiss National Science Foundation through project 200020-109854/1. 相似文献
14.
In this note, the new concepts of C-bases (resp., BC-bases, L-bases) which are special kinds of abstract bases are introduced. It is proved that the round ideal completion of a C-basis (resp., BC-basis, L-basis) is a continuous lattice (resp., bc-domain, L-domain). Furthermore, representation theorems of continuous lattices (resp., bc-domains, L-domains) by means of the round ideal completions of C-bases (resp., BC-bases, L-bases) are obtained. Supported by the NSF of China (10371106, 60774073) and by the Fund (S0667-082) from Nanjing University of Aeronautics and Astronautics. 相似文献
15.
Matt Szczesny 《Journal of Pure and Applied Algebra》2011,215(4):303-309
Given a family F of posets closed under disjoint unions and the operation of taking convex subposets, we construct a category CF called the incidence category ofF. This category is “nearly abelian” in the sense that all morphisms have kernels/cokernels, and possesses a symmetric monoidal structure akin to direct sum. The Ringel-Hall algebra of CF is isomorphic to the incidence Hopf algebra of the collection P(F) of order ideals of posets in F. This construction generalizes the categories introduced by K. Kremnizer and the author, in the case when F is the collection of posets coming from rooted forests or Feynman graphs. 相似文献
16.
On the ascending star subgraph decomposition of star forests 总被引:3,自引:0,他引:3
LetG be a graph of size
for some integern2. ThenG is said to have an ascending star subgraph decomposition ifG can be decomposed inton subgraphsG
1,G
2, ...,G
n such that eachG
i is a star of sizei with 1in. We shall prove in this paper that a star forest with size
, possesses an ascending star subgraph decomposition if the size of each component is at leastn, which is stronger than the conjecture proposed by Y. Alavi, A. J. Boals, G. Chartrand, P. Erds and O. R. Oellermann. 相似文献
17.
A topology on a set X is self complementary if there is a homeomorphic copy on the same set that is a complement in the lattice of topologies on X. The problem of characterizing finite self complementary topologies leads us to redefine the problem in terms of preorders (i.e. reflexive, transitive relations). A preorder P on a set X is self complementary if there is an isomorphic copy P of P on X that is arc disjoint to P (except for loops) and with the property that PP is strongly connected. We characterize here self complementary finite partial orders and self complementary finite equivalence relations. 相似文献
18.
In 1986 Tardos proved that for the poset 1+2+2+2+1, the clone of monotone operations is nonfinitely generated. We generalize his result in the class of series parallel posets. We characterize the posets with nonfinitely generated clones in this class by the property that they have a retract of the form either 1+2+2+2+1, 2+2+1, or 1+2+2.Research partially supported by Hungarian National Foundation for Research under grant no. 1903. 相似文献
19.
YANGXIAOGUANG 《高校应用数学学报(英文版)》1998,13(3):341-346
In this note, the author proves that the inverse problem of submodular function on digraphs with l∞ objective function can be solved by strongly polynomial algorithm. The result shows that most inverse network optimization problems with l∞ objective function can be solved in the polynomial time. 相似文献
20.
We define geometric semilattices, a generalization of geometric lattices. The poset of independent sets of a matroid is another example. We prove several axiomatic and constructive characterizations, for example: geometric semilattices are those semilattices obtained by removing a principal filter from a geometric lattice. We also show that all geometric semilattices are shellable, unifying and extending several previous results.Partially supported by NSF grant MCS 81-03474. 相似文献