Minimizing total tardiness in a stochastic single machine scheduling problem using approximate dynamic programming

This paper addresses the non-preemptive single machine scheduling problem to minimize total tardiness. We are interested in the online version of this problem, where orders arrive at the system at random times. Jobs have to be scheduled without knowledge of what jobs will come afterwards. The processing times and the due dates become known when the order is placed. The order release date occurs only at the beginning of periodic intervals. A customized approximate dynamic programming method is introduced for this problem. The authors also present numerical experiments that assess the reliability of the new approach and show that it performs better than a myopic policy.

Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil

In this paper, we consider a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries that occurs in a major Brazilian retail group. A single depot attends 519 stores of the group distributed in 11 Brazilian states. To find good solutions to this problem, we propose heuristics as initial solutions and a scatter search (SS) approach. Next, the produced solutions are compared with the routes actually covered by the company. Our results show that the total distribution cost can be reduced significantly when such methods are used. Experimental testing with benchmark instances is used to assess the merit of our proposed procedure. (C) 2008 Published by Elsevier B.V.

Ciratefi: An RST-invariant template matching with extension to color images

Template matching is a technique widely used for finding patterns in digital images. A good template matching should be able to detect template instances that have undergone geometric transformations. In this paper, we proposed a grayscale template matching algorithm named Ciratefi, invariant to rotation, scale, translation, brightness and contrast and its extension to color images. We introduce CSSIM (color structural similarity) for comparing the similarity of two color image patches and use it in our algorithm. We also describe a scheme to determine automatically the appropriate parameters of our algorithm and use pyramidal structure to improve the scale invariance. We conducted several experiments to compare grayscale and color Ciratefis with SIFT, C-color-SIFT and EasyMatch algorithms in many different situations. The results attest that grayscale and color Ciratefis are more accurate than the compared algorithms and that color-Ciratefi outperforms grayscale Ciratefi most of the time. However, Ciratefi is slower than the other algorithms.

A Separation Principle for the Continuous-Time LQ-Problem With Markovian Jump Parameters

In this paper, we devise a separation principle for the finite horizon quadratic optimal control problem of continuous-time Markovian jump linear systems driven by a Wiener process and with partial observations. We assume that the output variable and the jump parameters are available to the controller. It is desired to design a dynamic Markovian jump controller such that the closed loop system minimizes the quadratic functional cost of the system over a finite horizon period of time. As in the case with no jumps, we show that an optimal controller can be obtained from two coupled Riccati differential equations, one associated to the optimal control problem when the state variable is available, and the other one associated to the optimal filtering problem. This is a separation principle for the finite horizon quadratic optimal control problem for continuous-time Markovian jump linear systems. For the case in which the matrices are all time-invariant we analyze the asymptotic behavior of the solution of the derived interconnected Riccati differential equations to the solution of the associated set of coupled algebraic Riccati equations as well as the mean square stabilizing property of this limiting solution. When there is only one mode of operation our results coincide with the traditional ones for the LQG control of continuous-time linear systems.

On the Filtering Problem for Continuous-Time Markov Jump Linear Systems with no Observation of the Markov Chain

We consider in this paper the optimal stationary dynamic linear filtering problem for continuous-time linear systems subject to Markovian jumps in the parameters (LSMJP) and additive noise (Wiener process). It is assumed that only an output of the system is available and therefore the values of the jump parameter are not accessible. It is a well known fact that in this setting the optimal nonlinear filter is infinite dimensional, which makes the linear filtering a natural numerically, treatable choice. The goal is to design a dynamic linear filter such that the closed loop system is mean square stable and minimizes the stationary expected value of the mean square estimation error. It is shown that an explicit analytical solution to this optimal filtering problem is obtained from the stationary solution associated to a certain Riccati equation. It is also shown that the problem can be formulated using a linear matrix inequalities (LMI) approach, which can be extended to consider convex polytopic uncertainties on the parameters of the possible modes of operation of the system and on the transition rate matrix of the Markov process. As far as the authors are aware of this is the first time that this stationary filtering problem (exact and robust versions) for LSMJP with no knowledge of the Markov jump parameters is considered in the literature. Finally, we illustrate the results with an example.

New simple and efficient heuristics for the uncapacitated single allocation hub location problem

