Steady-State Analysis and Scheduling of Cyclic Job Shops with Overtaking

A cyclic shop is a production system that repeatedly produces identical sets of parts of multiple types, called minimal part sets (MPSs), in the same loading and processing sequence. A different part type may have a different machine visit sequence. We consider a version of cyclic job shop where some operations of an MPS instance are processed prior to some operations of the previous MPS instances. We call such a shop an overtaking cyclic job shop (OCJS). The overtaking degree can be specified by how many MPS instances the operations of an MPS instance can overtake. More overtaking results in more work-in-progress, but reduces the cycle time, in general. We prove that for a given processing sequence of the operations at each machine, under some conditions, an OCJS has a stable earliest starting schedule such that each operation starts as soon as its preceding operations are completed, the schedule repeats an identical timing pattern for each MPS instance, and the cycle time is kept to be minimal. To do these, we propose a specialized approach to analyzing steady states for an event graph model of an OCJS that has a cyclic structure, which can keep the MPS-based scheduling concept. Based on the steady-state results, we develop a mixed integer programming model for finding a processing sequence of the operations at each machine and the overtaking degrees, if necessary, that minimize the cycle time.     

The role of additive neurogenesis and synaptic plasticity in a hippocampal memory model with grid-cell like input

Recently, we presented a study of adult neurogenesis in a simplified hippocampal memory model. The network was required to encode and decode memory patterns despite changing input statistics. We showed that additive neurogenesis was a more effective adaptation strategy compared to neuronal turnover and conventional synaptic plasticity as it allowed the network to respond to changes in the input statistics while preserving representations of earlier environments. Here we extend our model to include realistic, spatially driven input firing patterns in the form of grid cells in the entorhinal cortex. We compare network performance across a sequence of spatial environments using three distinct adaptation strategies: conventional synaptic plasticity, where the network is of fixed size but the connectivity is plastic; neuronal turnover, where the network is of fixed size but units in the network may die and be replaced; and additive neurogenesis, where the network starts out with fewer initial units but grows over time. We confirm that additive neurogenesis is a superior adaptation strategy when using realistic, spatially structured input patterns. We then show that a more biologically plausible neurogenesis rule that incorporates cell death and enhanced plasticity of new granule cells has an overall performance significantly better than any one of the three individual strategies operating alone. This adaptation rule can be tailored to maximise performance of the network when operating as either a short- or long-term memory store. We also examine the time course of adult neurogenesis over the lifetime of an animal raised under different hypothetical rearing conditions. These growth profiles have several distinct features that form a theoretical prediction that could be tested experimentally. Finally, we show that place cells can emerge and refine in a realistic manner in our model as a direct result of the sparsification performed by the dentate gyrus layer.     

Constructing Level-2 Phylogenetic Networks from Triplets

Jansson and Sung showed that, given a dense set of input triplets T (representing hypotheses about the local evolutionary relationships of triplets of taxa), it is possible to determine in polynomial time whether there exists a level-1 network consistent with T, and if so, to construct such a network [24]. Here, we extend this work by showing that this problem is even polynomial time solvable for the construction of level-2 networks. This shows that, assuming density, it is tractable to construct plausible evolutionary histories from input triplets even when such histories are heavily nontree-like. This further strengthens the case for the use of triplet-based methods in the construction of phylogenetic networks. We also implemented the algorithm and applied it to yeast data.     

Design and Performance Analysis of Divisible Load Scheduling Strategies on Arbitrary Graphs

In this paper, we consider the problem of scheduling divisible loads on arbitrary graphs with the objective to minimize the total processing time of the entire load submitted for processing. We consider an arbitrary graph network comprising heterogeneous processors interconnected via heterogeneous links in an arbitrary fashion. The divisible load is assumed to originate at any processor in the network. We transform the problem into a multi-level unbalanced tree network and schedule the divisible load. We design systematic procedures to identify and eliminate any redundant processor–link pairs (those pairs whose consideration in scheduling will penalize the performance) and derive an optimal tree structure to obtain an optimal processing time, for a fixed sequence of load distribution. Since the algorithm thrives to determine an equivalent number of processors (resources) that can be used for processing the entire load, we refer to this approach as resource-aware optimal load distribution (RAOLD) algorithm. We extend our study by applying the optimal sequencing theorem proposed for single-level tree networks in the literature for multi-level tree for obtaining an optimal solution. We evaluate the performance for a wide range of arbitrary graphs with varying connectivity probabilities and processor densities. We also study the effect of network scalability and connectivity. We demonstrate the time performance when the point of load origination differs in the network and highlight certain key features that may be useful for algorithm and/or network system designers. We evaluate the time performance with rigorous simulation experiments under different system parameters for the ease of a complete understanding.     

