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.

Price dispersion and price indexes

The traditional theory of price index numbers is based on the law of one price. But in the real world, we frequently observe the existence of an equilibrium price dispersion instead of one price of equilibrium. This article discusses the effects of price dispersion on two price indexes: the cost of living index and the consumer price index. With price dispersion and consumer searching for the lowest price, these indexes cannot be interpreted as deterministic indicators, but as stochastic indicators, and they can be biased if price dispersion is not taken into account. A measure for the bias of the consumer price index is proposed and the article ends with an estimation of the bias based on data obtained from the consumer price index calculated for the city of Sao Paulo, Brazil, from January 1988 through December 2004. The period analysed is very interesting, because it exhibits different inflationary environments: high levels and high volatility of the rates of inflation with great price dispersion until July 1994 and low and relatively stable rates of inflation with prices less dispersed after August 1994.

U-curve: A branch-and-bound optimization algorithm for U-shaped cost functions on Boolean lattices applied to the feature selection problem

This paper presents the formulation of a combinatorial optimization problem with the following characteristics: (i) the search space is the power set of a finite set structured as a Boolean lattice; (ii) the cost function forms a U-shaped curve when applied to any lattice chain. This formulation applies for feature selection in the context of pattern recognition. The known approaches for this problem are branch-and-bound algorithms and heuristics that explore partially the search space. Branch-and-bound algorithms are equivalent to the full search, while heuristics are not. This paper presents a branch-and-bound algorithm that differs from the others known by exploring the lattice structure and the U-shaped chain curves of the search space. The main contribution of this paper is the architecture of this algorithm that is based on the representation and exploration of the search space by new lattice properties proven here. Several experiments, with well known public data, indicate the superiority of the proposed method to the sequential floating forward selection (SFFS), which is a popular heuristic that gives good results in very short computational time. In all experiments, the proposed method got better or equal results in similar or even smaller computational time. (C) 2009 Elsevier Ltd. All rights reserved.

Short-time behaviour of demand and price viewed through an exactly solvable model for heterogeneous interacting market agents

We introduce a stochastic heterogeneous interacting-agent model for the short-time non-equilibrium evolution of excess demand and price in a stylized asset market. We consider a combination of social interaction within peer groups and individually heterogeneous fundamentalist trading decisions which take into account the market price and the perceived fundamental value of the asset. The resulting excess demand is coupled to the market price. Rigorous analysis reveals that this feedback may lead to price oscillations, a single bounce, or monotonic price behaviour. The model is a rare example of an analytically tractable interacting-agent model which allows LIS to deduce in detail the origin of these different collective patterns. For a natural choice of initial distribution, the results are independent of the graph structure that models the peer network of agents whose decisions influence each other. (C) 2009 Elsevier B.V. All rights reserved.

E-contracting with price configuration for Web services and QoS

The large amount of information in electronic contracts hampers their establishment due to high complexity. An approach inspired in Software Product Line (PL) and based on feature modelling was proposed to make this process more systematic through information reuse and structuring. By assessing the feature-based approach in relation to a proposed set of requirements, it was showed that the approach does not allow the price of services and of Quality of Services (QoS) attributes to be considered in the negotiation and included in the electronic contract. Thus, this paper also presents an extension of such approach in which prices and price types associated to Web services and QoS levels are applied. An extended toolkit prototype is also presented as well as an experiment example of the proposed approach.

Do school based food and nutrition policies improve diet and reduce obesity?

OBJECTIVE: To review the effectiveness of school food and nutrition policies world wide in improving the school food environment, student's dietary intake, and decreasing overweight and obesity. METHODS: Systematic review of published and unpublished literature up to November 2007 of three categories of nutrition policy; nutrition guidelines, regulation of food and/or beverage availability, and price interventions applied in preschools, primary and secondary schools. RESULTS: 18 studies met the inclusion criteria. Most evidence of effectiveness was found for the impact of both nutrition guidelines and price interventions on intake and availability of food and drinks, with less conclusive research on product regulation. Despite the introduction of school food policies worldwide few large scale or national policies have been evaluated, and all included studies were from the USA and Europe. CONCLUSION: Some current school policies have been effective in improving the food environment and dietary intake in schools, but there is little evaluation of their impact on BMI. As schools have been proposed worldwide as a major setting for tackling childhood obesity it is essential that future policy evaluations measure the long term effectiveness of a range of school food policies in tackling both dietary intake and overweight and obesity.