Hub-and-spoke networks are widely studied in the area of location theory. They arise in several contexts, including passenger airlines, postal and parcel delivery, and computer and telecommunication networks. Hub location problems usually involve three simultaneous decisions to be made: the optimal number of hub nodes, their locations and the allocation of the non-hub nodes to the hubs. In the uncapacitated single allocation hub location problem (USAHLP) hub nodes have no capacity constraints and non-hub nodes must be assigned to only one hub. In this paper, we propose three variants of a simple and efficient multi-start tabu search heuristic as well as a two-stage integrated tabu search heuristic to solve this problem. With multi-start heuristics, several different initial solutions are constructed and then improved by tabu search, while in the two-stage integrated heuristic tabu search is applied to improve both the locational and allocational part of the problem. Computational experiments using typical benchmark problems (Civil Aeronautics Board (CAB) and Australian Post (AP) data sets) as well as new and modified instances show that our approaches consistently return the optimal or best-known results in very short CPU times, thus allowing the possibility of efficiently solving larger instances of the USAHLP than those found in the literature. We also report the integer optimal solutions for all 80 CAB data set instances and the 12 AP instances up to 100 nodes, as well as for the corresponding new generated AP instances with reduced fixed costs. Published by Elsevier Ltd.

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.

Pupal Development of Ceratitis capitata (Diptera: Tephritidae) and Diachasmimorpha longicaudata (Hymenoptera: Braconidae) at Different Moisture Values in Four Soil Types

This study aimed to evaluate adult emergence and duration of the pupal stage of the Mediterranean fruit fly, Ceratitis capitata (Wiedemann), and emergence of the fruit fly parasitoid, Diachasmimorpha longicaudata (Ashmead), under different moisture conditions in four soil types, using soil water matric potential Pupal stage duration in C capitata was influenced differently for males and females In females, only soil type affected pupal stage duration, which was longer in a clay soil In males, pupal stage duration was individually influenced by moisture and soil type, with a reduction in pupal stage duration in a heavy clay soil and in a sandy clay, with longer duration in the clay soil As allude potential decreased, duration of the pupal stage of C capitata males increased, regardless of soil type C capitata emergence was affected by moisture, regardless of soil type, and was higher in drier soils The emergence of D longicaudata adults was individually influenced by soil type and moisture factors, and the number of emerged D longicaudata adults was three times higher in sandy loam and lower in a heavy clay soil Always, the number of emerged adults was higher at higher moisture conditions C capitata and D longicaudata pupal development was affected by moisture and soil type, which may facilitate pest sampling and allow release areas for the parasitoid to be defined under field conditions.

Estimating hourly net radiation for leaf wetness duration using the Penman-Monteith equation

Leaf wetness duration (LWD) is related to plant disease occurrence and is therefore a key parameter in agrometeorology. As LWD is seldom measured at standard weather stations, it must be estimated in order to ensure the effectiveness of warning systems and the scheduling of chemical disease control. Among the models used to estimate LWD, those that use physical principles of dew formation and dew and/or rain evaporation have shown good portability and sufficiently accurate results for operational use. However, the requirement of net radiation (Rn) is a disadvantage foroperational physical models, since this variable is usually not measured over crops or even at standard weather stations. With the objective of proposing a solution for this problem, this study has evaluated the ability of four models to estimate hourly Rn and their impact on LWD estimates using a Penman-Monteith approach. A field experiment was carried out in Elora, Ontario, Canada, with measurements of LWD, Rn and other meteorological variables over mowed turfgrass for a 58 day period during the growing season of 2003. Four models for estimating hourly Rn based on different combinations of incoming solar radiation (Rg), airtemperature (T), relative humidity (RH), cloud cover (CC) and cloud height (CH), were evaluated. Measured and estimated hourly Rn values were applied in a Penman-Monteith model to estimate LWD. Correlating measured and estimated Rn, we observed that all models performed well in terms of estimating hourly Rn. However, when cloud data were used the models overestimated positive Rn and underestimated negative Rn. When only Rg and T were used to estimate hourly Rn, the model underestimated positive Rn and no tendency was observed for negative Rn. The best performance was obtained with Model I, which presented, in general, the smallest mean absolute error (MAE) and the highest C-index. When measured LWD was compared to the Penman-Monteith LWD, calculated with measured and estimated Rn, few differences were observed. Both precision and accuracy were high, with the slopes of the relationships ranging from 0.96 to 1.02 and R-2 from 0.85 to 0.92, resulting in C-indices between 0.87 and 0.93. The LWD mean absolute errors associated with Rn estimates were between 1.0 and 1.5h, which is sufficient for use in plant disease management schemes.

