A mathematical model for assembly line balancing model to consider disordering sequence of workstations

Purpose – A binary integer programming model for the simple assembly line balancing problem (SALBP), which is well known as SALBP-1, was formulated more than 30 years ago. Since then, a number of researchers have extended the model for the variants of assembly line balancing problem.The model is still prevalent nowadays mainly because of the lower and upper bounds on task assignment. These properties avoid significant increase of decision variables. The purpose of this paper is to use an example to show that the model may lead to a confusing solution. Design/methodology/approach – The paper provides a remedial constraint set for the model to rectify the disordered sequence problem. Findings – The paper presents proof that the assembly line balancing model formulated by Patterson and Albracht may lead to a confusing solution. Originality/value – No one previously has found that the commonly used model is incorrect.

10Gbit/s dispersion managed soliton transmission over 16,500km in standard fibre by reduction of soliton interactions

We show experimentally and numerically that in high-speed strongly dispersion-managed standard fiber soliton systems nonlinear interactions limit the propagation distance. We present results that show that the effect of these interactions can be significantly reduced by appropriate location of the amplifier within the dispersion map. Using this technique, we have been able to extend the propagation distance of 10-Gbit/s 231–1pseudorandom binary sequence soliton data to 16, 500km over standard fiber by use of dispersion compensation. To our knowledge this distance is the farthest transmission over standard fiber without active control ever reported, and it was achieved with the amplifier placed after the dispersion-compensating fiber in a recirculating loop.

10Gbit/s dispersion managed soliton transmission over 16,500km in standard fibre by reduction of soliton interactions

We show experimentally and numerically that in high-speed strongly dispersion-managed standard fiber soliton systems nonlinear interactions limit the propagation distance. We present results that show that the effect of these interactions can be significantly reduced by appropriate location of the amplifier within the dispersion map. Using this technique, we have been able to extend the propagation distance of 10-Gbit/s 231–1pseudorandom binary sequence soliton data to 16, 500km over standard fiber by use of dispersion compensation. To our knowledge this distance is the farthest transmission over standard fiber without active control ever reported, and it was achieved with the amplifier placed after the dispersion-compensating fiber in a recirculating loop.

Finite-connectivity spin-glass phase diagrams and low-density parity check codes

We obtain phase diagrams of regular and irregular finite-connectivity spin glasses. Contact is first established between properties of the phase diagram and the performance of low-density parity check (LDPC) codes within the replica symmetric (RS) ansatz. We then study the location of the dynamical and critical transition points of these systems within the one step replica symmetry breaking theory (RSB), extending similar calculations that have been performed in the past for the Bethe spin-glass problem. We observe that the location of the dynamical transition line does change within the RSB theory, in comparison with the results obtained in the RS case. For LDPC decoding of messages transmitted over the binary erasure channel we find, at zero temperature and rate R=14, an RS critical transition point at pc 0.67 while the critical RSB transition point is located at pc 0.7450±0.0050, to be compared with the corresponding Shannon bound 1-R. For the binary symmetric channel we show that the low temperature reentrant behavior of the dynamical transition line, observed within the RS ansatz, changes its location when the RSB ansatz is employed; the dynamical transition point occurs at higher values of the channel noise. Possible practical implications to improve the performance of the state-of-the-art error correcting codes are discussed. © 2006 The American Physical Society.

The dynamics of a genetic algorithm for a simple learning problem

A formalism for describing the dynamics of Genetic Algorithms (GAs) using method s from statistical mechanics is applied to the problem of generalization in a perceptron with binary weights. The dynamics are solved for the case where a new batch of training patterns is presented to each population member each generation, which considerably simplifies the calculation. The theory is shown to agree closely to simulations of a real GA averaged over many runs, accurately predicting the mean best solution found. For weak selection and large problem size the difference equations describing the dynamics can be expressed analytically and we find that the effects of noise due to the finite size of each training batch can be removed by increasing the population size appropriately. If this population resizing is used, one can deduce the most computationally efficient size of training batch each generation. For independent patterns this choice also gives the minimum total number of training patterns used. Although using independent patterns is a very inefficient use of training patterns in general, this work may also prove useful for determining the optimum batch size in the case where patterns are recycled.

How effective is low vision service provision? A systematic review

Visual impairment is a large and growing socioeconomic problem. Good evidence on rehabilitation outcomes is required to guide service development and improve the lives of people with sight loss. Of the 478 potentially relevant articles identified, only 58 studies met our liberal inclusion criteria, and of these only 7 were randomized controlled trials. Although the literature is sufficient to confirm that rehabilitation services result in improved clinical and functional ability outcomes, the effects on mood, vision-related quality of life (QoL) and health-related QoL are less clear. There are some good data on the performance of particular types of intervention, but almost no useful data about outcomes in children, those of working age, and other groups. There were no reports on cost effectiveness. Overall, the number of well-designed and adequately reported studies is pitifully small; visual rehabilitation research needs higher quality research. We highlight study design and reporting considerations and suggest a future research agenda.

Statistical mechanics of low-density parity check error-correcting codes over Galois fields

