A Hybrid Evolutionary Approach to the Nurse Rostering Problem

Nurse rostering is a difficult search problem with many constraints. In the literature, a number of approaches have been investigated including penalty function methods to tackle these constraints within genetic algorithm frameworks. In this paper, we investigate an extension of a previously proposed stochastic ranking method, which has demonstrated superior performance to other constraint handling techniques when tested against a set of constrained optimisation benchmark problems. An initial experiment on nurse rostering problems demonstrates that the stochastic ranking method is better in finding feasible solutions but fails to obtain good results with regard to the objective function. To improve the performance of the algorithm, we hybridise it with a recently proposed simulated annealing hyper-heuristic within a local search and genetic algorithm framework. The hybrid algorithm shows significant improvement over both the genetic algorithm with stochastic ranking and the simulated annealing hyper-heuristic alone. The hybrid algorithm also considerably outperforms the methods in the literature which have the previously best known results.

A hybrid metaheuristic approach to the university course timetabling problem

This paper describes the development of a novel metaheuristic that combines an electromagnetic-like mechanism (EM) and the great deluge algorithm (GD) for the University course timetabling problem. This well-known timetabling problem assigns lectures to specific numbers of timeslots and rooms maximizing the overall quality of the timetable while taking various constraints into account. EM is a population-based stochastic global optimization algorithm that is based on the theory of physics, simulating attraction and repulsion of sample points in moving toward optimality. GD is a local search procedure that allows worse solutions to be accepted based on some given upper boundary or ‘level’. In this paper, the dynamic force calculated from the attraction-repulsion mechanism is used as a decreasing rate to update the ‘level’ within the search process. The proposed method has been applied to a range of benchmark university course timetabling test problems from the literature. Moreover, the viability of the method has been tested by comparing its results with other reported results from the literature, demonstrating that the method is able to produce improved solutions to those currently published. We believe this is due to the combination of both approaches and the ability of the resultant algorithm to converge all solutions at every search process.

A Hybrid Imperialist Approach in Solving University Timetabling Problems. Information Sciences. Vol. 283, 1-21

Generating timetables for an institution is a challenging and time consuming task due to different demands on the overall structure of the timetable. In this paper, a new hybrid method which is a combination of a great deluge and artificial bee colony algorithm (INMGD-ABC) is proposed to address the university timetabling problem. Artificial bee colony algorithm (ABC) is a population based method that has been introduced in recent years and has proven successful in solving various optimization problems effectively. However, as with many search based approaches, there exist weaknesses in the exploration and exploitation abilities which tend to induce slow convergence of the overall search process. Therefore, hybridization is proposed to compensate for the identified weaknesses of the ABC. Also, inspired from imperialist competitive algorithms, an assimilation policy is implemented in order to improve the global exploration ability of the ABC algorithm. In addition, Nelder–Mead simplex search method is incorporated within the great deluge algorithm (NMGD) with the aim of enhancing the exploitation ability of the hybrid method in fine-tuning the problem search region. The proposed method is tested on two differing benchmark datasets i.e. examination and course timetabling datasets. A statistical analysis t-test has been conducted and shows the performance of the proposed approach as significantly better than basic ABC algorithm. Finally, the experimental results are compared against state-of-the art methods in the literature, with results obtained that are competitive and in certain cases achieving some of the current best results to those in the literature.

Logic and Memory Design Based on Unequal Error Protection for Voltage-scalable, Robust and Adaptive DSP Systems

In this paper, we propose a system level design approach considering voltage over-scaling (VOS) that achieves error resiliency using unequal error protection of different computation elements, while incurring minor quality degradation. Depending on user specifications and severity of process variations/channel noise, the degree of VOS in each block of the system is adaptively tuned to ensure minimum system power while providing "just-the-right" amount of quality and robustness. This is achieved, by taking into consideration block level interactions and ensuring that under any change of operating conditions, only the "less-crucial" computations, that contribute less to block/system output quality, are affected. The proposed approach applies unequal error protection to various blocks of a system-logic and memory-and spans multiple layers of design hierarchy-algorithm, architecture and circuit. The design methodology when applied to a multimedia subsystem shows large power benefits ( up to 69% improvement in power consumption) at reasonable image quality while tolerating errors introduced due to VOS, process variations, and channel noise.