Plant availability of phosphorus in four superphosphate fertilizers varying in water-insoluble phosphate compounds

There is concern that the use of lower quality phosphate rock can result in elevated amounts of Fe-Al-P water-insoluble compounds in fertilizers and, consequently, low agronomic effectiveness. Therefore, studies were conducted to evaluate the effect of some of these compounds on plant growth. Four commercial superphosphates varying in chemical composition (two single and two triple superphosphates) were selected for the study. Fertilizer impurities were collected as water-insoluble residues by washing each P source with deionized water. A modal analysis, based primarily on elemental chemical analysis and x-ray diffractometry, was used to estimate the chemical composition of each P source. Water-soluble monocalcium phosphate (MCP) and the water-leached fertilizer residues were prepared to give a range of fertilizers in terms of water-soluble phosphorus (WSP) (0-100% of the available P as MCP). The water-leached fractions, MCP, and the mixtures of MCP with water-leached fractions were applied to supply 40 mg available P kg(1) to a thermic Rhodic Kanhapludult with pH values of 5.2 +/- 0.05 (unlimed) and 6.4 +/- 0.08 (limed). Wheat (Triticum aestivum L.) grown in a greenhouse for 101 d served as the test crop. The requirement for WSP was source and pH dependent. At a soil pH of 5.2, the fertilizers required 73 to 95% WSP to reach the maximum dry-matter yield, while they required 60 to 86% WSP at pH 6.4. To reach 90% of the maximum yield, all superphosphate fertilizers required <50% WSP. These results show that it is not always necessary to have high water solubility as required by legislation in many countries.

Comparative study of phenolic compounds in different Brazilian rice (Oryza sativa L.) genotypes

This study was conducted to evaluate the natural variability of total, extractable and non-extractable phenolics in pigmented and non-pigmented rice genotypes (Oryza sativa L.) and to estimate whether the contents and distribution of these compounds are typical for genotypes from indica and japonica subspecies. Twenty-one samples of commercial as well as new genotypes of brown rice, including seven pigmented genotypes were obtained from two Agronomic Institutes in South Brazil. Free and conjugated phenolics were extracted with ethanol, while bound phenolics were released by alkaline hydrolysis. Total phenolics were estimated in both fractions by the Folin-Ciocalteau method. Genotypes from Japonica and indica non-pigmented subspecies were not statistically distinguishable from each other, but differences in phenolic contents were associated with pericarp color. Despite individual differences, total phenolics were four times higher in pigmented than in non-pigmented genotypes (4246 and 1073 mg ferulic acid equiv. kg(-1), respectively). These high amounts were mostly due to the presence of extractable (free and conjugated) phenolics, which comprised up to 81% of total phenolics for pigmented genotypes. Non-extractable (bound) phenolics comprised 40% of total phenolics of non-pigmented rice genotypes while pigmented genotypes presented greater absolute amounts, but their contribution on total phenolics was small. (C) 2008 Elsevier Inc. All rights reserved.

Study of sunless tanning formulas using molted snake skin as an alternative membrane model

Sunless tanning formulas have become increasingly popular in recent years for their ability to give people convincing tans without the dangers of skin cancer. Most sunless tanners currently on the market contain dihydroxyacetone (DHA), a keto sugar with three carbons. The temporary pigment provided by these formulasis designed to resemble a UV-induced tan. This study evaluated the effectiveness of carbomer gels and cold process self emulsifying bases on skin pigmentation, using different concentrations of a chemical system composed of DHA and N-acetyl tyrosine, which are found in moulted snake skins and their effectiveness was tested by Mexameter (R) MX 18. Eight different sunless tanning formulas were developed, four of which were gels and four of which were emulsions (base, base plus 4.0%, 5.0% and 6.0% (w/w) of a system of DHA and N-acetyl tyrosine). Tests to determine the extent of artificial tanning were done by applying 30 mg cm(-2) of each formula onto standard sizes of moulted snake skin (2.0 cm x 3.0 cm). A Mexameter (R) MX 18 was used to evaluate the extent of coloration in the moulted snake skin at T(0) (before the application) and after 24, 48, 72, 168, 192 and 216 h. The moulted snake skins can be used as an alternative membrane model for in vitro sunless tanning efficacy tests due to their similarity to the human stratum corneum. The DHA concentration was found to influence the initiation of the pigmentation in both sunless tanning systems (emulsion and gel) as well as the time required to increases by a given amount on the tanning index. In the emulsion system, the DHA concentration also influenced the final value on the tanning index. The type of system (emulsion or gel) has no influence on the final value in the tanning index after 216 h for samples with the same DHA concentration.