The constrained compartmentalized knapsack problem: mathematical models and solution methods

The constrained compartmentalized knapsack problem can be seen as an extension of the constrained knapsack problem. However, the items are grouped into different classes so that the overall knapsack has to be divided into compartments, and each compartment is loaded with items from the same class. Moreover, building a compartment incurs a fixed cost and a fixed loss of the capacity in the original knapsack, and the compartments are lower and upper bounded. The objective is to maximize the total value of the items loaded in the overall knapsack minus the cost of the compartments. This problem has been formulated as an integer non-linear program, and in this paper, we reformulate the non-linear model as an integer linear master problem with a large number of variables. Some heuristics based on the solution of the restricted master problem are investigated. A new and more compact integer linear model is also presented, which can be solved by a branch-and-bound commercial solver that found most of the optimal solutions for the constrained compartmentalized knapsack problem. On the other hand, heuristics provide good solutions with low computational effort. (C) 2011 Elsevier BM. All rights reserved.

Veias do sistema porta-hepático em gansos domésticos

A distribuição intraparenquimal das veias porta-hepáticas foi estudada em 30 gansos domésticos. Latex Neoprene corado foi injetado pela veia isquiática e os animais forma fixados por imersão e injeção intramuscular com formol a 10% e dissecados. O fígado esteve composto por um grande lobo hepático direito e por um lobo hepático esquerdo menor, os quais estiveram conectados por uma ponte de parênquima. O lobo direito do fígado teve exclusivamente vasos do sistema porta-hepático formados pela distribuição intraparenquimal da veia porta-hepática direita, enquanto que no lobo esquerdo estes originaram-se da veia porta-hepática direita e de pequenas veias porta-hepáticas esquerdas. A veia porta-hepática direita emitiu o ramo caudal direito, que emitiu um pequeno ramo caudolateral direito e um grande ramo caudomedial direito. Cranialmente esta veia emitiu os ramos craniais direito e ramos lateral direito. A porção transversa da veia porta-hepática direita cruzou para o lobo hepático esquerdo, emitindo de 1 a 6 pequenos ramos craniais e caudais para a região média do fígado. No lobo esquerdo, o ramo esquerdo da veia porta-hepática direita emitiu o ramo cranial esquerdo, o ramo lateral esquerdo e o ramo medial. De 1 a 6 veias porta-hepáticas esquerdas foram identificadas desembocando ou no ramo esquerdo da veia porta-hepática direita ou em sua porção transversa, oriundos do ventrículo gástrico e do pró-ventrículo. Em 40% dos gansos uma veia porta-hepática própria oriunda da confluência de vasos venosos da face esquerda do ventrículo distribuiu-se na extremidade caudal do lobo esquerdo isoladamente.

Renda familiar, preço de alimentos e aquisição domiciliar de frutas e hortaliças no Brasil

OBJETIVO: Analisar a influência da renda familiar e do preço de alimentos sobre a participação de frutas e hortaliças dentre os alimentos adquiridos pelas famílias brasileiras. MÉTODOS: Foram utilizados dados da Pesquisa de Orçamentos Familiares realizada pelo Instituto Brasileiro de Geografia e Estatística, com amostra probabilística de 48.470 domicílios brasileiros entre 2002 e 2003. A participação de frutas e hortaliças no total de aquisições de alimentos foi expressa como percentual do total de calorias adquiridas e como calorias provenientes desses alimentos ajustadas para o total de calorias adquirido. Empregaram-se técnicas de análise de regressão múltipla para estimação de coeficientes de elasticidade, controlando-se variáveis sociodemográficas e preço dos demais alimentos. RESULTADOS: Observou-se aumento da participação de frutas e hortaliças no total de aquisições de alimentos com a diminuição de seu próprio preço ou com o aumento da renda. A diminuição do preço de frutas e hortaliças em 1 por cento aumentaria sua participação em 0,79 por cento do total calórico; o aumento de 1 por cento na renda familiar aumentaria essa participação no total calórico em 0,27 por cento. O efeito da renda tendeu a ser menor nos estratos de maior renda. CONCLUSÕES: A redução do preço de frutas e hortaliças, tanto pelo apoio à cadeia de produção dos alimentos quanto por medidas fiscais, é um promissor instrumento de política pública capaz de aumentar a participação desses alimentos na dieta brasileira

PFLEIDERER 2: IDENTIFICATION OF A NEW GLOBULAR CLUSTER IN THE GALAXY

