An Estimation of Distribution Algorithm with Intelligent Local Search for Rule-based Nurse Rostering

This paper proposes a new memetic evolutionary algorithm to achieve explicit learning in rule-based nurse rostering, which involves applying a set of heuristic rules for each nurse's assignment. The main framework of the algorithm is an estimation of distribution algorithm, in which an ant-miner methodology improves the individual solutions produced in each generation. Unlike our previous work (where learning is implicit), the learning in the memetic estimation of distribution algorithm is explicit, i.e. we are able to identify building blocks directly. The overall approach learns by building a probabilistic model, i.e. an estimation of the probability distribution of individual nurse-rule pairs that are used to construct schedules. The local search processor (i.e. the ant-miner) reinforces nurse-rule pairs that receive higher rewards. A challenging real world nurse rostering problem is used as the test problem. Computational results show that the proposed approach outperforms most existing approaches. It is suggested that the learning methodologies suggested in this paper may be applied to other scheduling problems where schedules are built systematically according to specific rules.

An Estimation of Distribution Algorithm with Intelligent Local Search for Rule-based Nurse Rostering

This paper proposes a new memetic evolutionary algorithm to achieve explicit learning in rule-based nurse rostering, which involves applying a set of heuristic rules for each nurse's assignment. The main framework of the algorithm is an estimation of distribution algorithm, in which an ant-miner methodology improves the individual solutions produced in each generation. Unlike our previous work (where learning is implicit), the learning in the memetic estimation of distribution algorithm is explicit, i.e. we are able to identify building blocks directly. The overall approach learns by building a probabilistic model, i.e. an estimation of the probability distribution of individual nurse-rule pairs that are used to construct schedules. The local search processor (i.e. the ant-miner) reinforces nurse-rule pairs that receive higher rewards. A challenging real world nurse rostering problem is used as the test problem. Computational results show that the proposed approach outperforms most existing approaches. It is suggested that the learning methodologies suggested in this paper may be applied to other scheduling problems where schedules are built systematically according to specific rules.

Finite element modeling of fluid-rock interaction problems in pore-fluid saturated hydrothermal/sedimentary basins

In order to use the finite element method for solving fluid-rock interaction problems in pore-fluid saturated hydrothermal/sedimentary basins effectively and efficiently, we have presented, in this paper, the new concept and numerical algorithms to deal with the fundamental issues associated with the fluid-rock interaction problems. These fundamental issues are often overlooked by some purely numerical modelers. (1) Since the fluid-rock interaction problem involves heterogeneous chemical reactions between reactive aqueous chemical species in the pore-fluid and solid minerals in the rock masses, it is necessary to develop the new concept of the generalized concentration of a solid mineral, so that two types of reactive mass transport equations, namely, the conventional mass transport equation for the aqueous chemical species in the pore-fluid and the degenerated mass transport equation for the solid minerals in the rock mass, can be solved simultaneously in computation. (2) Since the reaction area between the pore-fluid and mineral surfaces is basically a function of the generalized concentration of the solid mineral, there is a definite need to appropriately consider the dependence of the dissolution rate of a dissolving mineral on its generalized concentration in the numerical analysis. (3) Considering the direct consequence of the porosity evolution with time in the transient analysis of fluid-rock interaction problems; we have proposed the term splitting algorithm and the concept of the equivalent source/sink terms in mass transport equations so that the problem of variable mesh Peclet number and Courant number has been successfully converted into the problem of constant mesh Peclet and Courant numbers. The numerical results from an application example have demonstrated the usefulness of the proposed concepts and the robustness of the proposed numerical algorithms in dealing with fluid-rock interaction problems in pore-fluid saturated hydrothermal/sedimentary basins. (C) 2001 Elsevier Science B.V. All rights reserved.

Interior point method for long-term generation scheduling of large-scale hydrothermal systems

This paper presents an interior point method for the long-term generation scheduling of large-scale hydrothermal systems. The problem is formulated as a nonlinear programming one due to the nonlinear representation of hydropower production and thermal fuel cost functions. Sparsity exploitation techniques and an heuristic procedure for computing the interior point method search directions have been developed. Numerical tests in case studies with systems of different dimensions and inflow scenarios have been carried out in order to evaluate the proposed method. Three systems were tested, with the largest being the Brazilian hydropower system with 74 hydro plants distributed in several cascades. Results show that the proposed method is an efficient and robust tool for solving the long-term generation scheduling problem.

