On-Line Scheduling with Rejection on Identical Parallel Machines

In this paper, we consider the on-line scheduling of unit time jobs with rejection on rn identical parallel machines. The objective is to minimize the total completion time of the accepted jobs plus the total penalty of the rejected jobs. We give an on-line algorithm for the problem with competitive ratio 1/2 （2 ＋√3） ≈ 1.86602.     

Scheduling with Rejection and Non-Identical Job Arrivals

In this paper, we address the scheduling problem with rejection and non-identical job arrivals, in which we may choose not to process certain jobs and each rejected job incurs a penalty, Our goal is to minimize the sum of the total penalties of the rejected jobs and the maximum completion time of the processed ones, For the off-line variant, we prove its NP-hardness and present a PTAS, and for the on-line special case with two job arrivals, we design a best possible algorithm with competitive ratio （√5＋1/2） .     

An on-line scheduling problem of parallel machines with common maintenance time

In this paper, the authors consider an on-line scheduling problem of m (m ≥ 3) identical machines with common maintenance time interval and nonresumable availability. For the case that the length of maintenance time interval is larger than the largest processing time of jobs, the authors prove that any on-line algorithm has not a constant competitive ratio. For the case that the length of maintenance time interval is less than or equal to the largest processing time of jobs, the authors prove a lower bound of 3 on the competitive ratio. The authors give an on-line algorithm with competitive ratio $4 - \tfrac{1} {m} $ . In particular, for the case of m = 3, the authors prove the competitive ratio of the on-line algorithm is $\tfrac{{10}} {3} $ .     

On the Laplacian spectral radii of trees with nearly perfect matchings

Let be the set of trees on 2k+1 vertices with nearly perfect matchings, and let be the set of trees on 2k + 2 vertices with perfect matchings. The largest Laplacian spectral radii of trees in and and the corresponding trees were given by Guo (2003). In this paper, the authors determine the second to the sixth largest Laplacian spectral radii among all trees in and give the corresponding trees. This research is supported by the National Natural Science Foundation of China under Grant No. 10331020.     

On-Line Scheduling on Parallel Machines to Minimize the Makespan

This paper considers two parallel machine scheduling problems,where the objectives of both problems are to minimize the makespan,and the jobs arrive over time,on two uniform machines with speeds 1 and s(s≥1),and on m identical machines,respectively.For the first problem,the authors show that the on-line LPT algorithm has a competitive ratio of(1 +5~(1/2))/2≈1.6180 and the bound is tight.Furthermore,the authors prove that the on-line LPT algorithm has the best possible competitive ratio if s≥1.8020.For the second problem,the authors present a lower bound of(15-(17)~(1/2))/8≈1.3596 on the competitive ratio of any deterministic on-line algorithm.This improves a previous result of 1.3473.     

Two-Weight Norm Inequality for Imaginary Powers of a Laplace Operator

We study two-weight norm inequality for imaginary powers of a Laplace operator in R^n, n ≥ 1, especially from weighted Lebesgue space Lv^p（R^n） to weighted Lebesgue space Lμ^p（R^n）, where 1 〈 p 〈 ∞. We prove that the two-weighted norm inequality holds whenever for some t 〉 1, （μ^t, v^t） ∈ Ap, or if （μ, v） ∈Ap, where μ and v^-1/（p-1） satisfy the growth condition and reverse doubling property.     

On the Meromorphic Solutions of Linear Differential Equations

In this paper, we investigate the growth of meromorphic solutions of higher order linear differential equation f^（k） ＋Ak-1 （z）e^Pk-1^（z） f^（k-1） ＋…＋A1 （z）e^P1（z） f′ ＋Ao（z）e^Po（z） f = 0 （k ≤ 2）, where Pj（z） （j = 0, 1,..., k - 1） are nonconstant polynomials such that deg Pj = n （j = 0, 1,..., k - 1） and Aj（z）（≠ 0） （j = 0, 1,..., k - 1） are meromorphic functions with order p（Aj） 〈 n （j = 0, 1,..., k - 1）.     

