An AI formalism for competing claims of identification: capturing the "Smemorato di Collegno" amnesia case

A formal representation is given of the situational structure, and the agents' beliefs about personal identity, in the Smemorato di Collegno amnesia case tried in 1927, in Pollenza, Italy. Another section discusses and formalizes a sample heuristic rule for conjecturing whether an individual identity other than personal, being conveyed by a toponym, was used literally or fictitiously in a given historical corpus of legal casenotes. For example, a landlocked city being named and referred to as though it was a sea port is a fairly good cue for assuming that the toponym is a disguise. Yet, the interpretation is governed by other conventions, when in a play by Shakeaspeare it is stated that a given scene is set on the sea coast of Bohemia. Further discussion of a situational casuistry for identification (especially individual and personal) along with more formal representations will appear in a companion paper "nissanidentifpirandello", also at the disciplinary meet of AI formalisms and legal applications.

Scheduling parallel dedicated machines under a single non-shared resource

The scheduling problem of minimizing the makespan for m parallel dedicated machines under single resource constraints is considered. For different variants of the problem the complexity status is established. Heuristic algorithms employing the so-called group technology approach are presented and their worst-case behavior is examined. Finally, a polynomial time approximation scheme is presented for the problem with fixed number of machines.

A multilevel algorithm for force-directed graph-drawing

We describe a heuristic method for drawing graphs which uses a multilevel framework combined with a force-directed placement algorithm. The multilevel technique matches and coalesces pairs of adjacent vertices to define a new graph and is repeated recursively to create a hierarchy of increasingly coarse graphs, G0, G1, …, GL. The coarsest graph, GL, is then given an initial layout and the layout is refined and extended to all the graphs starting with the coarsest and ending with the original. At each successive change of level, l, the initial layout for Gl is taken from its coarser and smaller child graph, Gl+1, and refined using force-directed placement. In this way the multilevel framework both accelerates and appears to give a more global quality to the drawing. The algorithm can compute both 2 & 3 dimensional layouts and we demonstrate it on examples ranging in size from 10 to 225,000 vertices. It is also very fast and can compute a 2D layout of a sparse graph in around 12 seconds for a 10,000 vertex graph to around 5-7 minutes for the largest graphs. This is an order of magnitude faster than recent implementations of force-directed placement algorithms.

Batching decisions for assembly production systems

The two-stage assembly scheduling problem is a model for production processes that involve the assembly of final or intermediate products from basic components. In our model, there are m machines at the first stage that work in parallel, and each produces a component of a job. When all components of a job are ready, an assembly machine at the second stage completes the job by assembling the components. We study problems with the objective of minimizing the makespan, under two different types of batching that occur in some manufacturing environments. For one type, the time to process a batch on a machine is equal to the maximum of the processing times of its operations. For the other type, the batch processing time is defined as the sum of the processing times of its operations, and a setup time is required on a machine before each batch. For both models, we assume a batch availability policy, i.e., the completion times of the operations in a batch are defined to be equal to the batch completion time. We provide a fairly comprehensive complexity classification of the problems under the first type of batching, and we present a heuristic and its worst-case analysis under the second type of batching.

A combined evolutionary search and multilevel optimisation approach to graph-partitioning

The graph-partitioning problem is to divide a graph into several pieces so that the number of vertices in each piece is the same within some defined tolerance and the number of cut edges is minimised. Important applications of the problem arise, for example, in parallel processing where data sets need to be distributed across the memory of a parallel machine. Very effective heuristic algorithms have been developed for this problem which run in real-time, but it is not known how good the partitions are since the problem is, in general, NP-complete. This paper reports an evolutionary search algorithm for finding benchmark partitions. A distinctive feature is the use of a multilevel heuristic algorithm to provide an effective crossover. The technique is tested on several example graphs and it is demonstrated that our method can achieve extremely high quality partitions significantly better than those found by the state-of-the-art graph-partitioning packages.

Models and tools for an integrated European environmental management and decision support system, (IEEMDSS)

This work proceeds from the assumption that a European environmental information and communication system (EEICS) is already established. In the context of primary users (land-use planners, conservationists, and environmental researchers) we ask what use may be made of the EEICS for building models and tools which is of use in building decision support systems for the land-use planner. The complex task facing the next generation of environmental and forest modellers is described, and a range of relevant modelling approaches are reviewed. These include visualization and GIS; statistical tabulation and database SQL, MDA and OLAP methods. The major problem of noncomparability of the definitions and measures of forest area and timber volume is introduced and the possibility of a model-based solution is considered. The possibility of using an ambitious and challenging biogeochemical modelling approach to understanding and managing European forests sustainably is discussed. It is emphasised that all modern methodological disciplines must be brought to bear, and a heuristic hybrid modelling approach should be used so as to ensure that the benefits of practical empirical modelling approaches are utilised in addition to the scientifically well-founded and holistic ecosystem and environmental modelling. The data and information system required is likely to end up as a grid-based-framework because of the heavy use of computationally intensive model-based facilities.

