Approximability of single machine scheduling with fixed jobs to minimize total completion time

We consider the single machine scheduling problem to minimize total completion time with fixed jobs, precedence constraints and release dates. There are some jobs that are already fixed in the schedule. The remaining jobs are free to be assigned to any free-time intervals on the machine in such a way that they do not overlap with the fixed jobs. Each free job has a release date, and the order of processing the free jobs is restricted by the given precedence constraints. The objective is to minimize the total completion time. This problem is strongly NP-hard. Approximability of this problem is studied in this paper. When the jobs are processed without preemption, we show that the problem has a linear-time n-approximation algorithm, but no pseudopolynomial-time (1 − δ)n-approximation algorithm exists even if all the release dates are zero, for any constant δ > 0, if P ≠ NP, where n is the number of jobs; for the case that the jobs have no precedence constraints and no release dates, we show that the problem has no pseudopolynomial-time (2 − δ)-approximation algorithm, for any constant δ > 0, if P ≠ NP, and for the weighted version, we show that the problem has no polynomial-time 2^q(n)-approximation algorithm and no pseudopolynomial-time q(n)-approximation algorithm, where q(n) is any given polynomial of n. When preemption is allowed, we show that the problem with independent jobs can be solved in O(n log n) time with distinct release dates, but the weighted version is strongly NP-hard even with no release dates; the problems with weighted independent jobs or with jobs under precedence constraints are shown having polynomial-time n-approximation algorithms. We also establish the relationship of the approximability between the fixed job scheduling problem and the bin-packing problem.     

A max version of the generalized spectral radius theorem

Let Ψ be a bounded set of n × n nonnegative matrices in max algebra. In this paper we propose the notions of the max algebra version of the generalized spectral radius μ(Ψ) of Ψ, and the max algebra version of the joint spectral radius η(Ψ) of Ψ. The max algebra version of the generalized spectral radius theorem μ(Ψ) = η(Ψ) is established. We propose the relationship between the generalized spectral radius ρ(Ψ) of Ψ (in the sense of Daubechies and Lagarias) and its max algebra version μ(Ψ). Moreover, a generalization of Elsner and van den Driessche’s lemma is presented as well.     

Approximating a two-machine flow shop scheduling under discrete scenario uncertainty

This paper deals with the two machine permutation flow shop problem with uncertain data, whose deterministic counterpart is known to be polynomially solvable. In this paper, it is assumed that job processing times are uncertain and they are specified as a discrete scenario set. For this uncertainty representation, the min-max and min-max regret criteria are adopted. The min-max regret version of the problem is known to be weakly NP-hard even for two processing time scenarios. In this paper, it is shown that the min-max and min-max regret versions of the problem are strongly NP-hard even for two scenarios. Furthermore, the min-max version admits a polynomial time approximation scheme if the number of scenarios is constant and it is approximable with performance ratio of 2 and not (4/3 − ?)-approximable for any ? > 0 unless P = NP if the number of scenarios is a part of the input. On the other hand, the min-max regret version is not at all approximable even for two scenarios.     

The destruction of tori in volume-preserving maps

Invariant tori are prominent features of symplectic and volume-preserving maps. From the point of view of chaotic transport the most relevant tori are those that are barriers, and thus have codimension one. For an n-dimensional volume-preserving map, such tori are prevalent when the map is nearly “integrable,” in the sense of having one action and n − 1 angle variables. As the map is perturbed, numerical studies show that the originally connected image of the frequency map acquires gaps due to resonances and domains of nonconvergence due to chaos. We present examples of a three-dimensional, generalized standard map for which there is a critical perturbation size, ε_c, above which there are no tori. Numerical investigations to find the “last invariant torus” reveal some similarities to the behavior found by Greene near a critical invariant circle for area preserving maps: the crossing time through the newly destroyed torus appears to have a power law singularity at ε_c, and the local phase space near the critical torus contains many high-order resonances.     

Minmax regret location–allocation problem on a network under uncertainty

