Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times

A scheduling problem with unrelated parallel machines, sequence and machine-dependent setup times, due dates and weighted jobs is considered in this work. A branch-and-bound algorithm (B&B) is developed and a solution provided by the metaheuristic GRASP is used as an upper bound. We also propose a set of instances for this type of problem. The results are compared to the solutions provided by two mixed integer programming models (MIP) with the solver CPLEX 9.0. We carry out computational experiments and the algorithm performs extremely well on instances with up to 30 jobs.     

Multiplexed spectral coding for simultaneous detection of DNA hybridization reactions based on FRET

Fluorescence resonance energy transfer (FRET) is widely used in spectral codification of information at the molecular level, and can be used to generate several layers of information on a DNA chip. We used two oligonucleotides (probes) labeled with different donor (harvesting) molecules in hybridization experiments with complementary oligonucleotides labeled with four different acceptors (targets). By looking at the fluorescence response of the sample after “specific” excitation of each donor molecule (by “specific” we mean a wavelength where one of the donors is predominantly excited), we inspected the possibility to identify the complementary oligonucleotide hybridized to the probe, in mixtures containing two donor probe/acceptor target pairs. In most samples (13 out of the 16 possible), it is trivial to identify the complementary target that is hybridized to the excited donor probe in the mixtures. The major limitations of the chosen system arise when very different concentrations of donor probe/acceptor target pairs are present in the same sample.     

Interactive tool for analysis of time-delay systems with dead-time compensators

The problem of controlling delayed systems has been widely studied in the control community. The Smith predictor (SP) scheme was the most famous and efficient technique to cope with this problem. Afterwards, robustness problems and those related to the control of integrating and unstable delayed processes were resolved. This work presents an interactive tool for studying and understanding the different alternatives available for controlling systems with large delays. Interactive tools have provided excellent support for the control community during recent years. In this sense, the tool developed here helps to compare easily the performance of PID controllers and SP approaches for processes with delay, as well as other control structures used to solve different problems that the original SP has when integrator and unstable models are employed. Robustness problems due to presence of model uncertainties can also be analyzed. Furthermore, some real industrial processes are also described as motivation in the study of the problems presented in the paper. The tool incorporates a set of typical transfer functions based on these real industrial processes.     

Invariant sets techniques for Youla–Kučera parameter synthesis

This article addresses an invariant sets approach for Youla–Ku?era parameter synthesis using linear matrix inequality (LMI) techniques. Given a linear discrete-time observer-based system affected by bounded disturbances and constraints, the proposed technique furnishes the best Youla parameter in terms of finding an invariant ellipsoidal set satisfying the constraints and having the maximal ellipsoidal projection on the state space. Compared with the results obtained for an observer-based design, the synthesis of a Youla parameter provides a larger ellipsoidal projection and an improved sensitivity function. The price to pay for these achievements in terms of robustness is usually a slow closed-loop performance with degraded complementary sensitivity function. In order to obtain a compromise between robustness and performance two methods are proposed: the first method imposes a new bound on the Lyapunov function decreasing speed and the second refers to the pole placement concept. The aforementioned approaches are finally validated in simulation considering position control of an induction motor.     

Applying classifier systems to learn the reactions in mobile robots

The navigation problem involves how to reach a goal avoiding obstacles in dynamic environments. This problem can be faced considering reactions and sequences of actions. Classifier systems (CSs) have proven their ability of continuous learning, however, they have some problems in reactive systems. A modified CS, namely a reactive classifier system (RCS), is proposed to overcome those problems. Two special mechanisms are included in the RCS: the non-existence of internal cycles inside the CS (no internal cycles) and the fusion of environmental message with the messages posted to the message list in the previous instant (generation list through fusion). These mechanisms allow the learning of both reactions and sequences of actions. This learning process involves two main tasks: first, discriminate between rules and, second, the discovery of new rules to obtain a successful operation in dynamic environments. DiVerent experiments have been carried out using a mini-robot Khepera to find a generalized solution. The results show the ability of the system for continuous learning and adaptation to new situations.     

A family of simple distributed minimum connected dominating set-based topology construction algorithms