Characterization of Brazilian lager and brown ale beers based on color, phenolic compounds, and antioxidant activity using chemometrics

BACKGROUND: Epidemiological studies have shown that beer has positive effects on inhibiting atherosclerosis, decreasing the content of serum low-density lipoprotein cholesterol and triglycerides, by acting as in vivo free radical scavenger. In this research, the antioxidant activity of commercial Brazilian beers (n = 29) was determined by the oxygen radical absorbance capacity (ORAC) and 1,1 -diphenyl-2-picrylhydrazyl (DPPH(center dot)) assays and results were analyzed by chemometrics. RESULTS: The brown ale samples (n = 11) presented higher (P < 0.05) flavonoids (124.01 mg L(-1)), total phenolics (362.22 mg L(-1)), non-flavonoid phenolics (238.21 mg L(-1)), lightness (69.48), redness (35.75), yellowness (55.71), color intensity (66.86), hue angle (59.14), color saturation (0.9620), DPPH(center dot) values (30.96% inhibition), and ORAC values (3,659.36 mu mol Trolox equivalents L(-1)), compared to lager samples (n = 18). Brown ale beers presented higher antioxidant properties (P < 0.05) measured by ORAC (1.93 times higher) and DPPH (1.65 times higher) compared to lager beer. ORAC values correlated well with the content of flavonoids (r = 0.47; P = 0.01), total phenolic compounds (r = 0.44; P < 0.01) and DPPH (r = 0.67; P < 0.01). DPPH values also correlated well to the content of flavonoids (r = 0.69; P < 0.01), total phenolic compounds (r = 0.60; P < 0.01), and non-flavonoid compounds (r = 0.46; P = 0.01). CONCLUSION: The results suggest that brown ale beers, and less significantly lager beers, could be sources of bioactive compounds with suitable free radical scavenging properties. (C) 2010 Society of Chemical Industry

High-level and phonological awareness abilities of children following management for supratentorial tumour: Part II

Background. Limited information is available regarding the impact of childhood tumour on the cerebral hemispheres and supratentorial cranial fossa. However, a recent study found that children managed for a tumour located in this region may demonstrate reduced general language abilities. However, the indirect or direct impact of a tumour in this region on higher-level language abilities in childhood is at present largely unknown. Materials and methods. The present study examined the higher language and phonological awareness abilities of five children treated for supratentorial tumour ranging in age from seven to fourteen years in age. Assessments included measures of receptive and expressive semantic abilities, inferencing, figurative language, and problem solving, as well as a comprehensive pre-literacy test. Results. As a group, reductions were evident in problem solving, and in the ability to receive and decode content of high-level language when compared to a group of age- and gender-matched peers. At an individual level, only two of five children managed for supratentorial tumour demonstrated language deficits. These two cases were noted to be the same children previously identified as also having general language deficits. More widespread findings were noted in phonological awareness, with four of the five children previously managed for supratentorial tumour demonstrating weaknesses in one or more areas. Conclusions. Findings demonstrated that weaknesses in general language ability in children managed for supratentorial tumour may indicate higher-level language difficulties. Language abilities beyond general measures of language should be monitored, as well as long-term consideration of phonological awareness abilities in this population.

A cross-linguistic comparison of address pronoun use in four European languages: Intralingual and interlingual dimensions

As part of a major ongoing project, we consider and compare contemporary patterns of address pronoun use in four major European languages- French, German, Italian and Swedish. We are specifically interested in two major aspects: intralingual behaviour, that is, within the same language community, and interlingual dimensions of address pronoun use. With respect to the former, we summarize our key findings to date. We then give consideration in a more preliminary fashion to issues and evidence relevant to the latter.