Gray code for derangements

We give a Gray code and constant average time generating algorithm for derangements, i.e., permutations with no fixed points. In our Gray code, each derangement is transformed into its successor either via one or two transpositions or a rotation of three elements. We generalize these results to permutations with number of fixed points bounded between two constants.     

Stage-structured Harvest Models

We formulate a stage-structured population model where the population is divided to two classes, the juveniles and the adults. Then, we include harvest in the model and assume that the harvesting is only on adults. The cases where the harvesting rate is constant, proportional to the amount of adults, or of Holling-II type are studied. While the model dynamics are relatively simple when the harvesting rate is proportional, the model system with a constant or a Holling-II type harvesting rate can have multiple positive equilibria. We explore the existence of all possible equilibria and investigate their stability. We also give numerical examples to confirm our findings.     

On fixed points of Knaster continua

Aarts and Fokkink [Proc. Amer. Math. Soc. 126 (1998) 881] have shown that any homeomorphism of the bucket handle has at least two fixed points. Using their methods, we determine the minimum number of fixed points homeomorphisms on generalized one-dimensional Knaster continua can have. We show that there is a class of these continua that admit homeomorphisms with a single fixed point. Among the examples is one that shows that Theorem 15 in [Proc. Amer. Math. Soc. 126 (1998) 881] is incorrect. We also show that there are generalized Knaster continua on which every homeomorphism has either uncountably many fixed points or uncountably many points of period two.     

An optimal replenishment policy for an EOQ model with partial backlogging

We study an inventory system where demand on the stockout period is partially backlogged. The backlogged demand ratio is a mixture of two exponential functions. The shortage cost has two significant costs: the unit backorder cost (which includes a fixed cost and a cost proportional to the length of time for which the backorder exists) and the cost of lost sales. A general procedure to determine the optimal policy and the minimum inventory cost for all the parameter values is developed. This model generalizes several inventory systems analyzed by different authors. Numerical examples are used to illustrate the theoretical results.     

Flexible servers in tandem lines with setup costs

We study the dynamic assignment of flexible servers to stations in the presence of setup costs that are incurred when servers move between stations. The goal is to maximize the long-run average profit. We provide a general problem formulation and some structural results, and then concentrate on tandem lines with two stations, two servers, and a finite buffer between the stations. We investigate how the optimal server assignment policy for such systems depends on the magnitude of the setup costs, as well as on the homogeneity of servers and tasks. More specifically, for systems with either homogeneous servers or homogeneous tasks, small buffer sizes, and constant setup cost, we prove the optimality of “multiple threshold” policies (where servers’ movement between stations depends on both the number of jobs in the system and the locations of the servers) and determine the values of the thresholds. For systems with heterogeneous servers and tasks, small buffers, and constant setup cost, we provide results that partially characterize the optimal server assignment policy. Finally, for systems with larger buffer sizes and various service rate and setup cost configurations, we present structural results for the optimal policy and provide numerical results that strongly support the optimality of multiple threshold policies.     

Approximation schemes for parallel machine scheduling with availability constraints

We investigate the problems of scheduling n weighted jobs to m parallel machines with availability constraints. We consider two different models of availability constraints: the preventive model, in which the unavailability is due to preventive machine maintenance, and the fixed job model, in which the unavailability is due to a priori assignment of some of the n jobs to certain machines at certain times. Both models have applications such as turnaround scheduling or overlay computing. In both models, the objective is to minimize the total weighted completion time. We assume that m is a constant, and that the jobs are non-resumable.For the preventive model, it has been shown that there is no approximation algorithm if all machines have unavailable intervals even if w_i=p_i for all jobs. In this paper, we assume that there is one machine that is permanently available and that the processing time of each job is equal to its weight for all jobs. We develop the first polynomial-time approximation scheme (PTAS) when there is a constant number of unavailable intervals. One main feature of our algorithm is that the classification of large and small jobs is with respect to each individual interval, and thus not fixed. This classification allows us (1) to enumerate the assignments of large jobs efficiently; and (2) to move small jobs around without increasing the objective value too much, and thus derive our PTAS. Next, we show that there is no fully polynomial-time approximation scheme (FPTAS) in this case unless P=NP.For the fixed job model, it has been shown that if job weights are arbitrary then there is no constant approximation for a single machine with 2 fixed jobs or for two machines with one fixed job on each machine, unless P=NP. In this paper, we assume that the weight of a job is the same as its processing time for all jobs. We show that the PTAS for the preventive model can be extended to solve this problem when the number of fixed jobs and the number of machines are both constants.     

Optimal control of the rectilinear motion of a rigid body on a rough plane by means of the motion of two internal masses

The problem of the optimal control of a rigid body moving along a rough horizontal plane due to motion of two internal masses is solved. One of the masses moves horizontally parallel to the line of motion of the main body, while the other mass moves in the vertical direction. Such a mechanical system models a vibration-driven robot–a mobile device able to move in a resistive medium without special propellers (e.g., wheels, legs or caterpillars). Periodic motions are constructed for the internal masses to ensure velocity-periodic motion of the main body with maximum average velocity, provided that the period is fixed and the magnitudes of the accelerations of the internal masses relative to the main body do not exceed prescribed limits. Based on the optimal solution obtained for a fixed period without any constraints imposed on the amplitudes of vibration of the internal masses, a suboptimal solution that takes such constraints into account is constructed.     

