New MILP models for the permutation flowshop problem

Two new mixed-integer linear programming (MILP) models for the regular permutation flowshop problem, called TBA and TS3, are derived using a combination of JAML (job-adjacency, machine-linkage) diagrams and variable substitution techniques. These new models are then compared to the incumbent best MILP models (Wilson, WST2, and TS2) for this problem found in the flowshop sequencing literature. We define the term best to mean that a particular model or set of models can solve a common set of test flowshop problems in significantly less time than other competing models. In other words, the two new MILP models (TBA and TS3) become the challengers to the current incumbent best models (Wilson, WST2, TS2.). Both new models are shown to require less time, on average, than the current best models for solving this set of problems; and the TS3 model is shown to solve these problems in statistically significantly less time than the other four models combined.     

Minimizing the number of early jobs on a proportionate flowshop

A proportionate flowshop is a special case of the classical flowshop, where the job processing times are machine-independent. We study the problem of minimizing the number of early jobs in this machine setting. This objective function has hardly been investigated on a single machine, and never on a flowshop. We introduce an efficient iterative solution algorithm. In each iteration, a single job is moved to the first position (and is added to the set of early jobs), and the remaining jobs are rescheduled such that the maximum earliness is minimized. The algorithm guarantees an optimal solution in O(n³) time, where n is the number of jobs.     

Flowshop scheduling problem to minimize total completion time with random and bounded processing times

The flowshop scheduling problems with n jobs processed on two or three machines, and with two jobs processed on k machines are addressed where jobs have random and bounded processing times. The probability distributions of random processing times are unknown, and only the lower and upper bounds of processing times are given before scheduling. In such cases, there may not exist a unique schedule that remains optimal for all feasible realizations of the processing times, and therefore, a set of schedules has to be considered which dominates all other schedules for the given criterion. We obtain sufficient conditions when transposition of two jobs minimizes total completion time for the cases of two and three machines. The geometrical approach is utilized for flowshop problem with two jobs and k machines.     

Basics of the Quasiconformal Analysis of a Two-Index Scale of Spatial Mappings

We define a scale of mappings that depends on two real parameters p and q, n?1 ≤ q ≤ p < ∞ and a weight function θ. In the case of q = p = n, θ ≡ 1, we obtain the well-known mappings with bounded distortion. Mappings of a two-index scale inherit many properties of mappings with bounded distortion. They are used for solving a few problems of global analysis and applied problems.     

Two-stage assembly-type flowshop batch scheduling problem subject to a fixed job sequence

This paper discusses a two-stage assembly-type flowshop scheduling problem with batching considerations subject to a fixed job sequence. The two-stage assembly flowshop consists of m stage-1 parallel dedicated machines and a stage-2 assembly machine which processes the jobs in batches. Four regular performance metrics, namely, the total completion time, maximum lateness, total tardiness, and number of tardy jobs, are considered. The goal is to obtain an optimal batching decision for the predetermined job sequence at stage 2. This study presents a two-phase algorithm, which is developed by coupling a problem-transformation procedure with a dynamic program. The running time of the proposed algorithm is O(mn+n⁵), where n is the number of jobs.     

Asymptotics for the Euler-Discretized Hull-White Stochastic Volatility Model

We consider the stochastic volatility model d S _t = σ _t S _t d W _t ,d σ _t = ω σ _t d Z _t , with (W _t ,Z _t ) uncorrelated standard Brownian motions. This is a special case of the Hull-White and the β=1 (log-normal) SABR model, which are widely used in financial practice. We study the properties of this model, discretized in time under several applications of the Euler-Maruyama scheme, and point out that the resulting model has certain properties which are different from those of the continuous time model. We study the asymptotics of the time-discretized model in the n→∞ limit of a very large number of time steps of size τ, at fixed \(\beta =\frac 12\omega ^{2}\tau n^{2}\) and \(\rho ={\sigma _{0}^{2}}\tau \), and derive three results: i) almost sure limits, ii) fluctuation results, and iii) explicit expressions for growth rates (Lyapunov exponents) of the positive integer moments of S _t . Under the Euler-Maruyama discretization for (S _t ,logσ _t ), the Lyapunov exponents have a phase transition, which appears in numerical simulations of the model as a numerical explosion of the asset price moments. We derive criteria for the appearance of these explosions.     