Integrating Crew Scheduling and Rostering Problems

Crew scheduling and crew rostering are similar and related problems which can be solved by similar procedures. So far, the existing solution methods usually create a model for each one of these problems (scheduling and rostering), and when they are solved together in some cases an interaction between models is considered in order to obtain a better solution. A single set covering model to solve simultaneously both problems is presented here, where the total quantity of drivers needed is directly considered and optimized. This integration allows to optimize all of the depots at the same time, while traditional approaches needed to work depot by depot, and also it allows to see and manage the relationship between scheduling and rostering, which was known in some degree but usually not easy to quantify as this model permits. Recent research in the area of crew scheduling and rostering has stated that one of the current challenges to be achieved is to determine a schedule where crew fatigue, which depends mainly on the quality of the rosters created, is reduced. In this approach rosters are constructed in such way that stable working hours are used in every week of work, and a change to a different shift is done only using free days in between to make easier the adaptation to the new working hours. Computational results for real-world-based instances are presented. Instances are geographically diverse to test the performance of the procedures and the model in different scenarios.

Storage problems in batch scheduling

This paper is concerned with the modelling of storage configurations for intermediate products in process industries. Those models form the basis of algorithms for scheduling chemical production plants. Different storage capacity settings (unlimited, finite, and no intermediate storage), storage homogeneity settings (dedicated and shared storage), and storage time settings (unlimited, finite, and no wait) are considered. We discuss a classification of storage constraints in batch scheduling and show how those constraints can be integrated into a general production scheduling model that is based on the concept of cumulative resources.

Scheduling in a two-machine flowshop for the minimization of the mean absolute deviation from a common due date

This paper addresses the minimization of the mean absolute deviation from a common due date in a two-machine flowshop scheduling problem. We present heuristics that use an algorithm, based on proposed properties, which obtains an optimal schedule fora given job sequence. A new set of benchmark problems is presented with the purpose of evaluating the heuristics. Computational experiments show that the developed heuristics outperform results found in the literature for problems up to 500 jobs. (C) 2007 Elsevier Ltd. All rights reserved.

The single machine earliness and tardiness scheduling problem: lower bounds and a branch-and-bound algorithm

This paper addresses the single machine scheduling problem with a common due date aiming to minimize earliness and tardiness penalties. Due to its complexity, most of the previous studies in the literature deal with this problem using heuristics and metaheuristics approaches. With the intention of contributing to the study of this problem, a branch-and-bound algorithm is proposed. Lower bounds and pruning rules that exploit properties of the problem are introduced. The proposed approach is examined through a computational comparative study with 280 problems involving different due date scenarios. In addition, the values of optimal solutions for small problems from a known benchmark are provided.

Finite element analysis of flow patterns near geological lenses in hydrodynamic and hydrothermal systems

We use theoretical and numerical methods to investigate the general pore-fluid flow patterns near geological lenses in hydrodynamic and hydrothermal systems respectively. Analytical solutions have been rigorously derived for the pore-fluid velocity, stream function and excess pore-fluid pressure near a circular lens in a hydrodynamic system. These analytical solutions provide not only a better understanding of the physics behind the problem, but also a valuable benchmark solution for validating any numerical method. Since a geological lens is surrounded by a medium of large extent in nature and the finite element method is efficient at modelling only media of finite size, the determination of the size of the computational domain of a finite element model, which is often overlooked by numerical analysts, is very important in order to ensure both the efficiency of the method and the accuracy of the numerical solution obtained. To highlight this issue, we use the derived analytical solutions to deduce a rigorous mathematical formula for designing the computational domain size of a finite element model. The proposed mathematical formula has indicated that, no matter how fine the mesh or how high the order of elements, the desired accuracy of a finite element solution for pore-fluid flow near a geological lens cannot be achieved unless the size of the finite element model is determined appropriately. Once the finite element computational model has been appropriately designed and validated in a hydrodynamic system, it is used to examine general pore-fluid flow patterns near geological lenses in hydrothermal systems. Some interesting conclusions on the behaviour of geological lenses in hydrodynamic and hydrothermal systems have been reached through the analytical and numerical analyses carried out in this paper.

Finite element analysis of heat transfer and mineralization in layered hydrothermal systems with upward throughflow