Effect of secretions from female genital tract on some vitality indexes of spermatozoa]

The survival time and speed of movement of washed bull spermatozoa suspended in Peterson buffer (1:10) and secretions from various parts of the genital tracts of cows (Cervix, horns, oviductus) collected in different stages of the estrous cycle (early luteal, full luteal, follicular) were determined. Survival time of the spermatozoa was determined at 46.5 degrees under a microscopic using the Beck and Salisbury method. The speed of movement was measured at 37 degrees in a Burker hemocytometer. The survival time and speed of movement of the spermatozoa were stimulated by secretions in the follicular and early luteal stages. Secretions during the full luteal stage depressed these figures. Secretions taken from different parts of the genital tract did not show any significant differences in stimulatory action.     

Role of Relaxation Time Scale in Noisy Signal Transduction

Intra-cellular fluctuations, mainly triggered by gene expression, are an inevitable phenomenon observed in living cells. It influences generation of phenotypic diversity in genetically identical cells. Such variation of cellular components is beneficial in some contexts but detrimental in others. To quantify the fluctuations in a gene product, we undertake an analytical scheme for studying few naturally abundant linear as well as branched chain network motifs. We solve the Langevin equations associated with each motif under the purview of linear noise approximation and derive the expressions for Fano factor and mutual information in close analytical form. Both quantifiable expressions exclusively depend on the relaxation time (decay rate constant) and steady state population of the network components. We investigate the effect of relaxation time constraints on Fano factor and mutual information to indentify a time scale domain where a network can recognize the fluctuations associated with the input signal more reliably. We also show how input population affects both quantities. We extend our calculation to long chain linear motif and show that with increasing chain length, the Fano factor value increases but the mutual information processing capability decreases. In this type of motif, the intermediate components act as a noise filter that tune up input fluctuations and maintain optimum fluctuations in the output. For branched chain motifs, both quantities vary within a large scale due to their network architecture and facilitate survival of living system in diverse environmental conditions.     

Stable Earliest Starting Schedules for Cyclic Job Shops: A Linear System Approach

We consider a cyclic job shop where an identical mixture of parts of different types, called a minimal part set (MPS), is produced repetitively in the same processing order. The precedence relationships among events (start of operation) are represented by a directed graph that has a recurrent structure. Each operation starts as soon as all its preceding operations are complete (called earliest starting). There is a class of desirable schedules that has the minimum cycle time and an identical schedule pattern for every MPS. By using linear system theory on minimax algebra, we characterize the set of all possible such schedules. We develop an efficient algorithm to find one among such schedules that minimizes a performance measure related to work-in-progress inventory. We also discuss an application to a flexible manufacturing system.     

Sequencing of parts and robot moves in a robotic cell

In this paper, we deal with the problem of sequencing parts and robot moves in a robotic cell where the robot is used to feed machines in the cell. The robotic cell, which produces a set of parts of the same or different types, is a flow-line manufacturing system. Our objective is to maximize the long-run average throughput of the system subject to the constraint that the parts are to be produced in proportion of their demand. The cycle time formulas are developed and analyzed for this purpose for cells producing a single part type using two or three machines. A state space approach is used to address the problem. Both necessary and sufficient conditions are obtained for various cycles to be optimal. Finally, in the case of many part types, the problem of scheduling parts for a specific sequence of robot moves in a two machine cell is formulated as a solvable case of the traveling salesman problem.     

Optimal scheduling for cell synchronization by cycle-phase-specific blockers

