Simulation optimization for process scheduling through simulated annealing

This paper presents a simulation optimization of a real scheduling problem in industry, simulated annealing is introduced for this purpose.  Investigation is performed into the practicality of using simulated annealing to produce high quality schedules.  Results on the solution quality and computational effort show the inherent properties of the simulated annealing.  It is shown that when using this method, high quality schedules can be produced within reasonable time contraints.

Design of multiple sequence alignment algorithms on parallel, distributed memory supercomputers

The challenge of comparing two or more genomes that have undergone recombination and substantial amounts of segmental loss and gain has recently been addressed for small numbers of genomes. However, datasets of hundreds of genomes are now common and their sizes will only increase in the future. Multiple sequence alignment of hundreds of genomes remains an intractable problem due to quadratic increases in compute time and memory footprint. To date, most alignment algorithms are designed for commodity clusters without parallelism. Hence, we propose the design of a multiple sequence alignment algorithm on massively parallel, distributed memory supercomputers to enable research into comparative genomics on large data sets. Following the methodology of the sequential progressiveMauve algorithm, we design data structures including sequences and sorted k-mer lists on the IBM Blue Gene/P supercomputer (BG/P). Preliminary results show that we can reduce the memory footprint so that we can potentially align over 250 bacterial genomes on a single BG/P compute node. We verify our results on a dataset of E.coli, Shigella and S.pneumoniae genomes. Our implementation returns results matching those of the original algorithm but in 1/2 the time and with 1/4 the memory footprint for scaffold building. In this study, we have laid the basis for multiple sequence alignment of large-scale datasets on a massively parallel, distributed memory supercomputer, thus enabling comparison of hundreds instead of a few genome sequences within reasonable time.

New cutting-planes for the time-and/or precedence-constrained ATSP and directed VRP

In this paper, we introduce five classes of new valid cutting planes for the precedence-constrained (PC) and/or time-window-constrained (TW) Asymmetric Travelling Salesman Problems (ATSPs) and directed Vehicle Routing Problems (VRPs). We show that all five classes of new inequalities are facet-defining for the directed VRP-TW, under reasonable conditions and the assumption that vehicles are identical. Similar proofs can be developed for the VRP-PC. As ATSP-TW and PC-ATSP can be formulated as directed identical-vehicle VRP-TW and PC-VRP, respectively, this provides a link to study the polyhedral combinatorics for the ATSP-TW and PC-ATSP. The first four classes of these new cutting planes are cycle-breaking inequalities that are lifted from the well-known D^-_k and D⁺_k inequalities (see Grötschel and Padberg in Polyhedral theory. The traveling salesman problem: a guided tour of combinatorial optimization, Wiley, New York, 1985). The last class of new cutting planes, the TW ₂ inequalities, are infeasible-path elimination inequalities. Separation of these constraints will also be discussed. We also present prelimanry numerical results to demonstrate the strengh of these new cutting planes.

Outsourcing the risks : alcohol licensing, risk and the making of the night time economy

Mariana Valverde argues that in the late twentieth century, the British state contracted out the prevention of disorder and monitoring of risks produced by widespread alcohol use to the private sector through the process of liquor licensing. This paper will argue that this scenario was duplicated in Victoria at the same time. It will do so by an analysis of four government-instigated inquiries into liquor licensing regimes from 1965 to 1998. The inquiries were distinguished by the subtly different emphases in their terms of reference. In 1965, the Phillips Royal Commission was directed to inquire into the best ways of dealing with the problems alcohol produced and how best to regulate it for the benefit of the population as a whole. By the time the Nieuwenhuysen Report was commissioned in 1985, the emphasis had changed, and he was directed to inquire how best to serve the interests of alcohol consumers and to produce the licensing regulatory regime which would enable the construction of a 24-hour city. Any anomalies that still existed in the revised Act were eliminated in the 1998 review which was instigated as a direct response to the National Competition Policy. A consequence of these changes over 30 years was the development of particular risk groups, such as ‘binge-drinking young people’, whose violence and nuisance must be controlled to enable all other ‘reasonable’ and ‘moderate’ drinkers be allowed to keep drinking. Thus the notion of risk had been redefined and the responsibility for dealing with these risks had been directed from the state to individual licensees and individual drinkers.

Effects of time since fire on birds : how informative are generalized fire response curves for conservation management?

Fire is both a widespread natural disturbance that affects the distribution of species and a tool that can be used to manage habitats for species. Knowledge of temporal changes in the occurrence of species after fire is essential for conservation management in fire-prone environments. Two key issues are: whether postfire responses of species are idiosyncratic or if multiple species show a limited number of similar responses; and whether such responses to time since fire can predict the occurrence of species across broad spatial scales. We examined the response of bird species to time since fire in semiarid shrubland in southeastern Australia using data from surveys at 499 sites representing a 100-year chronosequence. We used nonlinear regression to model the probability of occurrence of 30 species with time since fire in two vegetation types, and compared species' responses with generalized response shapes from the literature. The occurrence of 16 species was significantly influenced by time since fire: they displayed six main responses consistent with generalized response shapes. Of these 16 species, 15 occurred more frequently in mid- or later-successional vegetation (>20 years since fire), and only one species occurred more often in early succession (<5 years since fire). The models had reasonable predictive ability for eight species, some predictive ability for seven species, and were little better than random for one species. Bird species displayed a limited range of responses to time since fire; thus a small set of fire ages should allow the provision of habitat for most species. Postfire successional changes extend for decades and management of the age class distribution of vegetation will need to reflect this timescale. Response curves revealed important seral stages for species and highlighted the importance of mid- to late-successional vegetation (>20 years). Although time since fire clearly influences the distribution of numerous bird species, predictive models of the spatial distribution of species in fire-prone landscapes need to incorporate other factors in addition to time since fire.

Departure fuel loads in time-minimizing migrating birds can be explained by the energy costs of being heavy

Lindstrom and Alerstam presented a model that predicts optimal departure fuel loads as a function of the rate of fuel deposition in time-minimizing migrants. The basis of the model is that the coverable distance per unit of fuel deposited, diminishes with increasing fuel load. This is an effect of the increasing flight costs associated with increasing body mass. Lindstrom and Alerstam (1992) found that birds left at lower fuel loads than their model predicted for which they considered various ecological explanations. Alternatively, we hypothesize that the difference between prediction and empirical data might be a result of extra resting metabolic and transport costs associated with an increase in fuel load during stopover. We develop a new version of the Lindstrom and Alerstam (1992) model taking fuel load associated costs during stopover into account. We fit empirical data from rufous hummingbirds Selasphorus rufus and bluethroats Luscinia svecica to this new model. Estimated fuel-load costs are discussed in relation to knowledge presently available on variations in basal metabolic costs and transport costs with body mass. We show that fuel-load costs within a reasonable range can explain the observed departure fuel loads when migrating birds are time minimizers.