Improved Algorithm for Minimum Data Aggregation Time Problem in Wireless Sensor Networks

Wireless sensor networks promise a new paradigm for gathering data via collaboration among sensors spreading over a large geometrical region. Many applications impose delay requirements for data gathering and ask for time-efficient schedules for aggregating sensed data and sending to the data sink. In this paper, the authors study the minimum data aggregation time problem under collision-free transmission model. In each time round, data sent by a sensor reaches all sensors within its transmission range, but a sensor can receive data only when it is the only data that reaches the sensor. The goal is to find the method that schedules data transmission and aggregation at sensors so that the time for all requested data to be sent to the data sink is minimal. The authors propose a 7△/log2｜s｜＋c, new approximation algorithm for this NP-hard problem with guaranteed performance ratio which significantly reduces the current best ratio of △- 1, where S is the set of sensors containing source data, A is the maximal number of sensors within the transmission range of any sensor, and e is a constant. The authors also conduct extensive simulation, the obtained results justify the improvement of proposed algorithm over the existing one.     

Determining Whether a Multivariate Hyperexponential Function is Algebraic

Let F=C（x1,x2,…,xe,xe＋1,…,xm）, where x1, x2,… , xe are differential variables, and xe＋1,…,xm are shift variables. We show that a hyperexponential function, which is algebraic over F,is of form g（x1, x2, …,xm）q（x1,x2,…,xe）^1/lwe＋1^xe＋1…wm^xm, where g∈ F, q ∈ C（x1,x2,…,xe）,t∈Z^＋ and we＋1,…,wm are roots of unity. Furthermore,we present an algorithm for determining whether a hyperexponential function is algebraic over F.     

Scheduling problems with rejection to minimize the maximum flow time

This paper considers the scheduling problem with rejection on m identical parallel machines to minimize the maximum flow time. The authors show that this problem is NP-hard even when there is a single machine and all jobs have two distinct release dates. Furthermore, the authors present a dynamic programming algorithm and two approximation algorithms to solve them.     

Semi On-Line Scheduling Problem for Maximizing the Minimum Machine Completion Time on Two Uniform Machines

Ia this paper, we consider a semi on-line version on two uniform machines Mi, i = 1, 2, where the processing time of the largest job is known in advance. A speed si（s1 = 1, 1 ≤s2 = s） is associated with machine Mi. Our goal is to maximize the Cmin. We give a Cmin 2 algorithm and prove its competitive ratio is at most 2s＋1/s＋1 We also claim the Cmin 2 algorithm is tight and the gap between the competitive ratio of Cmin2 algorithm and the optimal value is not greater than 0.555. It is obvious that our result coincides with that given by He for s =1.     

On the single server retrial queue with priority subscribers and server breakdowns

The author concerned the reliability evaluation as well as queueing analysis of M1, M2/G1, G2/1 retrial queues with two different types of primary customers arriving according to independent Poisson flows. In the case of blocking, the first type of customers can be queued whereas the second type of customers must leave the service area but return after some random period of time to try their luck again. The author assumes that the server is unreliable and it has a service-type dependent, exponentially distributed life time as well as a service-type dependent, generally distributed repair time. The necessary and sufficient condition for the system to be stable is investigated. Using a supplementary variable method, the author obtains a steady-state solution for queueing measures, and the transient as well as the steady-state solutions for reliability measures of interest.     

A general iterative method of fixed points for equilibrium problems and optimization problems

The purpose of this paper is to present a general iterative scheme as below:

Control and Stabilization of the Rosenau Equation Posed on a Periodic Domain

This paper considers the Rosenau equation with a moving control?t u + ?_t?_x~4 u + ?_xu + u?x u = a(x + ct)h(x, t), c = 0, x ∈ T = R/(2πZ), t 0.The authors prove that the Rosenau equation with a moving control is locally exact controllable in Hs(T) with s ≥ 0 and globally exponential stable in H~s(T) with s ≥ 2. The two results nontrivially extend the work of(Rosier L and Zhang B Y, 2013) from the BBM equation to the Rosenau equation.     

Some Results on Generalized Difference Sets