On the basis of a general kinetic model of the cell cycle, the time schedule of administration of a blocking agent for cell synchronization was optimized. As blockers we considered agents that slow down the rate of transit through the short phase of the cycle. The Pontryagin maximum principle is used. Only stationary populations (the model of the steady state normal tissues) were considered. For such populations the exact form of optimal protocols may be simplified, without any significant loss in effectiveness, to the periodic alternation of suitably chosen intervals of maximum treatment and intervals of rest. The proper lengths of these intervals were obtained from the optimal protocols; their values for various parameters characterizing the cell cycle and the blocker action are presented. With the periodic form of protocols the synchronous movement of cells through any number of cycles may be obtained. The utilization of periodic protocols of synchronization in multiple cancer chemotherapy is discussed.     

Level Scheduling for batched JIT supply

A mixed-model assembly line requires the solution of a short-term sequencing problem which decides on the succession of different models launched down the line. A famous solution approach stemming from the Toyota Production System is the so-called Level Scheduling, which aims at distributing the part consumption induced by the model sequence evenly over time. Traditional Level Scheduling seeks to closely approximate target demand rates at every production cycle, however, such a strict leveling is only required if parts are directly pulled from a connected feeder line. In real-world assembly lines, parts are predominately delivered in (small) batches at certain points in time. In such a situation, a Just-in-Time supply is already facilitated whenever the cumulative consumption is leveled in accordance with each part’s delivery schedule, while the exact consumption pattern between two delivery points seems irrelevant. The paper on hand provides new Level Scheduling models, proves complexity, presents exact and heuristic solution procedures and shows inferiority of traditional Level Scheduling for such a batched JIT-supply of parts.     

A scheduling model for multirobot assembly cells

We propose a mixed 0–1 linear programming model for repetitive scheduling of multirobot assembly and machining cells. The approach adopted is monolithic as opposed to hierarchical to avoid system suboptimization. The model permits any number of alternative ways (or modes) to perform each operation. A mode of an operation is determined by the required resources (facilities) and the duration of their use. The model incorporates facility changeover times. Robot collisions are avoided. Several objective functions are formulated to support different purposes. The scheduling problem of a multirobot assembly cell is formulated and solved by using commercially available mathematical programming software. Solutions under four different objective functions are reported. Acknowledging the complexity and considerable size of the formulation required, we prescribe and illustrate specific methods to achieve size reduction. Finally, for successful use of our model, an information processing schema is offered as a general guidance to help data management needed by the model.     

Sequencing of Parts in Robotic Cells

This paper considers scheduling problems in robotic cells that produce a set of part types on several machines served by one robot. We study the problem of sequencing parts of different types in a cell to minimize the production cycle time when the sequence of the robot moves is given. This problem is NP-hard for most of the one-unit robot move cycles in a robotic cell with more than two machines and producing more than two part types. We first give a mathematical formulation to the problem, and then propose a branch-and-bound algorithm to solve it. The bounding scheme of this algorithm is based on relaxing, for all of the machines except two, the constraints that a machine should be occupied by a part for a period at least as long as the processing time of the part. The lower bound obtained in this way is tight. This relaxation allows us to overcome the complexity of the problem. The lower bound can be computed using the algorithm of Gilmore and Gomory. Computational experiments on part sequencing problems in three-machine robotic cells are given.     

A model for a network of phosphorylation-dephosphorylation cycles displaying the dynamics of dominoes and clocks