We use the finite element method to solve the coupled problem between convective pore-fluid flow, heat transfer and mineralization in layered hydrothermal systems with upward throughflow. In particular, we present the improved rock alteration index (IRAI) concept for predicting the most probable precipitation and dissolution regions of gold (Au) minerals in the systems. To validate the numerical method used in the computation, analytical solutions to a benchmark problem have been derived. After the numerical method is validated, it is used to investigate the pattern of pore-fluid Aom, the distribution of temperature and the mineralization pattern of gold minerals in a layered hydrothermal system with upward throughflow. The related numerical results have demonstrated that the present concept of IRAI is useful and applicable for predicting the most probable precipitation and dissolution regions of gold (Au) minerals in hydrothermal systems. (C) 2000 Elsevier Science S.A. All rights reserved.

Finite element modelling of three-dimensional convection problems in fluid-saturated porous media heated from below

We use the finite element method to model three-dimensional convective pore-fluid flow in fluid-saturated porous media when they are heated from below. In particular, we employ the particle-tracking technique to mimic the trajectories of particles in three-dimensional fluid flow problems. The related numerical results demonstrated that: (1) The progressive asymptotic approach procedure, which was previously developed for the finite element modelling of two-dimensional convective pore-fluid flow problems, is equally applicable to the finite element modelling of three-dimensional convective pore-fluid flow in fluid-saturated porous media heated from below. (2) The perturbation of gravity at different planes has a significant effect on the pattern of three-dimensional convective pore-fluid flow and therefore, may influence the pattern of orebody formation and mineralization in three-dimensional hydrothermal systems. Copyright (C) 2001 John Wiley & Sons, Ltd.

Finite element modelling of rock alteration and metamorphic process in hydrothermal systems

We use the finite element method to simulate the rock alteration and metamorphic process in hydrothermal systems. In particular, we consider the fluid-rock interaction problems in pore-fluid saturated porous rocks. Since the fluid rock interaction takes place at the contact interface between the pore-fluid and solid minerals, it is governed by the chemical reaction which usually takes place very slowly at this contact interface, from the geochemical point of view. Due to the relative slowness of the rate of the chemical reaction to the velocity of the pore-fluid flow in the hydrothermal system to be considered, there exists a retardation zone, in which the conventional static theory in geochemistry does not hold true. Since this issue is often overlooked by some purely numerical modellers, it is emphasized in this paper. The related results from a typical rock alteration and metamorphic problem in a hydrothermal system have shown not only the detailed rock alteration and metamorphic process, but also the size of the retardation zone in the hydrothermal system. Copyright (C) 2001 John Wiley & Sons, Ltd.

Computer simulations of coupled problems in geological and geochemical systems

The finite element method is used to simulate coupled problems, which describe the related physical and chemical processes of ore body formation and mineralization, in geological and geochemical systems. The main purpose of this paper is to illustrate some simulation results for different types of modelling problems in pore-fluid saturated rock masses. The aims of the simulation results presented in this paper are: (1) getting a better understanding of the processes and mechanisms of ore body formation and mineralization in the upper crust of the Earth; (2) demonstrating the usefulness and applicability of the finite element method in dealing with a wide range of coupled problems in geological and geochemical systems; (3) qualitatively establishing a set of showcase problems, against which any numerical method and computer package can be reasonably validated. (C) 2002 Published by Elsevier Science B.V.

Finite element modelling of reactive fluids mixing and mineralization in pore-fluid saturated hydrothermal/sedimentary basins

We present the finite element simulations of reactive mineral carrying fluids mixing and mineralization in pore-fluid saturated hydrothermal/sedimentary basins. In particular we explore the mixing of reactive sulfide and sulfate fluids and the relevant patterns of mineralization for Load, zinc and iron minerals in the regime of temperature-gradient-driven convective flow. Since the mineralization and ore body formation may last quite a long period of time in a hydrothermal basin, it is commonly assumed that, in the geochemistry, the solutions of minerals are in an equilibrium state or near an equilibrium state. Therefore, the mineralization rate of a particular kind of mineral can be expressed as the product of the pore-fluid velocity and the equilibrium concentration of this particular kind of mineral Using the present mineralization rate of a mineral, the potential of the modern mineralization theory is illustrated by means of finite element studies related to reactive mineral-carrying fluids mixing problems in materially homogeneous and inhomogeneous porous rock basins.