Sequences with ideal correlation functions have important applications in communications such as CDMA, FDMA, etc. It has been shown that difference sets can be used to construct such sequences. The author extends Pott and Bradley＇s method to a much broader case by proposing the concept of generalized difference sets. Some necessary conditions for the existence of generalized difference sets are established by means of some Diophantine equations. The author also provides an algorithm to determine the existence of generalized difference sets in the cyclic group Zv. Some examples are presented to illustrate that our method works.     

Forced Oscillations of a Class of Nonlinear Dispersive Wave Equations and their Stability

It has been observed in laboratory experiments that when nonlinear dispersive waves are forced periodically from one end of undisturbed stretch of the medium of propagation, the signal eventually becomes temporally periodic at each spatial point. The observation has been confirmed mathematically in the context of the damped Korteweg-de Vries （KdV） equation and the damped Benjamin-Bona-Mahony （BBM） equation. In this paper we intend to show the same results hold for the pure KdV equation （without the damping terms） posed on a finite domain. Consideration is given to the initial-boundary-value problem {ut＋ux＋uux＋uxxx=0, u（x,0）=φ（x）, 0〈x〈1, t〉0,u（0,t）=h（t）, u（1,t） = 0, ux（1,t） = 0, t〉0.It is shown that if the boundary forcing h is periodic with small ampitude, then the small amplitude solution u of （＊） becomes eventually time-periodic. Viewing （＊） （without the initial condition） as an infinite-dimensional dynamical system in the Hilbert space L^2（0, 1）, we also demonstrate that for a given periodic boundary forcing with small amplitude, the system （＊） admits a （locally） unique limit cycle, or forced oscillation, which is locally exponentially stable. A list of open problems are included for the interested readers to conduct further investigations.     

ON THE ALMOST SURELY ASYMPTOTIC BOUNDS OF A CLASS OF ORNSTEIN-UHLENBECK PROCESSES IN INFINITE DIMENSIONS*

Given a real-valued separable M-type 2 Banach space X with the p-th power of the norm of C2-class, the almost sure asymptotic upper bounds of the solutions of the Ornstein-Uhlenbeck Processes described by the following equations {dz（t）=A（t,z（t））dt＋σ（t,z（t））dW（t）,z（0）=z0∈X,are investigated. This study generalizes the corresponding well-known finite dimensional results of Lapeyre （1989） and Mao （1992）.     

ON （∈, ∈ ∨q）-FUZZY FILTERS OF BL-ALGEBRAS

The authors introduce the notions of （∈, ∈ ∨q）-fuzzy Boolean （implicative, positive implicative, and fantastic） filters in BL-algebras, present some characterizations on these generalized fuzzy filters, and describe the relations among these generalized fuzzy filters. It is proved that an （∈, ∈ ∨q）fuzzy filter in a BL-algebra is Boolean （implicative） if and only if it is both positive implicative and fantastic.     

Variational discretization for parabolic optimal control problems with control constraints

This paper studies variational discretization for the optimal control problem governed by parabolic equations with control constraints.First of all,the authors derive a priori error estimates where |||u-U₍h|||_L∞（J;L²（Ω））=O（h²+k）.It is much better than a priori error estimates of standard finite element and backward Euler method where |||μ-U_h|||₍L∞（J;L²（Ω））=O（h+ k）.Secondly,the authors obtain a posteriori error estimates of residual type.Finally,the authors present some numerical algorithms for the optimal control problem and do some numerical experiments to illustrate their theoretical results.     

On LCD Negacyclic Codes over Finite Fields

This paper deduces the structure of LCD negacyclic codes over the finite field Fq, where q is an odd prime power. Based on the study of q-cyclotomic cosets modulo 2 n, the authors obtain the parameters of LCD negacyclic codes of lengths n =(q+1)/2,(q~m-1)/2(q-1)and q~(t·2~τ)-1/2(q~t +1), respectively. And many optimal codes are given. Moreover, the authors research two special classes of MDS LCD negacyclic codes of length n |(q-1)/2 and n |(q+1)2, respectively.