Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness

Consider a single machine and a set of n jobs that are available for processing at time 0. Job j has a processing time p_j, a due date d_j and a weight w_j. We consider bi-criteria scheduling problems involving the maximum weighted tardiness and the number of tardy jobs. We give NP-hardness proofs for the scheduling problems when either one of the two criteria is the primary criterion and the other one is the secondary criterion. These results answer two open questions posed by Lee and Vairaktarakis in 1993. We consider complexity relationships between the various problems, give polynomial-time algorithms for some special cases, and propose fast heuristics for the general case. The effectiveness of the heuristics is measured by empirical study. Our results show that one heuristic performs extremely well compared to optimal solutions.     

A limit theorem for expectations conditional on a sum

Let ξ₁, ξ₂, ξ₃,... be a sequence of independent random variables, such that μ _j ?E[ξ _j ], 0<α?Var[ξ _j ] andE[|ξ _j ?μ _j |^2+δ] for some δ, 0<δ?1, and everyj?1. IfU and ξ₀ are two random variables such thatE[ξ ₀ ² ]<∞ andE[|U|ξ ₀ ² ]<∞, and the vector 〈U,ξ〉 is independent of the sequence {ξ _j :j?1}, then under appropriate regularity conditions $$E\left[ {U\left| {\xi _0 + S_n } \right. = \sum\limits_{j = 1}^n {\mu _j + c_n } } \right] = E[U] + O\left( {\frac{1}{{s_n^{1 + \delta } }}} \right) + O\left( {\frac{{|c_n |}}{{s_n^2 }}} \right)$$ whereS _n ?ξ₁+ξ₂+?+ξ _n ,μ _j ?E[ξ _j ],s _n ² ?Var[S _n ], andc _n =O(s _n ).     

Solution of the NP-hard total tardiness minimization problem in scheduling theory

The classical NP-hard (in the ordinary sense) problem of scheduling jobs in order to minimize the total tardiness for a single machine 1‖ΣT _j is considered. An NP-hard instance of the problem is completely analyzed. A procedure for partitioning the initial set of jobs into subsets is proposed. Algorithms are constructed for finding an optimal schedule depending on the number of subsets. The complexity of the algorithms is O(n ²Σp _j ), where n is the number of jobs and p _j is the processing time of the jth job (j = 1, 2, …, n).     

Characterization of the absence of a spectral gapfor a class of periodic Jacobi operators

Let q ∈ {2, 3} and let 0 = s₀ < s₁ < … < s_q = T be integers. For m, n ∈ Z, we put ¯m,n = {j ∈ Z| m? j ? n}. We set l_j = s_j − s_j−1 for j ∈ 1, q. Given (p₁,, p_q) ∈ R^q, let b: Z → R be a periodic function of period T such that b(·) = p_j on s_j−1 + 1, s_j for each j ∈ 1, q. We study the spectral gaps of the Jacobi operator (Ju)(n) = u(n + 1) + u(n − 1) + b(n)u(n) acting on l²(Z). By [λ_2j , λ_2j−1] we denote the jth band of the spectrum of J counted from above for j ∈ 1, T. Suppose that p_m ≠ p_n for m ≠ n. We prove that the statements (i) and (ii) below are equivalent for λ ∈ R and i ∈ 1, T − 1.     

Centers with degenerate infinity and their commutators

We study polynomial systems with degeneracy at infinity and a center-focus equilibrium at the origin. We give some general properties related to the existence of polynomial commutators and use these properties in order to characterize uniformly isochronous polynomial centers with polynomial commutator and, also, we show that the commutator of the centers of the analytic systems whose angular speed is constant can be chosen of radial form. Finally, we characterize the systems (−y+P_s+∑_j=kⁿ⁻¹xH_j,x+Q_s+∑_j=kⁿ⁻¹yH_j)^t with polynomial commutator, with P_j,Q_j,H_j and K_j homogeneous polynomials.     

Matrix orthogonal polynomials associated with perturbations of block Toeplitz matrices