A partially isochronous splitting algorithm for three-block separable convex minimization problems

During the last decade, the state-of-the-art alternating direction method of multipliers (ADMM) has successfully been used to solve many two-block separable convex minimization problems arising from several applied areas such as signal/image processing and statistical and machine learning. It however remains an interesting problem of how to implement ADMM to three-block separable convex minimization problems as required by the situation where many objective functions in the above-mentioned areas are actually more conveniently decomposed to the sum of three convex functions, due also to the observation that the straightforward extension of ADMM from the two-block case to the three-block case is apparently not convergent. In this paper, we shall introduce a new algorithm that is called a partially isochronous splitting algorithm (PISA) in order to implement ADMM for the three-block separable model. The main idea of our algorithm is to incorporate only one proximal term into the last subproblem of the extended ADMM so that the resulting algorithm maximally inherits the promising properties of ADMM. A remarkable superiority over the extended ADMM is that we can simultaneously solve two of the subproblems, thereby taking advantages of the separable structure and parallel architectures. Theoretically, we will establish the global convergence of our algorithm under standard conditions, and also the O(1/t) rate of convergence in both ergodic and nonergodic senses, where t is the iteration counter. The computational competitiveness of our algorithm is shown by numerical experiments on an application to the well-tested robust principal component analysis model.     

Koszul property of a class of graded algebras with nonpure resolutions

Given any integers a, b, c, and d with a > 1, c ≥ 0, b ≥ a + c, and d ≥ b + c, the notion of (a, b, c, d)-Koszul algebra is introduced, which is another class of standard graded algebras with “nonpure” resolutions, and includes many Artin-Schelter regular algebras of low global dimension as specific examples. Some basic properties of (a, b, c, d)-Koszul algebras/modules are given, and several criteria for a standard graded algebra to be (a, b, c, d)-Koszul are provided.     

Solutions to the Constrained Flowshop Sequencing Problem

If the flowshop sequencing problem is constrained so that job profiles are maintained independently of other work on the shop, then a range of new problem solutions are possible. Using geometrical relationships between the cumulative process times, a slope matching method has been devised which generally provides better results than Palmer's method and Gupta's algorithm. Secondly, it has been possible to reformulate the flowshop sequencing problem in terms of the travelling salesman problem. This has enabled the performance of the slope matching, Palmer and Gupta methods to be compared against a non-heuristic solution. Finally, provided that expressing a job in terms of the slopes of the cumulative start and end times is satisfactory, this enables in n-job, M-machine flowshop to be converted into an equivalent n-job 2 machine flowshop to which the use of Johnson's method will provide optimal sequences.     

Under-recurrence in the Khintchine recurrence theorem

The Khintchine recurrence theorem asserts that in a measure preserving system, for every set A and ε > 0, we have μ(A ∩ T^?nA) ≥ μ(A)² ? ε for infinitely many n ∈ N. We show that there are systems having underrecurrent sets A, in the sense that the inequality μ(A ∩ T^?nA) < μ(A)² holds for every n ∈ N. In particular, all ergodic systems of positive entropy have under-recurrent sets. On the other hand, answering a question of V. Bergelson, we show that not all mixing systems have under-recurrent sets. We also study variants of these problems where the previous strict inequality is reversed, and deduce that under-recurrence is a much more rare phenomenon than over-recurrence. Finally, we study related problems pertaining to multiple recurrence and derive some interesting combinatorial consequences.     

New Applications of the <Emphasis Type="Italic">p</Emphasis>-Adic Nevanlinna Theory