We consider a robust location–allocation problem with uncertainty in demand coefficients. Specifically, for each demand point, only an interval estimate of its demand is known and we consider the problem of determining where to locate a new service when a given fraction of these demand points must be served by the utility. The optimal solution of this problem is determined by the “minimax regret” location, i.e., the point that minimizes the worst-case loss in the objective function that may occur because a decision is made without knowing which state of nature will take place. For the case where the demand points are vertices of a network we show that the robust location–allocation problem can be solved in O(min{p, n − p}n³m) time, where n is the number of demand points, p (p < n) is the fixed number of demand points that must be served by the new service and m is the number of edges of the network.     

Compositions of Polynomials with Coefficients in a Given Field

Let F ⊂ K be fields of characteristic 0, and let K[x] denote the ring of polynomials with coefficients in K. Let p(x) = ∑_k = 0ⁿa_kx^k ∈ K[x], a_n ≠ 0. For p ∈ K[x]\F[x], define D_F(p), the F deficit of p, to equal n − max{0 ≤ k ≤ n : a_k∉F}. For p ∈ F[x], define D_F(p) = n. Let p(x) = ∑_k = 0ⁿa_kx^k and let q(x) = ∑_j = 0^mb_jx^j, with a_n ≠ 0, b_m ≠ 0, a_n, b_m ∈ F, b_j∉F for some j ≥ 1. Suppose that p ∈ K[x], q ∈ K[x]\F[x], p, not constant. Our main result is that p ° q ∉ F[x] and D_F(p ° q) = D_F(q). With only the assumption that a_nb_m ∈ F, we prove the inequality D_F(p ° q) ≥ D_F(q). This inequality also holds if F and K are only rings. Similar results are proven for fields of finite characteristic with the additional assumption that the characteristic of the field does not divide the degree of p. Finally we extend our results to polynomials in two variables and compositions of the form p(q(x, y)), where p is a polynomial in one variable.     

Homotopy perturbation method for a limit case Stefan problem governed by fractional diffusion equation

The work presents a mathematical model describing the time fractional anomalous-diffusion process of a generalized Stefan problem which is a limit case of a shoreline problem. In this model, the governing equations include a fractional time derivative of order 0 < α ? 1 and variable latent heat. The approximate solution of the problem is obtained by homotopy perturbation method. The results thus obtained are compared graphically with the exact solutions. A brief sensitivity study is also performed.     

Existence and regularity of solution of mixed boundary value problem of a Busemann-equation with nonlinear absorb term

The Busemann-equation is a classical equation coming from fluid dynamics. The well-posed problem and regularity of solution of Busemann-equation with nonlinear term are interesting and important. The Busemann-equation is elliptic in y>0 and is degenerate at the line y=0 in R². With a special nonlinear absorb term, we study a nonlinear degenerate elliptic equation with mixed boundary conditions in a piecewise smooth domain. By means of elliptic regularization technique, a delicate prior estimate and compact argument, we show that the solution of mixed boundary value problem of Busemann-equation is smooth in the interior and Lipschitz continuous up to the degenerate boundary on some conditions. The result is better than the result of classical boundary degenerate elliptic equation.     

Problem F2∥Cmax with forbidden jobs in the first or last position is easy

Saadani et al. [N.E.H. Saadani, P. Baptiste, M. Moalla, The simple F2∥C_max with forbidden tasks in first or last position: A problem more complex that it seems, European Journal of Operational Research 161 (2005) 21–31] studied the classical n-job flow shop scheduling problem F2∥C_max with an additional constraint that some jobs cannot be placed in the first or last position. There exists an optimal job sequence for this problem, in which at most one job in the first or last position is deferred from its position in Johnson’s [S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly 1 (1954) 61–68] permutation. The problem was solved in O(n²) time by enumerating all candidate job sequences. We suggest a simple O(n) algorithm for this problem provided that Johnson’s permutation is given. Since Johnson’s permutation can be obtained in O(n log n) time, the problem in Saadani et al. (2005) can be solved in O(n log n) time as well.     

Batch delivery scheduling with batch delivery cost on a single machine