Scheduling in a multi-class series of queues with deterministic service times

We consider a problem of scheduling in a multi-class network of single-server queues in series, in which service times at the nodes are constant and equal. Such a model has potential application to automated manufacturing systems or packet-switched communication networks, where a message is divided into packets (or cells) of fixed lengths. The network is a series-type assembly or transfer line, with the exception that there is an additional class of jobs that requires processing only at the first node (class 0). There is a holding cost per unit time that is proportional to the total number of customers in the system. The objective is to minimize the (expected) total discounted holding cost over a finite or an infinite horizon. We show that an optimal policy gives priority to class-0 jobs at node 1 when at least one of a set ofm–1 inequalities on partial sums of the components of the state vector is satisfied. We solve the problem by two methods. The first involves formulating the problem as a (discrete-time) Markov decision process and using induction on the horizon length. The second is a sample-path approach using an interchange argument to establish optimality.The research of this author was supported by the National Science Foundation under Grant No. DDM-8719825. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.     

Excess pore water pressure due to ground surface erosion

The Laplace transform is applied to solve the groundwater flow equation with a boundary that is initially fixed but that starts to move at a constant rate after some fixed time. This problem arises in the study of pore water pressures due to erosional unloading where the aquifer lies underneath an unsaturated zone. We derive an analytic solution and examine the predicted pressure profiles and boundary fluxes. We calculate the negative pore water pressure in the aquifer induced by the initial erosion of the unsaturated zone and subsequent erosion of the aquifer.     

Large time asymptotics for a modified coagulation model

We study the large time asymptotics of a simplified two species model for particles (typically molecules or cells). The particles can be in two states: A “free” state where they simply move with a given velocity or an aggregated state where they do not move anymore. We show that depending only on the strength of the interaction between particles, either all of them eventually coagulate or some may escape.     

Generic super-exponential stability of elliptic equilibrium positions for symplectic vector fields

In this article, we consider linearly stable elliptic fixed points (equilibrium) for a symplectic vector field and prove generic results of super-exponential stability for nearby solutions. We will focus on the neighborhood of elliptic fixed points but the case of linearly stable isotropic reducible invariant tori in a Hamiltonian system should be similar. More specifically, Morbidelli and Giorgilli have proved a result of stability over superexponentially long times if one considers an analytic Lagrangian torus, invariant for an analytic Hamiltonian system, with a diophantine translation vector which admits a sign-definite torsion. Then, the solutions of the system move very little over times which are super-exponentially long with respect to the inverse of the distance to the invariant torus. The proof proceeds in two steps: first one constructs a high-order Birkhoff normal form, then one applies the Nekhoroshev theory. Bounemoura has shown that the second step of this construction remains valid if the Birkhoff normal form linked to the invariant torus or the elliptic fixed point belongs to a generic set among the formal series. This is not sufficient to prove this kind of super-exponential stability results in a general setting. We should also establish that the most strongly non resonant elliptic fixed point or invariant torus in a Hamiltonian system admits Birkhoff normal forms fitted for the application of the Nekhoroshev theory. Actually, the set introduced by Bounemoura is already very large but not big enough to ensure that a typical Birkhoff normal form falls into this class. We show here that this property is satisfied generically in the sense of the measure (prevalence) through infinite-dimensional probe spaces (that is, an infinite number of parameters chosen at random) with methods similar to those developed in a paper of Gorodetski, Kaloshin and Hunt in another setting.     

The fair allocation of common fixed cost or revenue using DEA concept

The common fixed cost or revenue distribution amongst decision making units (briefly, DMUs) in an equitable way is one of the problems that can be solved by data envelopment analysis (DEA) concept. The motivation of this paper is common fixed cost or revenue allocation based on following three principles: First, allocation must be directly proportional to the elements (inputs and outputs) that are directly proportional to imposed common fixed cost or to obtained common fixed revenue. Second, allocation must be inversely proportional to the elements that are inversely proportional to common fixed cost or revenue. Finally, the elements that have no effect on common fixed cost or revenue must have no effect on allocation as well.     

An inventory model where backordered demand ratio is exponentially decreasing with the waiting time

We analyze an inventory system with a mixture of backorders and lost sales, where the backordered demand rate is an exponential function of time the customers wait before receiving the item. Stockout costs (backorder cost and lost sales cost) include a fixed cost and a cost proportional to the length of the shortage period. A procedure for determining the optimal policy and the maximum inventory profit is presented. This work extends several inventory models of the existing literature.     

Impulsive perturbations of a three-trophic prey-dependent food chain system

