A parallel algorithm for constrained two-staged two-dimensional cutting problems

In this paper, we solve the two-staged two-dimensional cutting problem using a parallel algorithm. The proposed approach combines two main features: beam search (BS) and strip generation solution procedures (SGSP). BS employs a truncated tree-search, where a selected subset of generated nodes are retuned for further search. SGSP, a constructive procedure, combines a (sub)set of strips for providing both partial lower and complementary upper bounds. The algorithm explores in parallel a subset of selected nodes following the master-slave paradigm. The master processor serves to guide the search-resolution and each slave processor develops its proper way, trying a global convergence. The aim of such an approach is to show how the parallelism is able to efficiently solve large-scale instances, by providing new solutions within a consistently reduced runtime. Extensive computational testing on instances, taken from the literature, shows the effectiveness of the proposed approach.     

Avoiding the world model trap: An acting robot does not need to be so smart!

We propose several examples of robotics applications where interactions with the environment play an important role, and where no modelization of the robot or of the world is needed. We argue that, in general, this helps to simplify the complexity of the control system, and illustrate this claim through several examples. We propose different neural networks which allow clustering of scattered objects by several robots, learning of obstacle avoidance and learning of target retrieval.     

Submillimeter features on injected acrylonitrile butadiene styrene parts: Visualization of the flow and numerical simulation

Numerical simulation of classical dimension parts with micrometric textures on their surface is still difficult to master. The limit condition of the calculations, and in particular, the implemented values, characteristics of the polymer and thermal exchanges (polymer/mold) strongly impact the results. Starting from a model with a 370 μm wide rib, by means of a numerical simulation, a study was done on the evolution of the material flow front velocities and the flow lengths in both the macroscopic part and the microgroove. This innovative visualization mold design was used to determine the velocities from an experimental perspective and to discuss the calculation conditions. On the one hand, there are significant differences regarding the choice of the no flow temperature (~ 40 K) used in the calculation code, the analytical heat transfer equation as well as the experimental results. On the other hand, according to the no flow temperature, it may be necessary to consider, during the filling phase, a perfect mold/polymer thermal contact in the groove. Depending in particular on the injection velocity and the geometry of the micro textures, a characteristic time can be determined which defines an optimal operating point for the topographic texture of the part.     

Tracking Fronts in One and Two-phase Incompressible Flows Using an Adaptive Mesh Refinement Approach

Numerical computation is an essential tool for describing multi-phase and multi-scale flows accurately. One possibility consists in using very fine monogrids to obtain accurate solutions. However, this approach is very costly in time and memory size. As an alternative, an Adaptive Mesh Refinement method (AMR) has been developed in order to follow either interfaces in two-phase flows or concentration of a pollutant in one-phase flows. This method has also been optimized to reduce time and memory costs. Several 2D cases have been studied to validate and show the efficiency of the method.     

An iterative procedure for lot streaming in job-shop scheduling

The issue in Lot Streaming is to split lots into sublots in order to improve the makespan (or some other criterion). We present a model and an iterative procedure in a general job-shop environment. In a first step, optimal sublot-sizes are computed given a sequence of sublots on the machines. In a second step, a better sequence is computed by solving a standard job-shop scheduling problem with fixed sublot-sizes. Some computational results on a sample (including the famous 10-10) are reported. In case of no set-up, in few iterations, the makespan approaches a lower bound with few sublots.     

Four different approaches for the measurement of IC surface temperature: application to thermal testing

Silicon die surface temperature can be used to monitor the health state of digital and analogue integrated circuits (IC). In the present paper, four different sensing techniques: scanning thermal microscope, laser reflectometer, laser interferometer and electronic built-in differential temperature sensors are used to measure the temperature at the surface of the same IC containing heat sources (hot spots) that behave as faulty digital gates. The goal of the paper is to describe the techniques as well as to present the performances of these sensing methods for the detection and localisation of hot spots in an IC.     

Improved Approximation Results for the Minimum Energy Broadcasting Problem