Let {c _j } _j=0 ⁿ be a sequence of matrix moments associated with a matrix of measures supported on the unit circle, and let {P _j } _j=0 ⁿ be its corresponding sequence of monic matrix orthogonal polynomials. In this contribution, we consider a perturbation on the moments and find an explicit relation for the perturbed orthogonal polynomials in terms of {P _j } _j=0 ⁿ . We also obtain an expression for the corresponding second kind polynomials.     

Factorization of entire solutions of some algebraic differential equations

We investigate the factorization of entire solutions of the following algebraic differential equations:

bn(z)finjn(f^′)+bn−1(z)fin−1jn−1(f^′)+?+b₀(z)fi₀j₀(f^′)=b(z),     

Characterization of similarities between two n-frames of projectors

An n-frame on a Banach space $\text{X}$ is E=(E₁,?, E_n) where the E_j's are bounded linear operators on $\text{X}$ such that E_j≠0,

$\text{∑}\text{j=1}\text{n}\text{E}{}_{\mathrm{j}}$

, and E_jE_k=δ_jkE_k (j, k=1,?, n). It is known that if two n-frames E and F are sufficiently close to each other, then they are similar, that is, F_j=TE_jT^-1 with T a bounded linear operator. Among the operators which realize the similarity of the two frames, there is the balanced transformation U(F, E)=(Σⁿ_j=1F_jE_j)(Σⁿ_j=1E_jF_jE_j)^{$\text{-1}\text{2}$}. One of our main results is a local characterization of the balanced transformation. Another operator which implements the similarity between E and F is the direct rotation R(F, E). It comes up in connection with the study of the set of all n-frames as a Banach manifold with an affine connection. Finally, it is shown that for quite a large set of pairs of 2-frames, the direct rotation has a global characterization.     

On an inequality in probability

Inequalities are obtained forΣⁿ_im1P(A₁) when P(A₁A₁) 1? i < j ? n are known. The result improves an elementary inequality due to Erdös, Neveu, Renyi and Zybrzyck.     

r-Numbers completion problems of partial upper canonical form I

A pair (A, B), where A is an n × n matrix and B is an n × m matrix, is said to have the nonnegative integers sequence {r_j}_j=1^p as the r-numbers sequence if r₁ = rank(B) and r_j = rank[B AB … A^j−1 B] − rank[B AB … A^j−2B], 2 ≤ j ≤ p. Given a partial upper triangular matrix A of size n × n in upper canonical form and an n × m matrix B, we develop an algorithm that obtains a completion A_c of A, such that the pair (A^c, B) has an r-numbers sequence prescribed under some restrictions.     

Accurate approximation of time-varying matrices of linear differential systems

We consider the problem of the identification of the time-varying matrix A(t) of a linear m-dimensional differential system y′ = A(t)y. We develop an approximation A_n,k = ∑ⁿ_{j ? 1}c_j{Y(t_k + τ_j) Y^?1(t_k) ? I} to A(t_k) for grid points t_k = a + kh, k = 0,…, N using specified τ_j = θ_jh, 0 < θ_j < 1, j = 1, …, n, and show that for each t_k, the L₁ norm of the error matrix is $\text{O}$(hⁿ). We demonstrate an efficient scheme for the evaluation of A_n,k and treat sample problems.     

Sorting by means of swappings

If π is a permutation of {1,…,n}, then the effect of the swap S_ij on π is that the ith and fth entry are sorted. If [i?j] = l, we call S_ij a miniswap (it sorts neighbours). The paper studies a partial order based on the swaps, and establishes some properties of miniswaps.     

Fluctuations of the empirical quantiles of independent Brownian motions

We consider iid Brownian motions, B_j(t), where B_j(0) has a rapidly decreasing, smooth density function f. The empirical quantiles, or pointwise order statistics, are denoted by B_j:n(t), and we consider a sequence Q_n(t)=B_j(n):n(t), where j(n)/n→α∈(0,1). This sequence converges in probability to q(t), the α-quantile of the law of B_j(t). We first show convergence in law in C[0,∞) of F_n=n^1/2(Q_n−q). We then investigate properties of the limit process F, including its local covariance structure, and Hölder-continuity and variations of its sample paths. In particular, we find that F has the same local properties as fBm with Hurst parameter H=1/4.     

