Optimal Control of the Obstacle for a Parabolic Variational Inequality

An optimal control problem for a parabolic obstacle variational inequality is considered. The obstacle in L²(0, T; H²(Ω) ∩ H¹₀(Ω)) with ψ_t ∈ L²(Q) is taken as the control, and the solution to the obstacle problem is taken as the state. The goal is to find the optimal control so that the state is close to the desired profile while the norm of the obstacle is not too large. Existence and necessary conditions for the optimal control are established.     

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.     

On the bin packing problem with a fixed number of object weights

We consider a bin packing problem where the number of different object weights is fixed to C. We analyze a simple approximate approach and show that it leads to an asymptotically exact polynomial algorithm with absolute error 0 if C = 2, at most 1 if 1 < C ? 6, and at most 1 + ⌊(C − 1)/3⌋ if C > 6. A consequence of our analysis is a new upper bound on the gap between the optimal value of the problem at hand and the round-up of the optimal value of the linear relaxation of its Gilmore–Gomory formulation.     

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.     

The two-machine no-wait general and proportionate open shop makespan problem

We consider the two-machine no-wait open shop minimum makespan problem in which the determination of an optimal solution requires an optimal pairing of the jobs followed by the optimal sequencing of the job pairs. We show that the required enumeration can be curtailed by reducing the pair sequencing problem for a given pair set to a traveling salesman problem which is equivalent to a two-machine no-wait flow shop problem solvable in O(n log n) time. We then propose an optimal O(n log n) algorithm for the proportionate problem with equal machine speeds in which each job has the same processing time on both machines. We show that our O(n log n) algorithm also applies to the more general proportionate problem with equal machine speeds and machine-specific setup times. We also analyze the proportionate problem with unequal machine speeds and conclude that the required enumeration can be further curtailed (compared to the problem with arbitrary job processing times) by eliminating certain job pairs from consideration.     

Joint pricing and inventory control with a Markovian demand model

We consider the joint pricing and inventory control problem for a single product over a finite horizon and with periodic review. The demand distribution in each period is determined by an exogenous Markov chain. Pricing and ordering decisions are made at the beginning of each period and all shortages are backlogged. The surplus costs as well as fixed and variable costs are state dependent. We show the existence of an optimal (s, S, p)-type feedback policy for the additive demand model. We extend the model to the case of emergency orders. We compute the optimal policy for a class of Markovian demand and illustrate the benefits of dynamic pricing over fixed pricing through numerical examples. The results indicate that it is more beneficial to implement dynamic pricing in a Markovian demand environment with a high fixed ordering cost or with high demand variability.     

Multi-degree cyclic scheduling of a no-wait robotic cell with multiple robots

This paper addresses cyclic scheduling of a no-wait robotic cell with multiple robots. In contrast to many previous studies, we consider r-degree cyclic (r > 1) schedules, in which r identical parts with constant processing times enter and leave the cell in each cycle. We propose an algorithm to find the minimal number of robots for all feasible r-degree cycle times for a given r (r > 1). Consequently, the optimal r-degree cycle time for any given number of robots for this given r can be obtained with the algorithm. To develop the algorithm, we first show that if the entering times of r parts, relative to the start of a cycle, and the cycle time are fixed, minimizing the number of robots for the corresponding r-degree schedule can be transformed into an assignment problem. We then demonstrate that the cost matrix for the assignment problem changes only at some special values of the cycle time and the part entering times, and identify all special values for them. We solve our problem by enumerating all possible cost matrices for the assignment problem, which is subsequently accomplished by enumerating intervals for the cycle time and linear functions of the part entering times due to the identification of the special values. The algorithm developed is shown to be polynomial in the number of machines for a fixed r, but exponential if r is arbitrary.     

Landau’s theorem for functions with logharmonic Laplacian

In this paper, we show the existence of Landau constant for functions with logharmonic Laplacian of the form F(z) = ∣z∣²L(z) + K(z), ∣z∣ < 1, where L is logharmonic and K is harmonic. Moreover, the problem of minimizing the area is solved     

Maximum order-index of matrices over commutative inclines: an answer to an open problem

This paper proves that the maximum order-index of n × n matrices over an arbitrary commutative incline equals (n − 1)² + 1. This is an answer to an open problem “Compute the maximum order-index of a member of M_n(L)”, proposed by Cao, Kim and Roush in a monograph Incline Algebra and Applications, 1984, where M_n(L) is the set of all n × n matrices over an incline L.     

Applications of bulk queues to group testing models with incomplete identification

A population of items is said to be “group-testable”, (i) if the items can be classified as “good” and “bad”, and (ii) if it is possible to carry out a simultaneous test on a batch of items with two possible outcomes: “Success” (indicating that all items in the batch are good) or “failure” (indicating a contaminated batch). In this paper, we assume that the items to be tested arrive at the group-testing centre according to a Poisson process and are served (i.e., group-tested) in batches by one server. The service time distribution is general but it depends on the batch size being tested. These assumptions give rise to the bulk queueing model M/G^(m,M)/1, where m and M(>m) are the decision variables where each batch size can be between m and M. We develop the generating function for the steady-state probabilities of the embedded Markov chain. We then consider a more realistic finite state version of the problem where the testing centre has a finite capacity and present an expected profit objective function. We compute the optimal values of the decision variables (m, M) that maximize the expected profit. For a special case of the problem, we determine the optimal decision explicitly in terms of the Lambert function.     

A finite difference solution to a two-dimensional parabolic inverse problem