Two-machine shop scheduling: Compromise between flexibility and makespan value

In this paper, we consider the problem of providing flexibility to solutions of two-machine shop scheduling problems. We use the concept of group-scheduling to characterize a whole set of schedules so as to provide more choice to the decision-maker at any decision point. A group-schedule is a sequence of groups of permutable operations defined on each machine where each group is such that any permutation of the operations inside the group leads to a feasible schedule. Flexibility of a solution and its makespan are often conflicting, thus we search for a compromise between a low number of groups and a small value of makespan. We resolve the complexity status of the relevant problems for the two-machine flow shop, job shop and open shop. A number of approximation algorithms are developed and their worst-case performance is analyzed. For the flow shop, an effective heuristic algorithm is proposed and the results of computational experiments are reported.

An improved approximation algorithm for the two-machine flow shop scheduling problem with an interstage transporter

We study the two-machine flow shop problem with an uncapacitated interstage transporter. The jobs have to be split into batches, and upon completion on the first machine, each batch has to be shipped to the second machine by a transporter. The best known heuristic for the problem is a –approximation algorithm that outputs a two-shipment schedule. We design a –approximation algorithm that finds schedules with at most three shipments, and this ratio cannot be improved, unless schedules with more shipments are created. This improvement is achieved due to a thorough analysis of schedules with two and three shipments by means of linear programming. We formulate problems of finding an optimal schedule with two or three shipments as integer linear programs and develop strongly polynomial algorithms that find solutions to their continuous relaxations with a small number of fractional variables

The application of multilevel refinement to the vehicle routing problem

We discuss the application of the multilevel (ML) refinement technique to the Vehicle Routing Problem (VRP), and compare it to its single-level (SL) counterpart. Multilevel refinement recursively coarsens to create a hierarchy of approximations to the problem and refines at each level. A SL heuristic, termed the combined node-exchange composite heuristic (CNCH), is developed first to solve instances of the VRP. A ML version (the ML-CNCH) is then created, using the construction and improvement heuristics of the CNCH at each level. Experimentation is used to find a suitable combination, which extends the global view of these heuristics. Results comparing both SL and ML are presented.

An approximation algorithm for the two-machine flow shop with a single transporter

We study the two-machine flow shop problem with an uncapacitated interstage transporter. The jobs have to be split into batches, and upon completion on the first machine, each batch has to be shipped to the second machine by a transporter. The best known heuristic for the problem is a –approximation algorithm that outputs a two-shipment schedule. We design a –approximation algorithm that finds schedules with at most three shipments, and this ratio cannot be improved, unless schedules with more shipments are created. This improvement is achieved due to a thorough analysis of schedules with two and three shipments by means of linear programming. We formulate problems of finding an optimal schedule with two or three shipments as integer linear programs and develop strongly polynomial algorithms that find solutions to their continuous relaxations with a small number of fractional variables.

Multilevel refinement for combinatorial optimisation: boosting metaheuristic performance

The multilevel paradigm as applied to combinatorial optimisation problems is a simple one, which at its most basic involves recursive coarsening to create a hierarchy of approximations to the original problem. An initial solution is found, usually at the coarsest level, and then iteratively refined at each level, coarsest to finest, typically by using some kind of heuristic optimisation algorithm (either a problem-specific local search scheme or a metaheuristic). Solution extension (or projection) operators can transfer the solution from one level to another. As a general solution strategy, the multilevel paradigm has been in use for many years and has been applied to many problem areas (for example multigrid techniques can be viewed as a prime example of the paradigm). Overview papers such as [] attest to its efficacy. However, with the exception of the graph partitioning problem, multilevel techniques have not been widely applied to combinatorial problems and in this chapter we discuss recent developments. In this chapter we survey the use of multilevel combinatorial techniques and consider their ability to boost the performance of (meta)heuristic optimisation algorithms.

Can density functional theory (DFT) be used as an aid to a deeper understanding of tandem mass spectrometric fragmentation pathways?