On the size of the Durfee square of a random integer partition

We prove a local limit theorem for the length of the side of the Durfee square in a random partition of a positive integer n as n→∞. We rely our asymptotic analysis on the power series expansion of x^m2∏_j=1^m(1−x^j)⁻² whose coefficient of xⁿ equals the number of partitions of n in which the Durfee square is m².     

Approximating reversal distance for strings with bounded number of duplicates

For a string A=a₁…a_n, a reversalρ(i,j), 1?i?j?n, transforms the string A into a string A^′=a₁…a_i-1a_ja_j-1…a_ia_j+1…a_n, that is, the reversal ρ(i,j) reverses the order of symbols in the substring a_i…a_j of A. In the case of signed strings, where each symbol is given a sign + or -, the reversal operation also flips the sign of each symbol in the reversed substring. Given two strings, A and B, signed or unsigned, sorting by reversals (SBR) is the problem of finding the minimum number of reversals that transform the string A into the string B.Traditionally, the problem was studied for permutations, that is, for strings in which every symbol appears exactly once. We consider a generalization of the problem, k-SBR, and allow each symbol to appear at most k times in each string, for some k?1. The main result of the paper is an O(k²)-approximation algorithm running in time O(n). For instances with , this is the best known approximation algorithm for k-SBR and, moreover, it is faster than the previous best approximation algorithm.     

Representation and index theory for C1-algebras generated by commuting isometries

We discuss here representation and Fredholm theory for C¹-algebras generated by commuting isometries. More particularly, for n commuting isometries {V_j: 1 ? j ? n} on separable Hilbert space we give a representation resembling the well-known representation for a single isometry. Our representation permits an analysis of the C¹-algebras $\text{Ol}$=$\text{Ol}$(V_j:1?j?n) generated by the {V_j}. The commutator ideal in $\text{Ol}$ is identified precisely and, under certain additional hypotheses, the Fredholm operators in $\text{Ol}$ are also precisely determined. Finally, we obtain formulas in terms of topological data for the index of Fredholm operators in some interesting algebras of the type $\text{Ol}$(V_j:1?j?n).     

Bernstein type operators having 1 and x j as fixed points

For certain generalized Bernstein operators {L _n } we show that there exist no i, j ∈ {1, 2, 3,…}, i < j, such that the functions e _i (x) = x ⁱ and e _j (x) = x ^j are preserved by L _n for each n = 1, 2,… But there exist infinitely many e _i such that e ₀(x) = 1 and e _j (x) = x _j are its fixed points.     

The p-Regular Partition Function Modulo p

Let b_?(n) denote the number of ?-regular partitions of n, where ? is a positive power of a prime p. We study in this paper the behavior of b_?(n) modulo powers of p. In particular, we prove that for every positive integer j, b_?(n) lies in each residue class modulo p^j for infinitely many values of n.     

GLOBAL EXISTENCE OF THE SOLUTION OF NONLINEAR SCHRDINGER EQUATIONS IN EXTERIOR DOMAINS

In this paper,we discuss the problem for the nonlinear Schr(?)dinger equation(?)where Ω is the exterior domain of a compact set in B~n,a_j(u)=O(|u|),b_j(u)=O(|u|)(1≤j≤n),c(u)=O(|u|~2)near u=0.If n≥5,some Sobolev norm of u_0(x)is sufficiently small,under suitableassumptions on smoothnessand and compatibility and the shape of Ω,we get that the problem has aunique global solution u(t,x),with the decay estimate‖u(t,·)‖_(L(?)(Ω))=O(t~(-n/4)),‖u(t,·)‖_(L~4(Ω))=O(t~(-n/4)),t→+∞.     

Continuity properties of the Drazin pseudoinverse

Let B^D denote that Drazin inverse of the n×n complex matrix B. Define the core-rank of B as rank (B^i(B)) where i(B) is the index of B. Let j = 1,2,…, and A_j and A be square matrices such that A_i converges to A with respect to some norm. The main result of this paper is that A_j^D converges to A^D if and only if there exist a j₀ such that core-rank A_j=core-rankA for j ? j₀.