A polynomial algorithm for special case of the one-machine scheduling problem with time-lags

The standard one-machine scheduling problem consists in schedulinga set of jobs in one machine which can handle only one job at atime, minimizing the maximum lateness. Each job is available forprocessing at its release date, requires a known processing timeand after finishing the processing, it is delivery after a certaintime. There also can exists precedence constraints between pairsof jobs, requiring that the first jobs must be completed beforethe second job can start. An extension of this problem consistsin assigning a time interval between the processing of the jobsassociated with the precedence constrains, known by finish-starttime-lags. In presence of this constraints, the problem is NP-hardeven if preemption is allowed. In this work, we consider a specialcase of the one-machine preemption scheduling problem with time-lags, where the time-lags have a chain form, and propose apolynomial algorithm to solve it. The algorithm consist in apolynomial number of calls of the preemption version of the LongestTail Heuristic. One of the applicability of the method is to obtainlower bounds for NP-hard one-machine and job-shop schedulingproblems. We present some computational results of thisapplication, followed by some conclusions.

The European Union Police Mission: The Beginning of a New Future for Bosnia and Herzegovina?

The creation, reform and/or restructuring of the police in post-conflict societies remains one of the key challenges for practitioners and scholars in the contemporary fields of peace and security, particularly due to the changing nature of conflicts. Since the 1990s the world has witnessed a proliferation of international police missions, with regional organisations gradually acquiring a prominent role. This paper analyses the 2003-2005 period of the European Union Police Mission (EUPM) in Bosnia and Herzegovina. Much is at stake in this mission, both in terms of the development of the EU´s external identity but also for Bosnia and Herzegovina’s road to EU membership and sustainable peace. This paper will argue that by 2005 the balance sheet was mixed. EUPM fell short of fulfilling its overall goal of ‘Europeanising’ Bosnian police services, and of its desire to be seen as providing that additional ingredient in police matters that would set it apart from the earlier UN mission. Nevertheless, despite its shortcomings, the Mission did not merit the harsh criticisms it was faced with. Its lack of success was not entirely the Mission’s doing. The paper focuses on three aspects: political and economic viability and sustainability, security levels in Bosnia and Herzegovina, and institution and capacity building. The explanatory framework used in this paper is based on the democratic policing discourse. In doing so the argument developed here will also shed light on the nature of so-called “best European practices” in police matters.

Las Olimpiadas desconocidas: Special Olympics

Este documento se presentó en la Asignatura Campus de la Universidad Autónoma de Barcelona (UAB) “Olimpismo, Sociedad y Deporte” durante el curso académico 1996/97. El objetivo de la autora es mostrar y describir qué es la entidad Special Olympics y cómo funciona.

New technologies in marketing: the special case of Buzz Marketing

Cada dia és més difícil convèncer al consumidor de que compri els productes d’una determinada empresa o contracti els seus serveis simplement amb la publicitat convencional. Això ha provocat l’aparició de noves tècniques per publicitar i arribar de manera mes eficient al públic objectiu. Buzz Marketing és un nou terme provinent de l’anglès i la seva traducció vindria a ser “marketing mitjançant el rumor o de tafaneria”. Hi ha noms similars com el Boca-Orella o la predicació.

Els jocs de la il·Iusió: la integració del disminuït psíquic a través de l’esport i del moviment Special Olympics

Aquest treball es va realitzar per a l’assignatura Campus “Olimpisme, Esport i Societat” durant el curs 1996-97. En ell es proporcionen els principis de la institució Special Olympics, i es descriu l’organització de la cinquena edició dels Jocs Special Olympics de Catalunya que van tenir lloc a Reus, el 1996.

Pràcticum I : Psicologia de l'Educació. Anàlisi de l'educació inclusiva a través d'una aula USEE a secundària

L'existència d'una aula USEE ha de permetre la inclusió dels alumnes amb NEE en un entorn majoritàriament ordinari. El present treball és una aproximació a l'educació inclusiva, les seves dificultats i aplicacions a través d'una experiència pràctica en un institut al voltant de la seva aula USEE. Les tasques pràctiques realitzades estan dividides en dos grans blocs: per una banda la recollida d'informació per a la identificació i l'anàlisi dels grau d'inclusió dels alumnes i del funcionament general del centre i per altra banda, una intervenció a la pròpia aula USEE a través d'un taller de ceràmica, el qual em va permetre valorar el sentiment de pertinença dels alumnes i treballar amb ells temes com l'autoconcepte, l'aprenentatge constructiu, les habilitats socials i les estratègies d'aprenentatge. He pogut constatar com una USEE és un recurs facilitador del model inclusiu si es donen algunes condicions fonamentals com aquelles que afecten a la cultura de centre. Finalment, el treball aporta algunes idees per orientar el centre cap a una millora en la seva cultura inclusiva.

