Beyond Smith's rule: An optimal dynamic index, rule for single machine stochastic scheduling with convex holding costs

Most research on single machine scheduling has assumedthe linearity of job holding costs, which is arguablynot appropriate in some applications. This motivates ourstudy of a model for scheduling $n$ classes of stochasticjobs on a single machine, with the objective of minimizingthe total expected holding cost (discounted or undiscounted). We allow general holding cost rates that are separable,nondecreasing and convex on the number of jobs in eachclass. We formulate the problem as a linear program overa certain greedoid polytope, and establish that it issolved optimally by a dynamic (priority) index rule,whichextends the classical Smith's rule (1956) for the linearcase. Unlike Smith's indices, defined for each class, ournew indices are defined for each extended class, consistingof a class and a number of jobs in that class, and yieldan optimal dynamic index rule: work at each time on a jobwhose current extended class has larger index. We furthershow that the indices possess a decomposition property,as they are computed separately for each class, andinterpret them in economic terms as marginal expected cost rate reductions per unit of expected processing time.We establish the results by deploying a methodology recentlyintroduced by us [J. Niño-Mora (1999). "Restless bandits,partial conservation laws, and indexability. "Forthcomingin Advances in Applied Probability Vol. 33 No. 1, 2001],based on the satisfaction by performance measures of partialconservation laws (PCL) (which extend the generalizedconservation laws of Bertsimas and Niño-Mora (1996)):PCL provide a polyhedral framework for establishing theoptimality of index policies with special structure inscheduling problems under admissible objectives, which weapply to the model of concern.

Solving two production scheduling problems with sequence-dependent set-up times

In today’s competitive markets, the importance of goodscheduling strategies in manufacturing companies lead to theneed of developing efficient methods to solve complexscheduling problems.In this paper, we studied two production scheduling problemswith sequence-dependent setups times. The setup times areone of the most common complications in scheduling problems,and are usually associated with cleaning operations andchanging tools and shapes in machines.The first problem considered is a single-machine schedulingwith release dates, sequence-dependent setup times anddelivery times. The performance measure is the maximumlateness.The second problem is a job-shop scheduling problem withsequence-dependent setup times where the objective is tominimize the makespan.We present several priority dispatching rules for bothproblems, followed by a study of their performance. Finally,conclusions and directions of future research are presented.

Programación de pedidos en una máquina de la vida real con tiempos de preparación dependientes de la secuencia

En este trabajo se evalúan algoritmos heurísticos de exploración de entornos(AED, ANED, SA, TS, GA y GRASP) en la programación de pedidos en unamáquina de la vida real, con el objetivo de minimizar la suma de retrasos . Elcaso estudiado se diferencia de los problemas convencionales en que lostiempos de preparación de las operaciones están separados de los tiempos deprocesamiento y son dependientes de la secuencia. Los resultadoscomputacionales revelan que la Búsqueda Tabú funciona mejor que los otrosalgoritmos aplicados.

A user-friendly web portal for T-Coffee on supercomputers

Background: Parallel T-Coffee (PTC) was the first parallel implementation of the T-Coffee multiple sequence alignment tool. It is based on MPI and RMA mechanisms. Its purpose is to reduce the execution time of the large-scale sequence alignments. It can be run on distributed memory clusters allowing users to align data sets consisting of hundreds of proteins within a reasonable time. However, most of the potential users of this tool are not familiar with the use of grids or supercomputers. Results: In this paper we show how PTC can be easily deployed and controlled on a super computer architecture using a web portal developed using Rapid. Rapid is a tool for efficiently generating standardized portlets for a wide range of applications and the approach described here is generic enough to be applied to other applications, or to deploy PTC on different HPC environments. Conclusions: The PTC portal allows users to upload a large number of sequences to be aligned by the parallel version of TC that cannot be aligned by a single machine due to memory and execution time constraints. The web portal provides a user-friendly solution.

Hysteresis in a system driven by either generalized force or displacement variables: martensitic phase transition in single-crystalline Cu-Zn-Al

We report on experiments aimed at comparing the hysteretic response of a Cu-Zn-Al single crystal undergoing a martensitic transition under strain-driven and stress-driven conditions. Strain-driven experiments were performed using a conventional tensile machine while a special device was designed to perform stress-driven experiments. Significant differences in the hysteresis loops were found. The strain-driven curves show reentrant behavior yield point which is not observed in the stress-driven case. The dissipated energy in the stress-driven curves is larger than in the strain-driven ones. Results from recently proposed models qualitatively agree with experiments.

Single period Markowitz portfolio selection, performance gauging and duality: a variation on Luenberger's shortage function

Markowitz portfolio theory (1952) has induced research into the efficiency of portfolio management. This paper studies existing nonparametric efficiency measurement approaches for single period portfolio selection from a theoretical perspective and generalises currently used efficiency measures into the full mean-variance space. Therefore, we introduce the efficiency improvement possibility function (a variation on the shortage function), study its axiomatic properties in the context of Markowitz efficient frontier, and establish a link to the indirect mean-variance utility function. This framework allows distinguishing between portfolio efficiency and allocative efficiency. Furthermore, it permits retrieving information about the revealed risk aversion of investors. The efficiency improvement possibility function thus provides a more general framework for gauging the efficiency of portfolio management using nonparametric frontier envelopment methods based on quadratic optimisation.

A Characterization of single-peaked preferences

We identify in this paper two conditions that characterize the domain of single-peaked preferences on the line in the following sense: a preference profile satisfies these two properties if and only if there exists a linear order $L$ over the set of alternatives such that these preferences are single-peaked with respect L. The first property states that for any subset of alternatives the set of alternatives considered as the worst by all agents cannot contains more than 2 elements. The second property states that two agents cannot disagree on the relative ranking of two alternatives with respect to a third alternative but agree on the (relative) ranking of a fourth one. Classification-JEL: D71, C78