In this paper we present new results on the performance of the Minimum Spanning Tree heuristic for the Minimum Energy Broadcast Routing (MEBR) problem. We first prove that, for any number of dimensions d≥2, the approximation ratio of the heuristic does not increase when the power attenuation coefficient α, that is the exponent to which the coverage distance must be raised to give the emission power, grows. Moreover, we show that, for any fixed instance, as a limit for α going to infinity, the ratio tends to the lower bound of Clementi et al. (Proceedings of the 18th annual symposium on theoretical aspects of computer science (STACS), pp. 121–131, 2001), Wan et al. (Wirel. Netw. 8(6):607–617, 2002) given by the d-dimensional kissing number, thus closing the existing gap between the upper and the lower bound. We then introduce a new analysis allowing to establish a 7.45-approximation ratio for the 2-dimensional case, thus significantly decreasing the previously known 12 upper bound (Wan et al. in Wirel. Netw. 8(6):607–617, 2002) (actually corrected to 12.15 in Klasing et al. (Proceedings of the 3rd IFIP-TC6 international networking conference, pp. 866–877, 2004)). Finally, we extend our analysis to any number of dimensions d≥2 and any α≥d, obtaining a general approximation ratio of 3 ^d −1, again independent of α. The improvements of the approximation ratios are specifically significant in comparison with the lower bounds given by the kissing numbers, as these grow at least exponentially with respect to d. The research was partially funded by the European project COST Action 293, “Graphs and Algorithms in Communication Networks” (GRAAL). Preliminary version of this paper appeared in Flammini et al. (Proceedings of ACM joint workshop on foundations of mobile computing (DIALM-POMC), pp. 85–91, 2004).     

Aerobic spore-forming bacteria for assessing quality of drinking water produced from surface water

Cryptosporidium and Giardia represent a major microbiological issue for drinking water production from surface water. As their monitoring through a treatment process is rather tedious and as low-concentration goals should be reached for drinking water, aerobic spore-forming bacteria (ASFB) have been studied as an indicator microorganism for a drinking water treatment plant using surface water. The results reveal that monitoring naturally occurring ASFB better highlights daily achievable performances and identifies unusual process events for global disinfection, for both physical and chemical treatment steps in a multi-barrier drinking water treatment plant. Advantages of ASFB over usual process parameters are that these microorganisms are more sensitive to process fluctuations.

The use of ASFB also showed that the efficiency of ozone disinfection is not as significantly influenced by the water temperature as reported, despite similar or higher CT values applied during warmer periods. Thus, the disinfection of resistant microorganisms with ozone can also be an efficient process at lower water temperature.

ASFB have been shown to be a conservative indicator for Cryptosporidium and Giardia up to a 1st stage filtration and the ASFB Log removals can be used to estimate Log removals for Cryptosporidium and Giardia: compared to ASFB, the Log removals for Cryptosporidium or Giardia are at least equal or 50% higher, respectively. Thus, the monitoring of ASFB along a drinking water treatment process could be a useful tool for performing risk analysis for parasites such as Cryptosporidium and Giardia, and would further allow integration of daily variability into a risk analysis.     

Ion-exchange membranes made of semi-interpenetrating polymer networks,used for pervaporation-assisted esterification and ion transport

Ionic membranes were prepared by blending poly(vinyl alcohol) (PVA) with an ionic polymer. Semi-interpenetrating polymer networks (sIPN) in which the crosslinked PVA chains trap the ionic polymer were obtained by using a heat treatment at 180 °C or dibromoethane vapor at 140 °C, respectively, for poly (styrene sulfonic acid) (PSSH), poly (sodium styrene sulfonate) (PSSNa), poly (acrylic acid) (PAA) or poly (dimethyl dimethylene piperidinum chloride) (PDMeDMPCl) as the ionic polymer. The stability of the sIPN membranes in some liquid media was studied to select the appropriate membranes for the envisaged applications. The thermally crosslinked PVA/PSSH membranes showed an effective catalytic effect on the esterification reaction between n-propanol and propanoic acid. An active composite membrane made of a layer of PVA/PSSH deposited on a dense PVA layer of an industrial dehydration membrane exhibited both high catalytic activity and high selectivity to water in the pervaporation-assisted esterification. The values of the counter-ion transport number indicated that some crosslinked ionic membranes have good ion permselectivity.