Heuristic methods for the single machine scheduling problem with different ready times and a common due date

The single machine scheduling problem with a common due date and non-identical ready times for the jobs is examined in this work. Performance is measured by the minimization of the weighted sum of earliness and tardiness penalties of the jobs. Since this problem is NP-hard, the application of constructive heuristics that exploit specific characteristics of the problem to improve their performance is investigated. The proposed approaches are examined through a computational comparative study on a set of 280 benchmark test problems with up to 1000 jobs.

Robust Hybrid Mechanisms for Scheduling of Grid Tasks

This paper proposes three new hybrid mechanisms for the scheduling of grid tasks, which integrate reactive and proactive approaches. They differ by the scheduler used to define the initial schedule of an application and by the scheduler used to reschedule the application. The mechanisms are compared to reactive and proactive mechanisms. Results show that hybrid approach produces performance close to that of the reactive mechanisms, but demanding less migrations.

Integrated pulp and paper mill planning and scheduling

This article describes a real-world production planning and scheduling problem occurring at an integrated pulp and paper mill (P&P) which manufactures paper for cardboard out of produced pulp. During the cooking of wood chips in the digester, two by-products are produced: the pulp itself (virgin fibers) and the waste stream known as black liquor. The former is then mixed with recycled fibers and processed in a paper machine. Here, due to significant sequence-dependent setups in paper type changeovers, sizing and sequencing of lots have to be made simultaneously in order to efficiently use capacity. The latter is converted into electrical energy using a set of evaporators, recovery boilers and counter-pressure turbines. The planning challenge is then to synchronize the material flow as it moves through the pulp and paper mills, and energy plant, maximizing customer demand (as backlogging is allowed), and minimizing operation costs. Due to the intensive capital feature of P&P, the output of the digester must be maximized. As the production bottleneck is not fixed, to tackle this problem we propose a new model that integrates the critical production units associated to the pulp and paper mills, and energy plant for the first time. Simple stochastic mixed integer programming based local search heuristics are developed to obtain good feasible solutions for the problem. The benefits of integrating the three stages are discussed. The proposed approaches are tested on real-world data. Our work may help P&P companies to increase their competitiveness and reactiveness in dealing with demand pattern oscillations. (C) 2012 Elsevier Ltd. All rights reserved.

Using the Hard, Randy, and Rittler Test to Evaluate Color Vision in Capuchins (Cebus libidinosus)

The identification of color vision types in primates is fundamental to understanding the evolution and biological function of color perception. The Hard, Randy, and Rittler (HRR) pseudoisochromatic test categorizes human color vision types successfully. Here we provide an experimental setup to employ HRR in a nonhuman primate, the capuchin (Cebus libidinosus), a platyrrhine with polymorphic color vision. The HRR test consists of plates with a matrix composed of gray circles that vary in size and brightness. Differently colored circles form a geometric shape (X, O, or Delta) that is discriminated visually from the gray background pattern. The ability to identify these shapes determines the type of dyschromatopsy (deficiency in color vision). We tested six capuchins in their own cages under natural sunlight. The subjects chose between two HRR plates in each trial: one with the gray pattern only and the other with a colored shape, presented on the left or right side at random. We presented the test 40 times and calculated the 95 % confidence limits for chance performance based on the binomial test. We also genotyped all subjects for exons 3 and 5 of the X-linked opsin genes. The HRR test diagnosed two subjects as protan dichromats (missing or defective L-cone), three as deutan dichromats (missing or defective M-cone), and one female as trichromat. Genetic analysis supported the behavioral data for all subjects. These findings show that the HRR test can be applied to diagnose color vision in nonhuman primates.

Asynchronous teams for joint lot-sizing and scheduling problem in flow shops

The integrated production scheduling and lot-sizing problem in a flow shop environment consists of establishing production lot sizes and allocating machines to process them within a planning horizon in a production line with machines arranged in series. The problem considers that demands must be met without backlogging, the capacity of the machines must be respected, and machine setups are sequence-dependent and preserved between periods of the planning horizon. The objective is to determine a production schedule to minimise the setup, production and inventory costs. A mathematical model from the literature is presented, as well as procedures for obtaining feasible solutions. However, some of the procedures have difficulty in obtaining feasible solutions for large-sized problem instances. In addition, we address the problem using different versions of the Asynchronous Team (A-Team) approach. The procedures were compared with literature heuristics based on Mixed Integer Programming. The proposed A-Team procedures outperformed the literature heuristics, especially for large instances. The developed methodologies and the results obtained are presented.

Combinatorial-topological framework for the analysis of global dynamics

We discuss an algorithmic framework based on efficient graph algorithms and algebraic-topological computational tools. The framework is aimed at automatic computation of a database of global dynamics of a given m-parameter semidynamical system with discrete time on a bounded subset of the n-dimensional phase space. We introduce the mathematical background, which is based upon Conley's topological approach to dynamics, describe the algorithms for the analysis of the dynamics using rectangular grids both in phase space and parameter space, and show two sample applications. (C) 2012 American Institute of Physics. [http://dx.doi.org/10.1063/1.4767672]

Three time-based scale formulations for the two-stage lot sizing and scheduling in process industries