A note on the separability principle in economies with single-peaked

We consider the problem of allocating an infinitely divisible commodity among a group of agents with single-peaked preferences. A rule that has played a central role in the analysis of the problem is the so-called uniform rule. Chun (2001) proves that the uniform rule is the only rule satisfying Pareto optimality, no-envy, separability, and continuity (with respect to the social endowment). We obtain an alternative characterization by using a weak replication-invariance condition, called duplication-invariance, instead of continuity. Furthermore, we prove that Pareto optimality, equal division lower bound, and separability imply no-envy. Using this result, we strengthen one of Chun's (2001) characterizations of the uniform rule by showing that the uniform rule is the only rule satisfying Pareto optimality, equal división lower bound, separability, and either continuity or duplication-invariance.

Aplicaciones Single Program Multiple Data (SPMD) en ambientes distribuidos

Un reto al ejecutar las aplicaciones en un cluster es lograr mejorar las prestaciones utilizando los recursos de manera eficiente, y este reto es mayor al utilizar un ambiente distribuido. Teniendo en cuenta este reto, se proponen un conjunto de reglas para realizar el cómputo en cada uno de los nodos, basado en el análisis de cómputo y comunicaciones de las aplicaciones, se analiza un esquema de mapping de celdas y un método para planificar el orden de ejecución, tomando en consideración la ejecución por prioridad, donde las celdas de fronteras tienen una mayor prioridad con respecto a las celdas internas. En la experimentación se muestra el solapamiento del computo interno con las comunicaciones de las celdas fronteras, obteniendo resultados donde el Speedup aumenta y los niveles de eficiencia se mantienen por encima de un 85%, finalmente se obtiene ganancias de los tiempos de ejecución, concluyendo que si se puede diseñar un esquemas de solapamiento que permita que la ejecución de las aplicaciones SPMD en un cluster se hagan de forma eficiente.

On Strategy-proofness and symmetric single-peakedness

We characterize the class of strategy-proof social choice functions on the domain of symmetric single-peaked preferences. This class is strictly larger than the set of generalized median voter schemes (the class of strategy-proof and tops-only social choice functions on the domain of single-peaked preferences characterized by Moulin (1980)) since, under the domain of symmetric single-peaked preferences, generalized median voter schemes can be disturbed by discontinuity points and remain strategy-proof on the smaller domain. Our result identifies the specific nature of these discontinuities which allow to design non-onto social choice functions to deal with feasibility constraints.

Control of optical fields and single photon emitters by advanced nanoantenna structures

The control of optical fields on the nanometre scale is becoming an increasingly important tool in many fields, ranging from channelling light delivery in photovoltaics and light emitting diodes to increasing the sensitivity of chemical sensors to single molecule levels. The ability to design and manipulate light fields with specific frequency and space characteristics is explored in this project. We present an alternative realisation of Extraordinary Optical Transmission (EOT) that requires only a single aperture and a coupled waveguide. We show how this waveguide-resonant EOT improves the transmissivity of single apertures. An important technique in imaging is Near-Field Scanning Optical Microscopy (NSOM); we show how waveguide-resonant EOT and the novel probe design assist in improving the efficiency of NSOM probes by two orders of magnitude, and allow the imaging of single molecules with an optical resolution of as good as 50 nm. We show how optical antennas are fabricated into the apex of sharp tips and can be used in a near-field configuration.

Omnidirectional Depth Computation from a Single Image

Omnidirectional cameras offer a much wider field of view than the perspective ones and alleviate the problems due to occlusions. However, both types of cameras suffer from the lack of depth perception. A practical method for obtaining depth in computer vision is to project a known structured light pattern on the scene avoiding the problems and costs involved by stereo vision. This paper is focused on the idea of combining omnidirectional vision and structured light with the aim to provide 3D information about the scene. The resulting sensor is formed by a single catadioptric camera and an omnidirectional light projector. It is also discussed how this sensor can be used in robot navigation applications

Label Space Reduction in MPLS Networks: How Much Can A Single Stacked Label Do?

Most network operators have considered reducing LSR label spaces (number of labels used) as a way of simplifying management of underlaying virtual private networks (VPNs) and therefore reducing operational expenditure (OPEX). The IETF outlined the label merging feature in MPLS-allowing the configuration of multipoint-to-point connections (MP2P)-as a means of reducing label space in LSRs. We found two main drawbacks in this label space reduction a)it should be separately applied to a set of LSPs with the same egress LSR-which decreases the options for better reductions, and b)LSRs close to the edge of the network experience a greater label space reduction than those close to the core. The later implies that MP2P connections reduce the number of labels asymmetrically

An empirical study of machine learning techniques applied to image watermarking

A study of how the machine learning technique, known as gentleboost, could improve different digital watermarking methods such as LSB, DWT, DCT2 and Histogram shifting.

Estimation of zero-sequence impedance of undergrounds cables for single-phase fault location in distribution systems with electric arc

This paper focus on the problem of locating single-phase faults in mixed distribution electric systems, with overhead lines and underground cables, using voltage and current measurements at the sending-end and sequence model of the network. Since calculating series impedance for underground cables is not as simple as in the case of overhead lines, the paper proposes a methodology to obtain an estimation of zero-sequence impedance of underground cables starting from previous single-faults occurred in the system, in which an electric arc occurred at the fault location. For this reason, the signal is previously pretreated to eliminate its peaks voltage and the analysis can be done working with a signal as close as a sinus wave as possible