Let IK be an algebraically closed field of characteristic 0 complete for an ultrametric absolute value. Following results obtained in complex analysis, here we examine problems of uniqueness for meromorphic functions having finitely many poles, sharing points or a pair of sets (C.M. or I.M.) defined either in the whole field IK or in an open disk, or in the complement of an open disk. Following previous works in C, we consider functions fⁿ(x)f^m(ax + b), gⁿ(x)g^m(ax + b) with |a| = 1 and n ≠ m, sharing a rational function and we show that f/g is a n + m-th root of 1 whenever n + m ≥ 5. Next, given a small function w, if n, m ∈ IN are such that |n ? m|_∞ ≥ 5, then fⁿ(x)f^m(ax + b) ? w has infinitely many zeros. Finally, we examine branched values for meromorphic functions fⁿ(x)f^m(ax + b).     

A hybrid shifting bottleneck procedure algorithm for the parallel-machine job-shop scheduling problem

In practice, parallel-machine job-shop scheduling (PMJSS) is very useful in the development of standard modelling approaches and generic solution techniques for many real-world scheduling problems. In this paper, based on the analysis of structural properties in an extended disjunctive graph model, a hybrid shifting bottleneck procedure (HSBP) algorithm combined with Tabu Search (TS) metaheuristic algorithm is developed to deal with the PMJSS problem. The original-version shifting bottleneck procedure (SBP) algorithm for the job-shop scheduling (JSS) has been significantly improved to solve the PMJSS problem with four novelties: (i) a topological-sequence algorithm is proposed to decompose the PMJSS problem in a set of single-machine scheduling (SMS) and/or parallel-machine scheduling subproblems; (ii) a modified Carlier algorithm based on the proposed lemmas and the proofs is developed to solve the SMS subproblem; (iii) the Jackson rule is extended to solve the PMS subproblem; (iv) a TS metaheuristic algorithm is embedded under the framework of SBP to optimise the JSS and PMJSS cases. The computational experiments show that the proposed HSBP is very efficient in solving the JSS and PMJSS problems.     

Cauchy problem for the Korteweg-de Vries equation in the case of a nonsmooth unbounded initial function

In the strip П = (?1, 0) × ?, we establish the existence of solutions of the Cauchy problem for the Korteweg-de Vries equation u _t + u _xxx + uu _x = 0 with initial condition either 1) u(?1, x) = ?xθ(x), or 2) u(?1, x) = ?xθ(?x), where θ is the Heaviside function. The solutions constructed in this paper are infinitely smooth for t ∈ (?1, 0) and rapidly decreasing as x → +∞. For the case of the first initial condition, we also establish uniqueness in a certain class. Similar special solutions of the KdV equation arise in the study of the asymptotic behavior with respect to small dispersion of the solutions of certain model problems in a neighborhood of lines of weak discontinuity.     

The Systems Approach to Hospitals

By exploiting the relationship between scheduling and sorting, this paper describes a functional heuristic algorithm for seeking a quick and approximate solution to the n-job, M-machine flowshop scheduling problem under the assumption that all jobs are processed on all machines in the same order and no passing of jobs is permitted. The proposed functional heuristic algorithm can be executed by hand for reasonably large size problems and yields solutions which are closer to optimal solutions than those obtained by Palmer's slope index algorithm.     

Extended phase properties and stability analysis of RKN-type integrators for solving general oscillatory second-order initial value problems

In this paper, we study in detail the phase properties and stability of numerical methods for general oscillatory second-order initial value problems whose right-hand side functions depend on both the position y and velocity y ^'. In order to analyze comprehensively the numerical stability of integrators for oscillatory systems, we introduce a novel linear test model y ^?(t) + ? ² y(t) + µ y ^'(t)=0 with µ<2?. Based on the new model, further discussions and analysis on the phase properties and stability of numerical methods are presented for general oscillatory problems. We give the new definitions of dispersion and dissipation which can be viewed as an essential extension of the traditional ones based on the linear test model y ^?(t) + ? ² y(t)=0. The numerical experiments are carried out, and the numerical results showthatthe analysisofphase properties and stability presentedinthispaper ismoresuitableforthenumericalmethodswhentheyareappliedtothe generaloscillatory second-order initial value problem involving both the position and velocity.     