A variation of low-density parity check (LDPC) error-correcting codes defined over Galois fields (GF(q)) is investigated using statistical physics. A code of this type is characterised by a sparse random parity check matrix composed of C non-zero elements per column. We examine the dependence of the code performance on the value of q, for finite and infinite C values, both in terms of the thermodynamical transition point and the practical decoding phase characterised by the existence of a unique (ferromagnetic) solution. We find different q-dependence in the cases of C = 2 and C ≥ 3; the analytical solutions are in agreement with simulation results, providing a quantitative measure to the improvement in performance obtained using non-binary alphabets.

Statistical physics of low density parity check error correcting codes

We study the performance of Low Density Parity Check (LDPC) error-correcting codes using the methods of statistical physics. LDPC codes are based on the generation of codewords using Boolean sums of the original message bits by employing two randomly-constructed sparse matrices. These codes can be mapped onto Ising spin models and studied using common methods of statistical physics. We examine various regular constructions and obtain insight into their theoretical and practical limitations. We also briefly report on results obtained for irregular code constructions, for codes with non-binary alphabet, and on how a finite system size effects the error probability.

Low density parity check codes: a statistical physics perspective

The modem digital communication systems are made transmission reliable by employing error correction technique for the redundancies. Codes in the low-density parity-check work along the principles of Hamming code, and the parity-check matrix is very sparse, and multiple errors can be corrected. The sparseness of the matrix allows for the decoding process to be carried out by probability propagation methods similar to those employed in Turbo codes. The relation between spin systems in statistical physics and digital error correcting codes is based on the existence of a simple isomorphism between the additive Boolean group and the multiplicative binary group. Shannon proved general results on the natural limits of compression and error-correction by setting up the framework known as information theory. Error-correction codes are based on mapping the original space of words onto a higher dimensional space in such a way that the typical distance between encoded words increases.

Typical performance of low-density parity-check codes over general symmetric channels

Typical performance of low-density parity-check (LDPC) codes over a general binary-input output-symmetric memoryless channel is investigated using methods of statistical mechanics. The binary-input additive-white-Gaussian-noise channel and the binary-input Laplace channel are considered as specific channel noise models.

Average error exponent in Gallager low-density parity-check codes

We present a theoretical method for a direct evaluation of the average error exponent in Gallager error-correcting codes using methods of statistical physics. Results for the binary symmetric channel(BSC)are presented for codes of both finite and infinite connectivity.

Average and reliability error exponents in low-density parity-check codes

We present a theoretical method for a direct evaluation of the average and reliability error exponents in low-density parity-check error-correcting codes using methods of statistical physics. Results for the binary symmetric channel are presented for codes of both finite and infinite connectivity.

Forced retroevolution of an RNA bacteriophage

The operator hairpin ahead of the replicase gene in RNA bacteriophage MS2 contains overlapping signals for binding the coat protein and ribosomes. Coat protein binding inhibits further translation of the gene and forms the first step in capsid formation. The hairpin sequence was partially randomized to assess the importance of this structure element for the bacteriophage and to monitor alternative solutions that would evolve on the passaging of mutant phages. The evolutionary reconstruction of the operator failed in the majority of mutants. Instead, a poor imitation developed containing only some of the recognition signals for the coat protein. Three mutants were of particular interest in that they contained double nonsense codons in the lysis reading frame that runs through the operator hairpin. The simultaneous reversion of two stop codons into sense codons has a very low probability of occurring. Therefore the phage solved the problem by deleting the nonsense signals and, in fact, the complete operator, except for the initiation codon of the replicase gene. Several revertants were isolated with activities ranging from 1% to 20% of wild type. The operator, long thought to be a critical regulator, now appears to be a dispensable element. In addition, the results indicate how RNA viruses can be forced to step back to an attenuated form.

An integrated scheduling problem of PCB components on sequential pick-and-place machines:mathematical models and heuristic solutions

This paper formulates several mathematical models for determining the optimal sequence of component placements and assignment of component types to feeders simultaneously or the integrated scheduling problem for a type of surface mount technology placement machines, called the sequential pick-andplace (PAP) machine. A PAP machine has multiple stationary feeders storing components, a stationary working table holding a printed circuit board (PCB), and a movable placement head to pick up components from feeders and place them to a board. The objective of integrated problem is to minimize the total distance traveled by the placement head. Two integer nonlinear programming models are formulated first. Then, each of them is equivalently converted into an integer linear type. The models for the integrated problem are verified by two commercial packages. In addition, a hybrid genetic algorithm previously developed by the authors is adopted to solve the models. The algorithm not only generates the optimal solutions quickly for small-sized problems, but also outperforms the genetic algorithms developed by other researchers in terms of total traveling distance.

A genetic algorithm approach to optimising component placement and retrieval sequence for chip shooter machines

A chip shooter machine in printed circuit board (PCB) assembly has three movable mechanisms: an X-Y table carrying a PCB, a feeder carrier with several feeders holding components and a rotary turret with multiple assembly heads to pick up and place components. In order to get the minimal placement or assembly time for a PCB on the machine, all the components on the board should be placed in a perfect sequence, and the components should be set up on a right feeder, or feeders since two feeders can hold the same type of components, and additionally, the assembly head should retrieve or pick up a component from a right feeder. The entire problem is very complicated, and this paper presents a genetic algorithm approach to tackle it.