Prediction of tandem mass spectrometric (MS/MS) fragmentation for non-peptidic molecules based on structure is of immense interest to the mass spectrometrist. If a reliable approach to MS/MS prediction could be achieved its impact within the pharmaceutical industry could be immense. Many publications have stressed that the fragmentation of a molecular ion or protonated molecule is a complex process that depends on many parameters, making prediction difficult. Commercial prediction software relies on a collection of general heuristic rules of fragmentation, which involve cleaving every bond in the structure to produce a list of 'expected' masses which can be compared with the experimental data. These approaches do not take into account the thermodynamic or molecular orbital effects that impact on the molecule at the point of protonation which could influence the potential sites of bond cleavage based on the structural motif. A series of compounds have been studied by examining the experimentally derived high-resolution MS/MS data and comparing it with the in silico modelling of the neutral and protonated structures. The effect that protonation at specific sites can have on the bond lengths has also been determined. We have calculated the thermodynamically most stable protonated species and have observed how that information can help predict the cleavage site for that ion. The data have shown that this use of in silico techniques could be a possible way to predict MS/MS spectra. Copyright (C) 2009 John Wiley & Sons, Ltd.

Unterstützungssysteme im Kontext von Regionalisierungsprozessen. Eine theoretische und empirische Annäherung

In Fragen der Schulentwicklung allgemein, aber auch im Zuge der aktuellen Regionalisierungstendenzen im Schul- und Bildungswesen, wird Unterstützungssystemen für die Einzelschule eine wachsende Bedeutung zugeschrieben. Dennoch finden sich bislang erst wenige Arbeiten im Diskurs, die Unterstützungssysteme im Zusammenhang mit Regionalisierungsprozessen beleuchten und robuste Analyseinstrumente vorstellen, mit deren Hilfe Unterstützung im Zusammenhang von Regionalisierung gefasst werden kann. Dieses Desiderat wird im vorliegenden Beitrag aufgegriffen, indem unter anderem auf Grundlage von governance- sowie motivationstheoretischen Überlegungen Kategorien für eine Heuristik erarbeitet werden, die es erlauben, Unterstützungssysteme allgemein und im Kontext von Schul- und Bildungslandschaften entlang verschiedener Dimensionen zu betrachten. Mittels Interviews, die im Rahmen des Projektes ,Schulen im Team – Übergänge gemeinsam gestalten‘ durchgeführt wurden, wird die Heuristik auf den Forschungskontext zu Regionalen Bildungsbüros inhaltsanalytisch angewendet. Erste Befunde weisen darauf hin, dass sich die Heuristik zur Untersuchung von Unterstützungssystemen für einen regionalen Kontext plausibilisieren lässt. (DIPF/Orig.)

Traceable Radiometry Underpinning Terrestrial- and Helio-Studies (truths)

The Traceable Radiometry Underpinning Terrestrial- and Helio- Studies (TRUTHS) mission offers a novel approach to the provision of key scientific data with unprecedented radiometric accuracy for Earth Observation (EO) and solar studies, which will also establish well-calibrated reference targets/standards to support other EO missions. This paper presents the TRUTHS mission and its objectives. TRUTHS will be the first satellite mission to calibrate its EO instrumentation directly to SI in orbit, overcoming the usual uncertainties associated with drifts of sensor gain and spectral shape by using an electrical rather than an optical standard as the basis of its calibration. The range of instruments flown as part of the payload will also provide accurate input data to improve atmospheric radiative transfer codes by anchoring boundary conditions, through simultaneous measurements of aerosols, particulates and radiances at various heights. Therefore, TRUTHS will significantly improve the performance and accuracy of EO missions with broad global or operational aims, as well as more dedicated missions. The provision of reference standards will also improve synergy between missions by reducing errors due to different calibration biases and offer cost reductions for future missions by reducing the demands for on-board calibration systems. Such improvements are important for the future success of strategies such as Global Monitoring for Environment and Security (GMES) and the implementation and monitoring of international treaties such as the Kyoto Protocol. TRUTHS will achieve these aims by measuring the geophysical variables of solar and lunar irradiance, together with both polarised and unpolarised spectral radiance of the Moon, Earth and its atmosphere.

The emotional structure of the advertising message in radio

Radio advertising is suffering from a remarkable crisis of creativity as it has yet not found its role in a radio model based on voice locution and information genres. This article suggests the need for implementing a peripheral or heuristic strategy to attract and hold listeners’ attention. Within this framework, the narration and scene representation are proposed as suitable persuasion techniques. The objective is to design a useful conceptual tool for an efficient creative conception of narration at the service of certain commercial strategy. First, the concept of narrative persuasion is grounded according to the possibilities of the sound code. Second, the keys of scene representation and commercial strategy (brand, product, advantage, benefit and target) within the sound message are presented. And third, these keys are articulated in a model. This model is pre-tested by means of analyzing eight different case-radio ads.