A single-machine scheduling problem with maintenance activities to minimize makespan

We study a single-machine scheduling problem with periodic maintenance activity under two maintenance stratagems. Although the scheduling problem with single or periodic maintenance and nonresumable jobs has been well studied, most of past studies considered only one maintenance stratagem. This research deals with a single-machine scheduling problem where the machine should be stopped for maintenance after a fixed periodic interval (T) or after a fixed number of jobs (K) have been processed. The objective is to minimize the makespan for the addressed problem. A two-stage binary integer programming (BIP) model is provided for driving the optimal solution up to 350-job instances. For the large-sized problems, two efficient heuristics are provided for the different combinations of T and K. Computational results show that the proposed algorithm Best-Fit-Butterfly (BBF) performs well because the total average percentage error is below 1%. Once the constraint of the maximum number of jobs (K) processed in the machine’s available time interval (T) is equal or larger than half of jobs, the heuristic Best-Fit-Decreasing (DBF) is strongly recommended.     

Properties of non-simultaneous blow-up in heat equations coupled via different localized sources

This paper deals with u_t = Δu + u^m(x, t)e^pv(0,t), v_t = Δv + u^q(0, t)e^nv(x,t), subject to homogeneous Dirichlet boundary conditions. The complete classification on non-simultaneous and simultaneous blow-up is obtained by four sufficient and necessary conditions. It is interesting that, in some exponent region, large initial data u₀(v₀) leads to the blow-up of u(v), and in some betweenness, simultaneous blow-up occurs. For all of the nonnegative exponents, we find that u(v) blows up only at a single point if m > 1(n > 0), while u(v) blows up everywhere for 0 ? m ? 1 (n = 0). Moreover, blow-up rates are considered for both non-simultaneous and simultaneous blow-up solutions.     

Mutually independent bipanconnected property of hypercube

A graph is denoted by G with the vertex set V(G) and the edge set E(G). A path P = 〈v₀, v₁, … , v_m〉 is a sequence of adjacent vertices. Two paths with equal length P₁ = 〈 u₁, u₂, … , u_m〉 and P₂ = 〈 v₁, v₂, … , v_m〉 from a to b are independent if u₁ = v₁ = a, u_m = v_m = b, and u_i ≠ v_i for 2 ? i ? m − 1. Paths with equal length from a to b are mutually independent if they are pairwisely independent. Let u and v be two distinct vertices of a bipartite graph G, and let l be a positive integer length, d_G(u, v) ? l ? ∣V(G) − 1∣ with (l − d_G(u, v)) being even. We say that the pair of vertices u, v is (m, l)-mutually independent bipanconnected if there exist m mutually independent paths with length l from u to v. In this paper, we explore yet another strong property of the hypercubes. We prove that every pair of vertices u and v in the n-dimensional hypercube, with d_Qn(u,v)?n-1, is (n − 1, l)-mutually independent bipanconnected for every with (l-d_Qn(u,v)) being even. As for d_Qn(u,v)?n-2, it is also (n − 1, l)-mutually independent bipanconnected if l?d_Qn(u,v)+2, and is only (l, l)-mutually independent bipanconnected if l=d_Qn(u,v).     

A residual transcendental extension of a valuation on K to K(x1, … , xn)

Let v be a valuation of a field K, G_v its value group and k_v its residue field. Let w be an extension of v to K(x₁, … , x_n). w is called a residual transcendental extension of v if k_w/k_v is a transcendental extension. In this study a residual transcendental extension w of v to K(x₁, … , x_n) such that transdegk_w/k_v = n is defined and some considerations related with this valuation are given.     

The asymptotic distribution of weighted empirical distribution functions

Let G_n denote the empirical distribution based on n independent uniform (0, 1) random variables. The asymptotic distribution of the supremum of weighted discrepancies between G_n(u) and u of the forms 6w_v(u)D_n(u)6 and 6w_v(G_n(u))D_n(u)6, where D_n(u) = G_n(u)?u, w_v(u) = (u(1?u))^?1+v and 0 ? v < $\text{1}\text{2}$ is obtained. Goodness-of-fit tests based on these statistics are shown to be asymptotically sensitive only in the extreme tails of a distribution, which is exactly where such statistics that use a weight function w_v with $\text{1}\text{2}$ ? v ? 1 are insensitive. For this reason weighted discrepancies which use the weight function w_v with 0 ? v < $\text{1}\text{2}$ are potentially applicable in the construction of confidence contours for the extreme tails of a distribution.     

Existence and Nonexistence of Entire Positive Solutions of Semilinear Elliptic Systems

We show that entire positive solutions exist for the semilinear elliptic system Δu = p(x)v^α, Δv = q(x)u^β on R^N, N ≥ 3, for positive α and β, provided that the nonnegative functions p and q are continuous and satisfy appropriate decay conditions at infinity. We also show that entire solutions fail to exist if the functions p and q are of slow decay.     