In this paper, we consider the problem of finding u = u(x, y, t) and p = p(t) which satisfy u_t = u_xx + u_yy + p(t)u + ? in R × [0, T], u(x, y, 0) = f(x, y), (x, y) ∈ R = [0, 1] × [0, 1], u is known on the boundary of R and u(x^∗, y^∗, t) = E(t), 0 < t ? T, where E(t) is known and (x^∗, y^∗) is a given point of R. Through a function transformation, the nonlinear two-dimensional diffusion problem is transformed into a linear problem, and a backward Euler scheme is constructed. It is proved by the maximum principle that the scheme is uniquely solvable, unconditionally stable and convergent in L_∞ norm. The convergence orders of u and p are of O(τ + h²). The impact of initial data errors on the numerical solution is also considered. Numerical experiments are presented to illustrate the validity of the theoretical results.     

An inverse problem for computing a leading coefficient in the Sturm-Liouville operator by using the boundary data

We consider an inverse problem for identifying a leading coefficient α(x) in −(α(x)y′(x))′ + q(x)y(x) = H(x), which is known as an inverse coefficient problem for the Sturm-Liouville operator. We transform y(x) to u(x, t) =  (1 + t)y(x) and derive a parabolic type PDE in a fictitious time domain of t. Then we develop a Lie-group adaptive method (LGAM) to find the coefficient function α(x). When α(x) is a continuous function of x, we can identify it very well, by giving boundary data of y, y′ and α. The efficiency of LGAM is confirmed by comparing the numerical results with exact solutions. Although the data used in the identification are limited, we can provide a rather accurate solution of α(x).     

A Stefan problem for a non-classical heat equation with a convective condition

We prove the existence and uniqueness, local in time, of the solution of a one-phase Stefan problem for a non-classical heat equation for a semi-infinite material with a convective boundary condition at the fixed face x = 0. Here the heat source depends on the temperature at the fixed face x = 0 that provides a heating or cooling effect depending on the properties of the source term. We use the Friedman-Rubinstein integral representation method and the Banach contraction theorem in order to solve an equivalent system of two Volterra integral equations. We also obtain a comparison result of the solution (the temperature and the free boundary) with respect to the one corresponding with null source term.     

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.     

Efficient Chebyshev spectral methods for solving multi-term fractional orders differential equations

In this paper, we state and prove a new formula expressing explicitly the derivatives of shifted Chebyshev polynomials of any degree and for any fractional-order in terms of shifted Chebyshev polynomials themselves. We develop also a direct solution technique for solving the linear multi-order fractional differential equations (FDEs) with constant coefficients using a spectral tau method. The spatial approximation with its fractional-order derivatives (described in the Caputo sense) are based on shifted Chebyshev polynomials T_L,n(x) with x ∈ (0, L), L > 0 and n is the polynomial degree. We presented a shifted Chebyshev collocation method with shifted Chebyshev–Gauss points used as collocation nodes for solving nonlinear multi-order fractional initial value problems. Several numerical examples are considered aiming to demonstrate the validity and applicability of the proposed techniques and to compare with the existing results.     

On functions convex in the direction of the real axis with a fixed second coefficient

In the paper we consider the class Γ of analytic and univalent functions f in the unit disk Δ, normalized by f(0) = f′(0) − 1 = 0, having real coefficients and such that f(Δ) is convex in the direction of the real axis. We are especially interested in some subclasses of Γ. The most important of them is Γ(c) consisting of those functions which have the second coefficients of the Taylor expansion fixed and equal to c. We obtain the Koebe set for this class as well as for the classes Γ⁺(c) and Γ⁻(c) of functions which are in some sense convex in the direction of positive and negative axes respectively.     

From homogenization to averaging in cellular flows

We consider an elliptic eigenvalue problem with a fast cellular flow of amplitude A  , in a two-dimensional domain with L²$L^2$ cells. For fixed A  , and L→∞$L\to \infty$, the problem homogenizes, and has been well studied. Also well studied is the limit when L   is fixed, and A→∞$A\to \infty$. In this case the solution equilibrates along stream lines.     

Control parameter estimation in a semi-linear parabolic inverse problem using a high accurate method

Parabolic inverse problems have an important role in many branches of science and technology. The aim of this research work is to solve these classes of equations using a high order compact finite difference scheme. We consider the following inverse problem for finding u(x, t) and p(t) governed by u_t = u_xx + p(t)u + φ(x, t) with an over specified condition inside the domain. Spatial derivatives are approximated using central difference scheme. The time advancement of the simulation is performed using a “third order compact Runge-Kutta method”. The convergence orders for the approximation of both u and p are of o(k³ + h²) which improves the results obtained in the literature. An exact test case is used to evaluate the validity of our numerical analysis. We found that the accuracy of the results is better than that of previous works in the literature.     

Rank one operators and norm of elementary operators

Let A be a standard operator algebra acting on a (real or complex) normed space E. For two n-tuples A = (A₁, … , A_n) and B = (B₁, … , B_n) of elements in A, we define the elementary operator R_A,B on A by the relation for all X in A. For a single operator A∈A, we define the two particular elementary operators L_A and R_A on A by L_A(X) = AX and R_A(X) = XA, for every X in A. We denote by d(R_A,B) the supremum of the norm of R_A,B(X) over all unit rank one operators on E. In this note, we shall characterize: (i) the supremun d(R_A,B), (ii) the relation , (iii) the relation d(L_A − R_B) = ∥A∥ + ∥B∥, (iv) the relation d(L_AR_B − L_BR_A) = 2∥A∥ + ∥B∥. Moreover, we shall show the lower estimate d(L_A − R_B) ? max{sup_λ∈V(B)∥A − λI∥, sup_λ∈V(A)∥B − λI∥} (where V(X) is the algebraic numerical range of X in A).