We consider a scheduling problem in which n independent and simultaneously available jobs are to be processed on a single machine. The jobs are delivered in batches and the delivery date of a batch equals the completion time of the last job in the batch. The delivery cost depends on the number of deliveries. The objective is to minimize the sum of the total weighted flow time and delivery cost. We first show that the problem is strongly NP-hard. Then we show that, if the number of batches is B, the problem remains strongly NP-hard when B ? U for a variable U ? 2 or B ? U for any constant U ? 2. For the case of B ? U, we present a dynamic programming algorithm that runs in pseudo-polynomial time for any constant U ? 2. Furthermore, optimal algorithms are provided for two special cases: (i) jobs have a linear precedence constraint, and (ii) jobs satisfy the agreeable ratio assumption, which is valid, for example, when all the weights or all the processing times are equal.     

Differential quadrature method (DQM) and Boubaker Polynomials Expansion Scheme (BPES) for efficient computation of the eigenvalues of fourth-order Sturm-Liouville problems

The differential quadrature method (DQM) and the Boubaker Polynomials Expansion Scheme (BPES) are applied in order to compute the eigenvalues of some regular fourth-order Sturm-Liouville problems. Generally, these problems include fourth-order ordinary differential equations together with four boundary conditions which are specified at two boundary points. These problems concern mainly applied-physics models like the steady-state Euler-Bernoulli beam equation and mechanicals non-linear systems identification. The approach of directly substituting the boundary conditions into the discrete governing equations is used in order to implement these boundary conditions within DQM calculations. It is demonstrated through numerical examples that accurate results for the first kth eigenvalues of the problem, where k = 1, 2, 3, … , can be obtained by using minimally 2(k + 4) mesh points in the computational domain. The results of this work are then compared with some relevant studies.     

Soliton solutions for (2 + 1)-dimensional and (3 + 1)-dimensional K(m, n) equations

We consider the nonlinear dispersive K(m,n) equation with the generalized evolution term and derive analytical expressions for some conserved quantities. By using a solitary wave ansatz in the form of sech^p function, we obtain exact bright soliton solutions for (2 + 1)-dimensional and (3 + 1)-dimensional K(m,n) equations with the generalized evolution terms. The results are then generalized to multi-dimensional K(m,n) equations in the presence of the generalized evolution term. An extended form of the K(m,n) equation with perturbation term is investigated. Exact bright soliton solution for the proposed K(m,n) equation having higher-order nonlinear term is determined. The physical parameters in the soliton solutions are obtained as function of the dependent model coefficients.     

Entropy solutions for a fourth-order nonlinear degenerate problem for noise removal

In this paper, we establish the existence and uniqueness of entropy solutions for a fourth-order nonlinear degenerate parabolic problem for noise removal in dimension 1≤d<4$1\le d<4$.     

Critical Exponents of Quasilinear Parabolic Equations

In this paper we study the critical exponents of the Cauchy problem in Rⁿ of the quasilinear singular parabolic equations: u_t = div(|∇u|^m − 1∇u) + t^s|x|^σu^p, with non-negative initial data. Here s ≥ 0, (n − 1)/(n + 1) < m < 1, p > 1 and σ > n(1 − m) − (1 + m + 2s). We prove that p_c ≡ m + (1 + m + 2s + σ)/n > 1 is the critical exponent. That is, if 1 < p ≤ p_c then every non-trivial solution blows up in finite time, but for p > p_c, a small positive global solution exists.     

Completion of a partial integral matrix to a unimodular matrix

We first characterize submatrices of a unimodular integral matrix. We then prove that if n entries of an n × n partial integral matrix are prescribed and these n entries do not constitute a row or a column, then this matrix can be completed to a unimodular matrix. Consequently an n × n partial integral matrix with n − 1 prescribed entries can always be completed to a unimodular matrix.     

Hermitian matrices with a bounded number of eigenvalues

Conjugation covariants of matrices are applied to study the real algebraic variety consisting of complex Hermitian matrices with a bounded number of distinct eigenvalues. A minimal generating system of the vanishing ideal of degenerate three by three Hermitian matrices is given, and the structure of the corresponding coordinate ring as a module over the special unitary group is determined. The method applies also for degenerate real symmetric three by three matrices. For arbitrary n   partial information on the minimal degree component of the vanishing ideal of the variety of n×n$n\times n$ Hermitian matrices with a bounded number of eigenvalues is obtained, and some known results on sum of squares presentations of subdiscriminants of real symmetric matrices are extended to the case of complex Hermitian matrices.