We consider a model for a network of phosphorylation-dephosphorylation cycles coupled through forward and backward regulatory interactions, such that a protein phosphorylated in a given cycle activates the phosphorylation of a protein by a kinase in the next cycle as well as the dephosphorylation of a protein by a phosphatase in a preceding cycle. The network is cyclically organized in such a way that the protein phosphorylated in the last cycle activates the kinase in the first cycle. We study the dynamics of the network in the presence of both forward and backward coupling, in conditions where a threshold exists in each cycle in the amount of protein phosphorylated as a function of the ratio of kinase to phosphatase maximum rates. We show that this system can display sustained (limit-cycle) oscillations in which each cycle in the pathway is successively turned on and off, in a sequence resembling the fall of a series of dominoes. The model thus provides an example of a biochemical system displaying the dynamics of dominoes and clocks (Murray & Kirschner, 1989). It also shows that a continuum of clock waveforms exists of which the fall of dominoes represents a limit. When the cycles in the network are linked through only forward (positive) coupling, bistability is observed, while in the presence of only backward (negative) coupling, the system can display multistability or oscillations, depending on the number of cycles in the network. Inhibition or activation of any kinase or phosphatase in the network immediately stops the oscillations by bringing the system into a stable steady state; oscillations resume when the initial value of the kinase or phosphatase rate is restored. The progression of the system on the limit cycle can thus be temporarily halted as long as an inhibitor is present, much as when a domino is held in place. These results suggest that the eukaryotic cell cycle, governed by a network of phosphorylation-dephosphorylation reactions in which the negative control of cyclin-dependent kinases plays a prominent role, behaves as a limit-cycle oscillator impeded in the presence of inhibitors. We contrast the case where the sequence of domino-like transitions constitutes the clock with the case where the sequence of transitions is passively coupled to a biochemical oscillator operating as an independent clock.     

Interfacial spin trapping in model membrane systems

The nature of mitochondrial DNA replication during the synchronous cell cycle in the yeast, $\text{Saccharomyces}\text{cerevisiae}$ has been investigated by examining the rate of labeled DNA precursor incorporation into specific segments of the mitochondrial genome at defined points during synchronous growth. The movement of label uptake from one area of the DNA to another at different times during the synchronous cell cycle indicates mitochondrial DNA replication to be a synchronous process during this time with most or all molecules at the same point in replication at any given time during the cell cycle.     

Life Cycle Analysis of Mammalian Cells: II. Cells from the Chinese Hamster Ovary Grown in Suspension Culture

A method for life cycle analysis in mammalian cells which utilizes the collection function has been applied to the Chinese hamster ovary grown in suspension. The following durations were found for the various parts of the life cycle: S, 4.13 hours; G1, 4.71 hours; G2, 2.81 hours; mitosis, 0.81 hours. The cell has a total generation time of 12.4 hours as opposed to 20.1 hours for the S3 HeLa cell. However, the relative lengths of each phase of the life cycle are identical within experimental uncertainty in the two cells.     

Neural action fields for optic flow based navigation: a simulation study of the fly lobula plate network

Optic flow based navigation is a fundamental way of visual course control described in many different species including man. In the fly, an essential part of optic flow analysis is performed in the lobula plate, a retinotopic map of motion in the environment. There, the so-called lobula plate tangential cells possess large receptive fields with different preferred directions in different parts of the visual field. Previous studies demonstrated an extensive connectivity between different tangential cells, providing, in principle, the structural basis for their large and complex receptive fields. We present a network simulation of the tangential cells, comprising most of the neurons studied so far (22 on each hemisphere) with all the known connectivity between them. On their dendrite, model neurons receive input from a retinotopic array of Reichardt-type motion detectors. Model neurons exhibit receptive fields much like their natural counterparts, demonstrating that the connectivity between the lobula plate tangential cells indeed can account for their complex receptive field structure. We describe the tuning of a model neuron to particular types of ego-motion (rotation as well as translation around/along a given body axis) by its 'action field'. As we show for model neurons of the vertical system (VS-cells), each of them displays a different type of action field, i.e., responds maximally when the fly is rotating around a particular body axis. However, the tuning width of the rotational action fields is relatively broad, comparable to the one with dendritic input only. The additional intra-lobula-plate connectivity mainly reduces their translational action field amplitude, i.e., their sensitivity to translational movements along any body axis of the fly.     

On the genealogy of a population of biparental individuals

If one goes backward in time, the number of ancestors of an individual doubles at each generation. This exponential growth very quickly exceeds the population size, when this size is finite. As a consequence, the ancestors of a given individual cannot be all different and most remote ancestors are repeated many times in any genealogical tree. The statistical properties of these repetitions in genealogical trees of individuals for a panmictic closed population of constant size N can be calculated. We show that the distribution of the repetitions of ancestors reaches a stationary shape after a small number G(c) approximately log N of generations in the past, that only about 80% of the ancestral population belongs to the tree (due to coalescence of branches), and that two trees for individuals in the same population become identical after G(c)generations have elapsed. Our analysis is easy to extend to the case of exponentially growing population.