The dynamics of an impulsively controlled three-trophic food chain system with general nonlinear functional responses for the intermediate consumer and the top predator are analyzed using the Floquet theory and comparison techniques. It is assumed that the impulsive controls act in a periodic fashion, the constant impulse (the biological control) and the proportional impulses (the chemical controls) acting with the same period, but not simultaneously. Sufficient conditions for the global stability of resource and intermediate consumer-free periodic solution and of the intermediate consumer-free periodic solution are established, the latter corresponding to the success of the integrated pest management strategy from which our food chain system arises. In this regard, it is seen that, theoretically speaking, the control strategy can be always made to succeed globally if proper pesticides are employed, while as far as the biological control is concerned, its global effectiveness can also be reached provided that the top predator is voracious enough or the (constant) number of top predators released each time is large enough or the release period is small enough. Some situations which lead to chaotic behavior of the system are also investigated by means of numerical simulations.     

Efficient Sequential Quadratic Programming Implementations for Equality-Constrained Discrete-Time Optimal Control

Efficient sequential quadratic programming (SQP) implementations are presented for equality-constrained, discrete-time, optimal control problems. The algorithm developed calculates the search direction for the equality-based variant of SQP and is applicable to problems with either fixed or free final time. Problem solutions are obtained by solving iteratively a series of constrained quadratic programs. The number of mathematical operations required for each iteration is proportional to the number of discrete times N. This is contrasted by conventional methods in which this number is proportional to N ³. The algorithm results in quadratic convergence of the iterates under the same conditions as those for SQP and simplifies to an existing dynamic programming approach when there are no constraints and the final time is fixed. A simple test problem and two application problems are presented. The application examples include a satellite dynamics problem and a set of brachistochrone problems involving viscous friction.     

On (<Emphasis Type="Italic">T,S</Emphasis><Subscript><Emphasis Type="Italic">i</Emphasis></Subscript>) Policy Inventory Model for Deteriorating Items with Time Proportional Demand

This paper considers the economic order-quantity model when shortages are allowed for the situation of fixed cycle time and increasing (or decreasing) levels of order quantities for the time proportional demand and in which items of inventory deteriorate at a constant rate. The results are supported with the help of an example. Sensitivity analysis is also discussed for the given model.     

Extinction and permanence of the predator–prey system with stocking of prey and harvesting of predator impulsively

In this paper, a predator–prey system with stocking of prey and harvesting of predator impulsively is studied. Here, the prey population is stocked with a constant quantity and the predator population is harvested at a rate proportional to the species itself at fixed moments. Under some conditions, the existence and global asymptotic stability of the boundary periodic solution are proved, which implies that the system will be extinct; and given some different restrictions, ultimate positive upper and lower bounds of all solutions are obtained, showing the system being permanent. At last, two examples are given to illustrate our results. Copyright © 2005 John Wiley & Sons, Ltd.     

Product damage and free sampling: a newsvendor model with passive and proactive self-consumption

A retailer sells a single product for a single period. During transportation and storage, some of these products are consumed by the retailer either (1) due to unavoidable damages (passive self-consumption), or (2) distributed for free to the customers (proactive self-consumption). This creates a mismatch between the amount purchased by the retailer and the amount available for sale. We study passive self-consumption with (i) fixed and (ii) proportional consumption, and proactive self-consumption with (iii) additive and (iv) multiplicative demand. Under proactive self-consumption, the retailer holds more inventory and receives a higher profit; the reverse is true under passive self-consumption. Yet, (i), (iii) and (iv) result in a higher order quantity and same fill rate compared to no self-consumption, (ii) may result in a higher or lower order quantity with a lower fill rate. When both types of self-consumption coexist, the optimal policy can be complicated. We characterize the optimal policy and show through numerical studies that the optimal policy can take at most three formats: sell to the market with positive proactive self-consumption, sell to the market with zero proactive self-consumption and do not sell to the market. Interestingly, the optimal order quantity is not smooth in the fraction of the proportional self-consumption. Further we find that when the market adoption rate is uncertain, the optimal strategy preserves a similar structure. The retailer benefits from expediting if the difference between the high and the low market adoption rates is high and the probability of a high market adoption rate is low.     

Cooperation among mobile individuals with payoff expectations in the spatial prisoner’s dilemma game

We propose a model to address the problem how the evolution of cooperation in a social system depends on the spatial motion and the payoff expectation. In the model, if the actual payoff of an individual is smaller than its payoff expectation, the individual will either move to a new site or simply reverse its current strategy. It turns out that migration of dissatisfied individuals with relatively low expectation level leads to the aggregation of cooperators and promotion of cooperation. Moreover, under appropriate parameters migration leads to some interesting spatiotemporal patterns which seems not to have been reported in previously studied spatial games. Furthermore, it also found that a population with constant expectation can better favor cooperative behavior than a population with adaptive aspiration.     

Optimal investment to minimize the probability of drawdown

We determine the optimal investment strategy in a Black–Scholes financial market to minimize the so-called probability of drawdown, namely, the probability that the value of an investment portfolio reaches some fixed proportion of its maximum value to date. We assume that the portfolio is subject to a payout that is a deterministic function of its value, as might be the case for an endowment fund paying at a specified rate, for example, at a constant rate or at a rate that is proportional to the fund’s value.