On palindromic factorization of words

Given a finite word u, we define its palindromic length  _|u|pal${|u|}_{\mathrm{pal}}$ to be the least number n   such that u=_v1v2…_vn$u=v_1{v}_2\dots v_n$ with each _vi$v_i$ a palindrome. We address the following open question: let P be a positive integer and w   an infinite word such that _|u|pal?P${|u|}_{\mathrm{pal}}?P$ for every factor u of w. Must w be ultimately periodic? We give a partial answer to this question by proving that for each positive integer k, the word w must contain a k  -power, i.e., a factor of the form u^k$u^k$. In particular, w cannot be a fixed point of a primitive morphism. We also prove more: for each pair of positive integers k and l, the word w must contain a position covered by at least l distinct k-powers. In particular, w cannot be a Sierpinski-like word.     

Customer order scheduling to minimize the number of late jobs

In the order scheduling problem, every job (order) consists of several tasks (product items), each of which will be processed on a dedicated machine. The completion time of a job is defined as the time at which all its tasks are finished. Minimizing the number of late jobs was known to be strongly NP-hard. In this note, we show that no FPTAS exists for the two-machine, common due date case, unless P = NP. We design a heuristic algorithm and analyze its performance ratio for the unweighted case. An LP-based approximation algorithm is presented for the general multicover problem. The algorithm can be applied to the weighted version of the order scheduling problem with a common due date.     

A note on “scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan”

In a recent paper, Chen [J.S. Chen, Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan, European Journal of Operational Research 190 (2008) 90–102] proposes a heuristic algorithm to deal with the problem Scheduling of Nonresumable Jobs and Flexible Maintenance Activities on A Single Machine to Minimize Makespan  . Chen also provides computational results to demonstrate its effectiveness. In this note, we first show that the worst-case performance bound of this heuristic algorithm is 2. Then we show that there is no polynomial time approximation algorithm with a worst-case performance bound less than 2 unless P=NP$P=\mathit{NP}$, which implies that Chen’s heuristic algorithm is the best possible polynomial time approximation algorithm for the considered scheduling problem.     

A full second order variational model for multiscale texture analysis

We present a second order image decomposition model to perform denoising and texture extraction. We look for the decomposition f=u+v+w where u is a first order term, v a second order term and w the (0 order) remainder term. For highly textured images the model gives a two-scale texture decomposition: u can be viewed as a macro-texture (larger scale) whose oscillations are not too large and w is the micro-texture (very oscillating) that may contain noise. We perform mathematical analysis of the model and give numerical examples.     

Estimates of solutions of impulsive parabolic equations under Neumann boundary condition

In this paper, we prove the relation v(t)?u(t,x)?w(t), where u(t,x) is the solution of an impulsive parabolic equations under Neumann boundary condition ∂u(t,x)/∂ν=0, and v(t) and w(t) are solutions of two impulsive ordinary equations. We also apply these estimates to investigate the asymptotic behavior of a model in the population dynamics, and it is shown that there exists a unique solution of the model which converges to the periodic solution of an impulsive ordinary equation asymptotically.     

A note on the partition dimension of Cartesian product graphs

Let G = (V, E) be a connected graph. The distance between two vertices u, v ∈ V, denoted by d(u, v), is the length of a shortest u − v path in G. The distance between a vertex v ∈ V and a subset P ⊂ V is defined as , and it is denoted by d(v, P). An ordered partition {P₁, P₂, … , P_t} of vertices of a graph G, is a resolving partition of G, if all the distance vectors (d(v, P₁), d(v, P₂), … , d(v, P_t)) are different. The partition dimension of G, denoted by pd(G), is the minimum number of sets in any resolving partition of G. In this article we study the partition dimension of Cartesian product graphs. More precisely, we show that for all pairs of connected graphs G, H, pd(G × H) ? pd(G) + pd(H) and pd(G × H) ? pd(G) + dim(H), where dim(H) denotes the metric dimension of H. Consequently, we show that pd(G × H) ? dim(G) + dim(H) + 1.     

The induced path function, monotonicity and betweenness

The geodesic interval function I of a connected graph allows an axiomatic characterization involving axioms on the function only, without any reference to distance, as was shown by Nebeský [20]. Surprisingly, Nebeský [23] showed that, if no further restrictions are imposed, the induced path function J of a connected graph G does not allow such an axiomatic characterization. Here J(u,v) consists of the set of vertices lying on the induced paths between u and v. This function is a special instance of a transit function. In this paper we address the question what kind of restrictions could be imposed to obtain axiomatic characterizations of J. The function J satisfies betweenness if w∈J(u,v), with w≠u, implies u∉J(w,v) and x∈J(u,v) implies J(u,x)⊆J(u,v). It is monotone if x,y∈J(u,v) implies J(x,y)⊆J(u,v). In the case where we restrict ourselves to functions J that satisfy betweenness, or monotonicity, we are able to provide such axiomatic characterizations of J by transit axioms only. The graphs involved can all be characterized by forbidden subgraphs.     

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.     