Women in police services in the EU: facts and figures 2012

The Institute for Public Security of Catalonia (ISPC), the only state-funded education and research centre for police in Catalonia-Spain, developed in 2012 a comparative study on Gender diversity in police services in the European Union. The study is an update of the research Facts & Figures 2008 that was carried out by the European Network of Policewomen (ENP), a non-profit organization that works in partnership with colleagues from police and/or law enforcement organizations in its member countries to facilitate positive changes in the position of women in police services. To gather the 2012 data, the ISPC invited EU Member States’ police services to cooperate in the study answering a 10- ITEM questionnaire. The questionnaire was the same tool used in 2008 by the ENP. In February 2012, the ISPC sent the questionnaires through Cepol National Contact Points’ network. In order to include as many police services as possible in the study, the ENP also supported us to gather some of the data. Altogether we received questionnaires from 29 police services corresponding to 17 UE countries. Besides, we used data from open sources about England and Wales police services and the French National Police. In this document you can find: first, the tool we used to collect the data; second, the answers we gathered presented per country; finally, some comparative tables and graphics developed by the ISPC. Countries: Austria, Belgium Cyprus, Denmark, England, Wales, Estonia, Finland, France, Germany, Italy, Latvia, Lithuania, Luxembourg, Netherlands, Portugal, Romania, Slovenia, Spain, Swden.

Algorithmic aspects of bio-inspired string operations

We present building blocks for algorithms for the efficient reduction of square factor, i.e. direct repetitions in strings. So the basic problem is this: given a string, compute all strings that can be obtained by reducing factors of the form zz to z. Two types of algorithms are treated: an offline algorithm is one that can compute a data structure on the given string in advance before the actual search for the square begins; in contrast, online algorithms receive all input only at the time when a request is made. For offline algorithms we treat the following problem: Let u and w be two strings such that w is obtained from u by reducing a square factor zz to only z. If we further are given the suffix table of u, how can we derive the suffix table for w without computing it from scratch? As the suffix table plays a key role in online algorithms for the detection of squares in a string, this derivation can make the iterated reduction of squares more efficient. On the other hand, we also show how a suffix array, used for the offline detection of squares, can be adapted to the new string resulting from the deletion of a square. Because the deletion is a very local change, this adaption is more eficient than the computation of the new suffix array from scratch.

Impaired fast-spiking, suppressed cortical inhibition and increased susceptibility to seizures in mice lacking Kv3.2 K+ channel proteins

Voltage-gated K+ channels of the Kv3 subfamily have unusual electrophysiological properties, including activation at very depolarized voltages (positive to −10 mV) and very fast deactivation rates, suggesting special roles in neuronal excitability. In the brain, Kv3 channels are prominently expressed in select neuronal populations, which include fast-spiking (FS) GABAergic interneurons of the neocortex, hippocampus, and caudate, as well as other high-frequency firing neurons. Although evidence points to a key role in high-frequency firing, a definitive understanding of the function of these channels has been hampered by a lack of selective pharmacological tools. We therefore generated mouse lines in which one of the Kv3 genes, Kv3.2, was disrupted by gene-targeting methods. Whole-cell electrophysiological recording showed that the ability to fire spikes at high frequencies was impaired in immunocytochemically identified FS interneurons of deep cortical layers (5-6) in which Kv3.2 proteins are normally prominent. No such impairment was found for FS neurons of superficial layers (2-4) in which Kv3.2 proteins are normally only weakly expressed. These data directly support the hypothesis that Kv3 channels are necessary for high-frequency firing. Moreover, we found that Kv3.2 −/− mice showed specific alterations in their cortical EEG patterns and an increased susceptibility to epileptic seizures consistent with an impairment of cortical inhibitory mechanisms. This implies that, rather than producing hyperexcitability of the inhibitory interneurons, Kv3.2 channel elimination suppresses their activity. These data suggest that normal cortical operations depend on the ability of inhibitory interneurons to generate high-frequency firing.

