A two-machine flowshop problem with processing time-dependent buffer constraints—An application in multimedia presentations

To have a quality multimedia presentation through networks, its presentation lag needs to be controlled. One way to reduce the lag is to prefetch the media objects before their due dates. This paper explores techniques for optimizing the object sequence in a prefetch-enabled TV-like presentation. An optimal solution is the one with which the presentation lag is minimized. We formulate the problem into a two-machine flowshop scheduling problem with a single chain precedence constraint and a player-side buffer constraint. The player-side buffer is “processing time-dependent” and distinguished from the conventional item-based intermediate buffer constraints discussed in previous flowshop studies. We prove the problem to be strongly NP-hard. A branch and bound algorithm equipped with four lower bounds and an NEH-based upper bound is developed. The simulation results show that the average gaps between the overall lower bounds and the NEH-based upper bound are less than 3% for problems with a large buffer size, and less than 13% for problems with a small buffer size and high density of precedence constraints. For applications where the media objects are delivered through extremely busy servers with which only very restricted CPU resources can be allocated for computation, the CDS-based algorithm provides better sequences than the NEH-based algorithm.     

Consistency constraints and 3D building reconstruction

Virtual architectural (indoor) scenes are often modeled in 3D for various types of simulation systems. For instance, some authors propose methods dedicated to lighting, heat transfer, acoustic or radio-wave propagation simulations. These methods rely in most cases on a volumetric representation of the environment, with adjacency and incidence relationships. Unfortunately, many buildings data are only given by 2D plans and the 3D needs varies from one application to another. To face these problems, we propose a formal representation of consistency constraints dedicated to building interiors and associated with a topological model. We show that such a representation can be used for: (i) reconstructing 3D models from 2D architectural plans (ii) detecting automatically geometrical, topological and semantical inconsistencies (iii) designing automatic and semi-automatic operations to correct and enrich a 2D plan. All our constraints are homogeneously defined in 2D and 3D, implemented with generalized maps and used in modeling operations. We explain how this model can be successfully used for lighting and radio-wave propagation simulations.     

Uniqueness of the Perfect Fusion Grid on ℤ d

Region merging methods consist of improving an initial segmentation by merging some pairs of neighboring regions. In a graph, merging two regions, separated by a set of vertices, is not straightforward. The perfect fusion graphs defined in J. Cousty et al. (J. Math. Imaging Vis. 30:(1):87–104, 2008) verify all the basic properties required by region merging algorithms as used in image segmentation. Unfortunately, the graphs which are the most frequently used in image analysis (namely, those induced by the direct and the indirect adjacency relations) are not perfect fusion graphs. The perfect fusion grid, introduced in the above mentioned reference, is an adjacency relation on ℤ ^d which can be used in image analysis, which indeed induces perfect fusion graphs and which is “between” the graphs induced by the direct and the indirect adjacencies. One of the main results of this paper is that the perfect fusion grid is the only such graph whatever the dimension d.

A revision of recent approaches for two-dimensional strip-packing problems

In this paper, we present a review of the recent approaches proposed in the literature for strip-packing problems. Many of them have been concurrently published, given some similar results for the same set of benchmarks. Due to the quantity of published papers, it is difficult to ascertain the level of current research in this area.     

A method for a robust optimization of joint product and supply chain design

This paper proposes a method for finding a robust solution to the problem of joint product family and supply chain design. Optimizing product design and the supply chain network at the same time brings substantial benefits. However, this approach involves decisions that can generate uncertainties in the long term. The challenge is to come up with a method that can adapt to most possible environments without straying too far from the optimal solution. Our approach is based on the generation of scenarios that correspond to combinations of uncertain parameters within the model. The performance of designs resulting from these scenario optimizations are compared to the performance of each of the other design scenarios, based on their probability of occurrence. The proposed methodology will allow practitioners to choose a suitable design, from the most profitable to the most reliable.     

Self-stabilization with r-operators

This paper describes a parameterized distributed algorithm applicable to any directed graph topology. The function parameter of our algorithm is instantiated to produce distributed algorithms for both fundamental and high level applications, such as shortest path calculus and depth-first-search tree construction. Due to fault resilience properties of our algorithm, the resulting protocols are self-stabilizing at no additional cost. Self-stabilizing protocols can resist transient failures and guarantee system recovery in a finite time. Since the condition on the function parameter (being a strictly idempotent r-operator) permits a broad range of applications to be implemented, the solution presented in our paper can be useful for a large class of distributed systems. Received: August 1999 / Accepted: January 2001     

Structural and electronic properties of zirconia phases: A FP-LAPW investigations

The structural and electronic properties of ZrO₂ polymorphs were investigated using density functional theory (DFT). The Kohn–Sham equations were solved by applying the full-potential linearized augmented plane wave (FP-LAPW) method. We used the generalized gradient approximation (GGA) in the Perdew–Wang formalism to the exchange and correlation energy functional. The ground state properties such as lattice parameter, transition pressures, bulk modulus and its pressure derivative as well as the structural phase stability were calculated. The results were compared with previous calculations and experimental data when available. The FP-LAPW method correctly orders the zero temperature energies of all zirconia polymorphs. We have also studied the effect of distortion from the cubic to the tetragonal structure on the basis of charge density calculations. On the other hand, band structure and density of states (DOS), which allow us to discuss the features of orbital mixing, are also given. Our results suggest that the cotunnite structure should be better than the other zirconia phases as gate dielectric material.     

BiNem® manufacturing process for mass production

Abstract— As the need for high‐resolution ultra‐low‐power bistable displays grows, it is important to rapidly implement the mass‐production manufacturing of BiNem® LCDs. The cost‐effective approach for BiNem® manufacturing is based on using STN manufacturing process technologies since BiNem® and STN displays have a similar internal structure. The key differences between BiNem® and STN displays from a manufacturing point of view will be discussed. We show that industrial STN manufacturing equipment can be used to produce BiNem® LCDs at competitive costs. Reflective e‐book display modules with VGA resolution are produced in the pilot‐production series.