Optimization of Cement Grouts Containing Silica Fume and Viscosity Modifying Admixture

There is an increasing need to identify the effect of mix composition on the rheological properties of cementitious grouts using minislump, Marsh cone, cohesion plate, washout test, and cubes to determine the fluidity, the cohesion, and other mechanical properties of grouting applications. Mixture proportioning involves the tailoring of several parameters to achieve adequate fluidity, cohesion, washout resistance and compressive strength. This paper proposes a statistical design approach using a composite fractional factorial design which was carried out to model the influence of key parameters on the performance of cement grouts. The responses relate to performance included minislump, flow time using Marsh cone, cohesion measured by Lombardi plate meter, washout mass loss and compressive strength at 3, 7, and 28 days. The statistical models are valid for mixtures with water-to-binder ratio of 0.37–0.53, 0.4–1.8% addition of high-range water reducer (HRWR) by mass of binder, 4–12% additive of silica fume as replacement of cement by mass, and 0.02–0.8% addition of viscosity modifying admixture (VMA) by mass of binder. The models enable the identification of underlying factors and interactions that influence the modeled responses of cement grout. The comparison between the predicted and measured responses indicated good accuracy of the established models to describe the effect of the independent variables on the fluidity, cohesion, washout resistance and the compressive strength. This paper demonstrates the usefulness of the models to better understand trade-offs between parameters. The multiparametric optimization is used to establish isoresponses for a desirability function for cement grout. An increase of HRWR led to an increase of fluidity and washout, a reduction in plate cohesion value, and a reduction in the Marsh cone time. An increase of VMA demonstrated a reduction of fluidity and the washout mass loss, and an increase of Marsh cone time and plate cohesion. Results indicate that the use of silica fume increased the cohesion plate and Marsh cone, and reduced the minislump. Additionally, the silica fume improved the compressive strength and the washout resistance.

Dual functional ionic liquids as plasticisers and antimicrobial agents for medical polymers

Contamination of medical devices with bacteria such as Meticillin resistant Staphylococcus aureus (MRSA) is of great clinical concern. Poly(vinyl chloride) is widely used in the production of medical devices, such as catheters. The flexibility of catheter tubing is derived from the addition of plasticisers. Here, we report the design of two dual functional ionic liquids, 1-ethylpyridinium docusate and tributyl(2-hydroxyethyl)phosphonium docusate, which uniquely provide a plasticising effect, and exhibit antimicrobial and antibiofilm-forming activity to a range of antibiotic resistant bacteria. The plasticisation of poly(vinyl chloride) was tailored as a function of ionic liquid concentration. The effective antimicrobial behaviour of both ionic liquids originates from the chemical structure of the anion or cation and is not limited to the length of the alkyl chain on the anion/cation. The design approach adopted will be useful in developing ionic liquids as multi-functional additives for polymers.

Fully hardware based WFQ architecture for high-speed QoS packet scheduling