In this paper, we propose three novel mathematical models for the two-stage lot-sizing and scheduling problems present in many process industries. The problem shares a continuous or quasi-continuous production feature upstream and a discrete manufacturing feature downstream, which must be synchronized. Different time-based scale representations are discussed. The first formulation encompasses a discrete-time representation. The second one is a hybrid continuous-discrete model. The last formulation is based on a continuous-time model representation. Computational tests with state-of-the-art MIP solver show that the discrete-time representation provides better feasible solutions in short running time. On the other hand, the hybrid model achieves better solutions for longer computational times and was able to prove optimality more often. The continuous-type model is the most flexible of the three for incorporating additional operational requirements, at a cost of having the worst computational performance. Journal of the Operational Research Society (2012) 63, 1613-1630. doi:10.1057/jors.2011.159 published online 7 March 2012

Structure and anomalous solubility for hard spheres in an associating lattice gas model

In this paper we investigate the solubility of a hard-sphere gas in a solvent modeled as an associating lattice gas. The solution phase diagram for solute at 5% is compared with the phase diagram of the original solute free model. Model properties are investigated both through Monte Carlo simulations and a cluster approximation. The model solubility is computed via simulations and is shown to exhibit a minimum as a function of temperature. The line of minimum solubility (TmS) coincides with the line of maximum density (TMD) for different solvent chemical potentials, in accordance with the literature on continuous realistic models and on the "cavity" picture. (C) 2012 American Institute of Physics. [http://dx.doi.org/10.1063/1.4743635]

Huckebein is part of a combinatorial repression code in the anterior blastoderm

The hierarchy of the segmentation cascade responsible for establishing the Drosophila body plan is composed by gap, pair-rule and segment polarity genes. However, no pair-rule stripes are formed in the anterior regions of the embryo. This lack of stripe formation, as well as other evidence from the literature that is further investigated here, led us to the hypothesis that anterior gap genes might be involved in a combinatorial mechanism responsible for repressing the cis-regulatory modules (CRMs) of hairy (h), even-skipped (eve), runt (run), and fushi-tarazu (ftz) anterior-most stripes. In this study, we investigated huckebein (hkb), which has a gap expression domain at the anterior tip of the embryo. Using genetic methods we were able to detect deviations from the wild-type patterns of the anterior-most pair-rule stripes in different genetic backgrounds, which were consistent with Hkb-mediated repression. Moreover, we developed an image processing tool that, for the most part, confirmed our assumptions. Using an hkb misexpression system, we further detected specific repression on anterior stripes. Furthermore, bioinformatics analysis predicted an increased significance of binding site clusters in the CRMs of h 1, eve 1, run 1 and ftz 1 when Hkb was incorporated in the analysis, indicating that Hkb plays a direct role in these CRMs. We further discuss that Hkb and Slp1, which is the other previously identified common repressor of anterior stripes, might participate in a combinatorial repression mechanism controlling stripe CRMs in the anterior parts of the embryo and define the borders of these anterior stripes. (C) 2011 Elsevier Inc. All rights reserved.

Hard Thermal Loops in the n-Dimensional phi(3) Theory

We derive a closed-form result for the leading thermal contributions which appear in the n-dimensional I center dot (3) theory at high temperature. These contributions become local only in the long wavelength and in the static limits, being given by different expressions in these two limits.

Influence of adenotonsillectomy on hard palate dimensions

Objective: To evaluate hard palate width and height in mouth-breathing children pre- and post-adenotonsillectomy. Methods: We evaluated 44 children in the 3-6 year age bracket, using dental study casts in order to determine palatal height, intercanine width, and intermolar width. The children were divided into two groups: nasal breathing (n = 15) and mouth breathing (n = 29). The children in the latter group underwent adenotonsillectomy. The study casts were obtained prior to adenotonsillectomy, designated time point 1(11), at 13 months after adenotonsillectomy (T2), and at 28 months after adenotonsillectomy (13). Similar periods of observation were obtained for nasal breathing children. Results: At T1, there was a significantly lower intercanine width in mouth breathing children; intermolar width and palate height were similar between groups. After surgery, there was a significant increase in all the analyzed parameters in both groups, probably due to facial growth. Instead, the increase in intercanine width was substantially more prominent in mouth breathing children than in nasal breathing children, and the former difference failed in significance after the procedure. Conclusions: There were no significant differences between the nasal-breathing and mouth-breathing children in terms of intermolar width and palatal height prior to or after tonsillectomy. Although intercanine width was initially narrower in the mouth-breathing children, it showed normalization after the surgical procedure. These results confirm that the restoration of nasal breathing is central to proper occlusal development. (C) 2012 Elsevier Ireland Ltd. All rights reserved.

Multi-objective evolutionary algorithm for single and multiple fault service restoration in large-scale distribution systems

Network reconfiguration for service restoration (SR) in distribution systems is a complex optimization problem. For large-scale distribution systems, it is computationally hard to find adequate SR plans in real time since the problem is combinatorial and non-linear, involving several constraints and objectives. Two Multi-Objective Evolutionary Algorithms that use Node-Depth Encoding (NDE) have proved able to efficiently generate adequate SR plans for large distribution systems: (i) one of them is the hybridization of the Non-Dominated Sorting Genetic Algorithm-II (NSGA-II) with NDE, named NSGA-N; (ii) the other is a Multi-Objective Evolutionary Algorithm based on subpopulation tables that uses NDE, named MEAN. Further challenges are faced now, i.e. the design of SR plans for larger systems as good as those for relatively smaller ones and for multiple faults as good as those for one fault (single fault). In order to tackle both challenges, this paper proposes a method that results from the combination of NSGA-N, MEAN and a new heuristic. Such a heuristic focuses on the application of NDE operators to alarming network zones according to technical constraints. The method generates similar quality SR plans in distribution systems of significantly different sizes (from 3860 to 30,880 buses). Moreover, the number of switching operations required to implement the SR plans generated by the proposed method increases in a moderate way with the number of faults.