We provide evidence that indicates the star cluster Pfleiderer 2, which is projected in a rich field, as a newly identified Galactic globular cluster. Since it is located in a crowded field, core extraction and decontamination tools were applied to reveal the cluster sequences in B, V, and I color-magnitude diagrams (CMDs). The main CMD features of Pfleiderer 2 are a tilted red giant branch and a red horizontal branch, indicating a high metallicity around solar. The reddening is E(B - V) = 1.01. The globular cluster is located at a distance of d(circle dot) = 16 +/- 2 kpc from the Sun. The cluster is located 2.7 kpc above the Galactic plane and at a distance of R(GC) = 9.7 kpc from the Galactic center, which is unusual for a metal-rich globular cluster.

f t value of the 0(+)-> 0(+) beta(+) decay of (32)Ar: A measurement of isospin symmetry breaking in a superallowed decay

We determined the absolute branch of the T=2 superallowed decay of (32)Ar by detecting the beta(+)-delayed protons and gamma decays of the daughter state. We obtain b(SA)(beta)=(22.71 +/- 0.16)%, which represents the first determination of a proton branch to better than 1%. Using this branch along with the previously determined (32)Ar half-life and energy release, we determined ft=(1552 +/- 12) s for the superallowed decay. This ft value, together with the corrected Ft value extracted from previously known T=1 superallowed decays, yields a measurement of the isospin symmetry breaking correction in (32)Ar decay delta(exp)(C)=(2.1 +/- 0.8)%. This can be compared to a theoretical calculation delta(C)=(2.0 +/- 0.4)%. As by-products of this work, we determined the gamma and proton branches for the decay of the lowest T=2 state of (32)Cl, made a precise determination of the total proton branch and relative intensities of proton groups that leave (31)S in its first excited state and deduced an improved value for the (32)Cl mass.

Some heuristic algorithms for total tardiness minimization in a flowshop with blocking

The flowshop scheduling problem with blocking in-process is addressed in this paper. In this environment, there are no buffers between successive machines: therefore intermediate queues of jobs waiting in the system for their next operations are not allowed. Heuristic approaches are proposed to minimize the total tardiness criterion. A constructive heuristic that explores specific characteristics of the problem is presented. Moreover, a GRASP-based heuristic is proposed and Coupled with a path relinking strategy to search for better outcomes. Computational tests are presented and the comparisons made with an adaptation of the NEH algorithm and with a branch-and-bound algorithm indicate that the new approaches are promising. (c) 2007 Elsevier Ltd. All rights reserved.

Pricing corporate bonds in Brazil: 2000 to 2004

This paper analyzes the factors that influence the issuing price of debentures in Brazil in the period from year 2000 to 2004, applying a factor model, in which exogenous variables explain return and price behavior. The variables in this study include: rating, choice of index, maturity, country risk, basic interest rate, long-term and short-term rate spread, the stock market index, and the foreign exchange rate. Results indicate that the index variable, probability of default and bond`s maturity influence pricing and points out associations of long-term bonds with better rating issues. (C) 2008 Elsevier Inc. All rights reserved.

Two-level network design with intermediate facilities: An application to electrical distribution systems

We consider the two-level network design problem with intermediate facilities. This problem consists of designing a minimum cost network respecting some requirements, usually described in terms of the network topology or in terms of a desired flow of commodities between source and destination vertices. Each selected link must receive one of two types of edge facilities and the connection of different edge facilities requires a costly and capacitated vertex facility. We propose a hybrid decomposition approach which heuristically obtains tentative solutions for the vertex facilities number and location and use these solutions to limit the computational burden of a branch-and-cut algorithm. We test our method on instances of the power system secondary distribution network design problem. The results show that the method is efficient both in terms of solution quality and computational times. (C) 2010 Elsevier Ltd. All rights reserved.

Orthogonal packing of identical rectangles within isotropic convex regions

A mixed integer continuous nonlinear model and a solution method for the problem of orthogonally packing identical rectangles within an arbitrary convex region are introduced in the present work. The convex region is assumed to be made of an isotropic material in such a way that arbitrary rotations of the items, preserving the orthogonality constraint, are allowed. The solution method is based on a combination of branch and bound and active-set strategies for bound-constrained minimization of smooth functions. Numerical results show the reliability of the presented approach. (C) 2010 Elsevier Ltd. All rights reserved.