Global existence and asymptotic convergence of weak solutions for the one-dimensional Navier-Stokes equations with capillarity and nonmonotonic pressure

We construct global weak solution of the Navier-Stokes equations with capillarity and nonmonotonic pressure. The volume variable v₀ is initially assumed to be in H¹ and the velocity variable u₀ to be in L² on a finite interval [0,1]. We show that both variables become smooth in positive time and that asymptotically in time u→0 strongly in L²([0,1]) and v approaches the set of stationary solutions in H¹([0,1]).     

Preemptive multiprocessor order scheduling to minimize total weighted flowtime

Consider m identical machines in parallel, each of which can produce k different product types. There is no setup cost when the machines switch from producing one product type to another. There are n orders each of which requests various quantities of the different product types. All orders are available for processing at time t = 0, and preemption is allowed. Order i has a weight w_i and its completion time is the time when its last requested product type finishes. Our goal is to find a preemptive schedule such that the total weighted completion time ∑_wiCi$\sum w_i{C}_i$ is minimized. We show that this problem is NP-hard even when all jobs have identical weights and there are only two machines. Motivated by the computational complexity of the problem, we propose a simple heuristic and show that it obeys a worst-case bound of 2 − 1/m. Finally, empirical studies show that our heuristic performs very well when compared with a lower bound of the optimal cost.     

Distance-hereditary graphs and signpost systems

An ordered pair (U,R) is called a signpost system if U is a finite nonempty set, R⊆U×U×U, and the following axioms hold for all u,v,w∈U: (1) if (u,v,w)∈R, then (v,u,u)∈R; (2) if (u,v,w)∈R, then (v,u,w)∉R; (3) if u≠v, then there exists t∈U such that (u,t,v)∈R. (If F is a (finite) connected graph with vertex set U and distance function d, then U together with the set of all ordered triples (u,v,w) of vertices in F such that d(u,v)=1 and d(v,w)=d(u,w)−1 is an example of a signpost system). If (U,R) is a signpost system and G is a graph, then G is called the underlying graph of (U,R) if V(G)=U and xy∈E(G) if and only if (x,y,y)∈R (for all x,y∈U). It is possible to say that a signpost system shows a way how to travel in its underlying graph. The following result is proved: Let (U,R) be a signpost system and let G denote the underlying graph of (U,R). Then G is connected and every induced path in G is a geodesic in G if and only if (U,R) satisfies axioms (4)-(8) stated in this paper; note that axioms (4)-(8)-similarly as axioms (1)-(3)-can be formulated in the language of the first-order logic.     

Semiconductor final test scheduling with Sarsa(λ, k) algorithm

Semiconductor test scheduling problem is a variation of reentrant unrelated parallel machine problems considering multiple resource constraints, intricate {product, tester, kit, enabler assembly} eligibility constraints, sequence-dependant setup times, etc. A multi-step reinforcement learning (RL) algorithm called Sarsa(λ, k) is proposed and applied to deal with the scheduling problem with throughput related objective. Allowing enabler reconfiguration, the production capacity of the test facility is expanded and scheduling optimization is performed at the bottom level. Two forms of Sarsa(λ, k), i.e. forward view Sarsa(λ, k) and backward view Sarsa(λ, k), are constructed and proved equivalent in off-line updating. The upper bound of the error of the action-value function in tabular Sarsa(λ, k) is provided when solving deterministic problems. In order to apply Sarsa(λ, k), the scheduling problem is transformed into an RL problem by representing states, constructing actions, the reward function and the function approximator. Sarsa(λ, k) achieves smaller mean scheduling objective value than the Industrial Method (IM) by 68.59% and 76.89%, respectively for real industrial problems and randomly generated test problems. Computational experiments show that Sarsa(λ, k) outperforms IM and any individual action constructed with the heuristics derived from the existing heuristics or scheduling rules.     

Weinbaum factorizations of primitive words

C. M. Weinbaum [1] showed the following: Let w be a primitive word and a be letter in w. Then a conjugate of w can be written as uv such that a is a prefix and a suffix of u, but v neither starts nor ends with a, and u and v have a unique position in w as cyclic factors. The latter condition means that there is exactly one conjugate of w having u as a prefix and there is exactly one conjugate of w having v as a prefix. It is this condition which makes the result non-trivial. We give a simplified proof for Weinbaum’s result. Guided by this proof we exhibit quite different, but still simple, proofs for more general statements. For this purpose we introduce the notion of Weinbaum factor and Weinbaum factorization.