New Trends in Public Facility Location Modeling

The past four decades have witnessed an explosive growth in the field of networkbased facility location modeling. This is not at all surprising since location policy is one of the most profitable areas of applied systems analysis in regional science and ample theoretical and applied challenges are offered. Location-allocation models seek the location of facilities and/or services (e.g., schools, hospitals, and warehouses) so as to optimize one or several objectives generally related to the efficiency of the system or to the allocation of resources. This paper concerns the location of facilities or services in discrete space or networks, that are related to the public sector, such as emergency services (ambulances, fire stations, and police units), school systems and postal facilities. The paper is structured as follows: first, we will focus on public facility location models that use some type of coverage criterion, with special emphasis in emergency services. The second section will examine models based on the P-Median problem and some of the issues faced by planners when implementing this formulation in real world locational decisions. Finally, the last section will examine new trends in public sector facility location modeling.

Are rules-based government programs shielded from special-interest politics? Evidence from revenue-sharing transfers in Brazil

Manipulation of government finances for the benefit of narrowly defined groups is usuallythought to be limited to the part of the budget over which politicians exercise discretion inthe short run, such as earmarks. Analyzing a revenue-sharing program between the centraland local governments in Brazil that uses an allocation formula based on local population estimates,I document two main results: first, that the population estimates entering the formulawere manipulated and second, that this manipulation was political in nature. Consistent withswing-voter targeting by the right-wing central government, I find that municipalities withroughly equal right-wing and non-right-wing vote shares benefited relative to opposition orconservative core support municipalities. These findings suggest that the exclusive focus ondiscretionary transfers in the extant empirical literature on special-interest politics may understatethe true scope of tactical redistribution that is going on under programmatic disguise.

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.

Parallel scheduling of multiclass M/M/m queues: Approximate and heavy-traffic optimization of achievable performance

We address the problem of scheduling a multiclass $M/M/m$ queue with Bernoulli feedback on $m$ parallel servers to minimize time-average linear holding costs. We analyze the performance of a heuristic priority-index rule, which extends Klimov's optimal solution to the single-server case: servers select preemptively customers with larger Klimov indices. We present closed-form suboptimality bounds (approximate optimality) for Klimov's rule, which imply that its suboptimality gap is uniformly bounded above with respect to (i) external arrival rates, as long as they stay within system capacity;and (ii) the number of servers. It follows that its relativesuboptimality gap vanishes in a heavy-traffic limit, as external arrival rates approach system capacity (heavy-traffic optimality). We obtain simpler expressions for the special no-feedback case, where the heuristic reduces to the classical $c \mu$ rule. Our analysis is based on comparing the expected cost of Klimov's ruleto the value of a strong linear programming (LP) relaxation of the system's region of achievable performance of mean queue lengths. In order to obtain this relaxation, we derive and exploit a new set ofwork decomposition laws for the parallel-server system. We further report on the results of a computational study on the quality of the $c \mu$ rule for parallel scheduling.

On certain greedoid polyhedra, partially indexable scheduling problems and extended restless bandit allocation indices

We present a polyhedral framework for establishing general structural properties on optimal solutions of stochastic scheduling problems, where multiple job classes vie for service resources: the existence of an optimal priority policy in a given family, characterized by a greedoid(whose feasible class subsets may receive higher priority), where optimal priorities are determined by class-ranking indices, under restricted linear performance objectives (partial indexability). This framework extends that of Bertsimas and Niño-Mora (1996), which explained the optimality of priority-index policies under all linear objectives (general indexability). We show that, if performance measures satisfy partial conservation laws (with respect to the greedoid), which extend previous generalized conservation laws, then theproblem admits a strong LP relaxation over a so-called extended greedoid polytope, which has strong structural and algorithmic properties. We present an adaptive-greedy algorithm (which extends Klimov's) taking as input the linear objective coefficients, which (1) determines whether the optimal LP solution is achievable by a policy in the given family; and (2) if so, computes a set of class-ranking indices that characterize optimal priority policies in the family. In the special case of project scheduling, we show that, under additional conditions, the optimal indices can be computed separately for each project (index decomposition). We further apply the framework to the important restless bandit model (two-action Markov decision chains), obtaining new index policies, that extend Whittle's (1988), and simple sufficient conditions for their validity. These results highlight the power of polyhedral methods (the so-called achievable region approach) in dynamic and stochastic optimization.