A full hardware implementation of a Weighted Fair Queuing (WFQ) packet scheduler is proposed. The circuit architecture presented has been implemented using Altera Stratix II FPGA technology, utilizing RLDII and QDRII memory components. The circuit can provide fine granularity Quality of Service (QoS) support at a line throughput rate of 12.8Gb/s in its current implementation. The authors suggest that, due to the flexible and scalable modular circuit design approach used, the current circuit architecture can be targeted for a full ASIC implementation to deliver 50 Gb/s throughput. The circuit itself comprises three main components; a WFQ algorithm computation circuit, a tag/time-stamp sort and retrieval circuit, and a high throughput shared buffer. The circuit targets the support of emerging wireline and wireless network nodes that focus on Service Level Agreements (SLA's) and Quality of Experience.

Algorithms and architectures for high performance recursive filtering

Recently, a number of most significant digit (msd) first bit parallel multipliers for recursive filtering have been reported. However, the design approach which has been used has, in general, been heuristic and consequently, optimality has not always been assured. In this paper, msd first multiply accumulate algorithms are described and important relationships governing the dependencies between latency, number representations, etc are derived. A more systematic approach to designing recursive filters is illustrated by applying the algorithms and associated relationships to the design of cascadable modules for high sample rate IIR filtering and wave digital filtering.

Rijndael FPGA implementations utilising look-up tables

This paper presents single-chip FPGA Rijndael algorithm implementations of the Advanced Encryption Standard (AES) algorithm, Rijndael. In particular, the designs utilise look-up tables to implement the entire Rijndael Round function. A comparison is provided between these designs and similar existing implementations. Hardware implementations of encryption algorithms prove much faster than equivalent software implementations and since there is a need to perform encryption on data in real time, speed is very important. In particular, Field Programmable Gate Arrays (FPGAs) are well suited to encryption implementations due to their flexibility and an architecture, which can be exploited to accommodate typical encryption transformations. In this paper, a Look-Up Table (LUT) methodology is introduced where complex and slow operations are replaced by simple LUTs. A LUT-based fully pipelined Rijndael implementation is described which has a pre-placement performance of 12 Gbits/sec, which is a factor 1.2 times faster than an alternative design in which look-up tables are utilised to implement only one of the Round function transformations, and 6 times faster than other previous single-chip implementations. Iterative Rijndael implementations based on the Look-Up-Table design approach are also discussed and prove faster than typical iterative implementations.

Parameter studies of fibre laser micro-welding of AISI 316L using Taguchi method

This paper discusses the application of the Taguchi experimental design approach in optimizing the key process parameters for micro-welding of thin AISI 316L foil using the 100W CW fibre laser. A L16 Taguchi experiment was conducted to systematically understand how the power, scanning velocity, focus position, gas flow rate and type of shielding gas affect the bead dimensions. The welds produced in the L16 Taguchi experiment was mainly of austenite cellular-dendrite structure with an average grain size of 5µm. An exact penetration weld with the largest penetration to fusion width ratio was obtained. Among those process parameters, the interaction between power and scanning velocity presented the strongest effect to the penetration to fusion width ratio and the power was found to be the predominantly important factor that drives the interaction with other factors to appreciably affect the bead dimensions.

System level DSP synthesis using voltage overscaling, unequal error protection & adaptive quality tuning

In this paper, we propose a system level design approach considering voltage over-scaling (VOS) that achieves error resiliency using unequal error protection of different computation elements, while incurring minor quality degradation. Depending on user specifications and severity of process variations/channel noise, the degree of VOS in each block of the system is adaptively tuned to ensure minimum system power while providing "just-the-right" amount of quality and robustness. This is achieved, by taking into consideration system level interactions and ensuring that under any change of operating conditions only the "lesscrucial" computations, that contribute less to block/system output quality, are affected. The design methodology applied to a DCT/IDCT system shows large power benefits (up to 69%) at reasonable image quality while tolerating errors induced by varying operating conditions (VOS, process variations, channel noise). Interestingly, the proposed IDCT scheme conceals channel noise at scaled voltages. ©2009 IEEE.

Cold-formed steel portal frames in fire: Full-scale testing and finite element analysis

A full-scale, non-uniform natural fire test on a cold-formed steel portal frame building is described. The results of the test are used to validate a non-linear, elasto-plastic, finite element shell idealisation, for the purposes of later forming the basis of a performance-based design approach for cold-formed steel portal frames at elevated temperatures.