Variations of Landau’s theorem for p-regular and p-singular conjugacy classes

The well-known Landau’s theorem states that, for any positive integer k, there are finitely many isomorphism classes of finite groups with exactly k (conjugacy) classes. We study variations of this theorem for p-regular classes as well as p-singular classes. We prove several results showing that the structure of a finite group is strongly restricted by the number of p-regular classes or the number of p-singular classes of the group. In particular, if G is a finite group with O_p(G) = 1 then |G/F(G)|_p' is bounded in terms of the number of p-regular classes of G. However, it is not possible to prove that there are finitely many groups with no nontrivial normal p-subgroup and kp-regular classes without solving some extremely difficult number-theoretic problems (for instance, we would need to show that the number of Fermat primes is finite).     

Indecomposable decompositions of modular standard modules for two families of association schemes

We investigate the indecomposable decomposition of the modular standard modules of two families of association schemes of finite order. First, we show that, for each prime number p, the standard module over a field F of characteristic p of a residually thin scheme S of p-power order is an indecomposable FS-module. Second, we describe the indecomposable decomposition of the standard module over a field of positive characteristic of a wreath product of finitely many association schemes of rank 2.     

On the curve of critical exponents for nonlinear elliptic problems in the case of a zero mass

For semilinear elliptic equations ?Δu = λ|u| ^p?2 u?|u| ^q?2 u, boundary value problems in bounded and unbounded domains are considered. In the plane of exponents p × q, the so-called curves of critical exponents are defined that divide this plane into domains with qualitatively different properties of the boundary value problems and the corresponding parabolic equations. New solvability conditions for boundary value problems, conditions for the stability and instability of stationary solutions, and conditions for the existence of global solutions to parabolic equations are found.     

Planar Posets,Dimension, Breadth and the Number of Minimal Elements

In recent years, researchers have shown renewed interest in combinatorial properties of posets determined by geometric properties of its order diagram and topological properties of its cover graph. In most cases, the roots for the problems being studied today can be traced back to the 1970’s, and sometimes even earlier. In this paper, we study the problem of bounding the dimension of a planar poset in terms of the number of minimal elements, where the starting point is the 1977 theorem of Trotter and Moore asserting that the dimension of a planar poset with a single minimal element is at most 3. By carefully analyzing and then refining the details of this argument, we are able to show that the dimension of a planar poset with t minimal elements is at most 2t + 1. This bound is tight for t = 1 and t = 2. But for t ≥ 3, we are only able to show that there exist planar posets with t minimal elements having dimension t + 3. Our lower bound construction can be modified in ways that have immediate connections to the following challenging conjecture: For every d ≥ 2, there is an integer f(d) so that if P is a planar poset with dim(P) ≥ f(d), then P contains a standard example of dimension d. To date, the best known examples only showed that the function f, if it exists, satisfies f(d) ≥ d + 2. Here, we show that lim _d→∞ f(d)/d ≥ 2.     

A Special Multi-Objective Assignment Problem

The following assignment problem is considered. There are n activities to be assigned to n personnel. The cost of assigning activity i to person j is c _ij . It is required to find all the efficient assignments, i.e. those for which there exists no other assignment which has at least as small costs for each person and strictly smaller costs for at least one person. The main results are as follows. In Theorem 1 it is shown that whereas, for many integer problems, the standard scalar weighting factor approach will not produce all the efficient solutions, in this case it will. In Theorem 2 it is shown that when each efficient vector is determined by a single assignment solution, the efficient set is identical to the set of efficient vertices of the convex hull of the assignment solution set.