This paper considers the problem of topology construction to save energy in wireless sensor networks. The proposed topology construction mechanisms build reduced topologies using the Connected Dominating Set approach in a distributed, efficient, and simple manner. This problem is very challenging because the solution must provide a connected network with complete coverage of the area of interest using the minimum number of nodes possible. Further, the algorithms need to be computationally inexpensive and the protocols simple enough in terms of their message and computation complexity, so they do not consume more energy creating the reduced topology than the energy that they are supposed to save. In addition, it is desirable to reduce or completely eliminate the need of localization mechanisms since they introduce additional costs and energy consumption. To this end, we present the family of A3 distributed topology construction algorithms, four simple algorithms that build reduced topologies with very low computational and message complexity without the need of localization information: A3, A3Cov, A3Lite and A3CovLite. The algorithms are compared in sparse and dense networks versus optimal theoretical bounds for connected-coverage topologies and two distributed heuristics found in the literature using the number of active nodes and the ratio of coverage as the main performance metrics. The results demonstrate that there is no clear winner, and rather, trade offs exist. If coverage is not as critical as energy (network lifetime), it would be better to use A3Lite, as it needs fewer number of nodes and messages. If coverage is very important for the application, then the A3CovLite is the best option mostly because of the lower message complexity.     

A model-driven approach for reusing tests in smart home systems

The continuous advances of ubiquitous and pervasive computing have contributed to the successful increase in smart home systems. However, usually these systems are developed at a lower abstraction level very tied to specific technologies. Model-driven approaches have emerged to tackle the design of these systems, improving their reusability and maintainability and decreasing their complexity. Nevertheless, the existing model-driven approaches to develop smart home systems do not cover the whole development process, and testing activities are still relegated to the final programming stages, reducing their reusability for different technologies or platforms. Some approaches have proposed the incorporation of testing activities into the model-driven process. However, the test models defined are very tied to the specific systems and they must be redesigned for every new system to test, reducing thus the reusability of the test behavior. In this setting, this paper presents a process to define reusable tests that may be automatically applied to different smart home systems. The process is integrated into a whole MDD approach that provides support for the modeling of smart home systems at two different abstraction levels, ensuring the reusability of tests also for different smart home platforms.     

p2pWeb: An open,decentralized infrastructure of Web servers for sharing ephemeral Web content

Nowadays, we are witnessing an increasing growth of Web 2.0 content such as micronews, blogs and RSS feeds. This trend exemplified by applications like Twitter and LiveJournal is starting to slow down not only by the limitations of existing services – proprietary and centralized, but also by the cumbersome process of discovering and tracking interesting content. This content is generally ephemeral and thus difficult to index by conventional Web search technology. This problem is exacerbated by the passive role adopted by Web content providers: it is surprising that Web servers publish information and expect that thousands of other servers (search engines, Web-based aggregators like GoogleNews, etc.) advertise their content to the world.In this work we propose p2pWeb, an open, decentralized infrastructure to enable Web servers to use their spare capacity to filter out, aggregate and disseminate Web content in a scalable and timely manner. p2pWeb is flexible enough to support a broad variety of services. The main property of p2pWeb is that all communication abstractions, including aggregation and multicast, are implemented hierarchically and using the HTTP protocol. Simulation results certify the viability of our approach.     

Mobile Application Profiling for Connected Mobile Devices

The SymPA (Symbian Protocol Analyzer) tool correlates traffic information, radio-access-technology measurements, and location data to help developers evaluate mobile applications in the field.     

A multi-objective genetic algorithm applied to autonomous underwater vehicles for sewage outfall plume dispersion observations

This work presents a multi-objective genetic algorithm to solve route planning problem for multiple autonomous underwater vehicles (AUVs) for interdisciplinary coastal research. AUVs are mobile unmanned platforms that carry their own energy and are able to move themselves in the water without intervention from an external operator. Using AUVs one can provide high-quality measurements of physical properties of effluent plumes in a very effective manner under real oceanic conditions. The AUV's route planning problem is a combinatorial optimization problem, where the vehicles must travel through a three-dimensional irregular space with all dimensions known. Therefore, minimization of the total travel distance while considering the maximum number of water samples is the main objective. Besides the AUV kinematics restrictions other considerations must be taken into account to the problem, like the ocean currents. The practical applications of this approach are the environmental monitoring missions which typically require the sampling of a volume of water with non-trivial geometry for which parallel line sweeping might be a costly solution. Some real-life test problems and related solutions are presented.