Comparison of Work Scheduling Using Constraint Programming or Auctions

Business processes designers take into account the resources that the processes would need, but, due to the variable cost of certain parameters (like energy) or other circumstances, this scheduling must be done when business process enactment. In this report we formalize the energy aware resource cost, including time and usage dependent rates. We also present a constraint programming approach and an auction-based approach to solve the mentioned problem including a comparison of them and a comparison of the proposed algorithms for solving them

Vehículos-robot de guiado automático para almacenes y plantas de manufacturación

En este proyecto de final de carrera se realiza la gestión del tráfico de AGV y la simulación de su comportamiento al circular por una planta de estudio. Con la simulación se puede ver como varía el comportamiento de la planta al modificar el número de AGV y la velocidad a la que circulan. La planta objeto de estudio es un laboratorio de análisis clínico en el que se ha sustituido el sistema de transporte interno basado en cintas por uno con AGV, con lo que se ha podido comprobar que dicha sustitución es factible.

Sistema d'AGV (vehicles-robot de guiatge automàtic) per a magatzems i plantes de manufactura

Una de les solucions per a minimitzar els costos de producció o d'emmagatzematge és automatitzarne la logística interna. Per dissenyar les aplicacions corresponents és convenient poder validar-les amb un prototipatge. Això ha motivat la realització d'aquest projecte, on s'ha obtingut un prototip d'AGV (automated guided vehicle) que rep les ordres per Bluetooth i, mitjançant uns infrarojos per poder seguir unes línies al terra, és capaç d'anar des del punt inicial fins on se li ha encarregat i tornar al punt inicial. Aquest vehicle pot servir de base per a la implementació d'AGV orientats a aplicacions reals i, per tant, per a la construcció de sistemes més grans i que poden ser utilitzats en plantes de producció, laboratoris, magatzems, ports i d'altres aplicacions diverses.

Assembling genes from predicted exons in linear time with dynamic programming

In a number of programs for gene structure prediction in higher eukaryotic genomic sequences, exon prediction is decoupled from gene assembly: a large pool of candidate exons is predicted and scored from features located in the query DNA sequence, and candidate genes are assembled from such a pool as sequences of nonoverlapping frame-compatible exons. Genes are scored as a function of the scores of the assembled exons, and the highest scoring candidate gene is assumed to be the most likely gene encoded by the query DNA sequence. Considering additive gene scoring functions, currently available algorithms to determine such a highest scoring candidate gene run in time proportional to the square of the number of predicted exons. Here, we present an algorithm whose running time grows only linearly with the size of the set of predicted exons. Polynomial algorithms rely on the fact that, while scanning the set of predicted exons, the highest scoring gene ending in a given exon can be obtained by appending the exon to the highest scoring among the highest scoring genes ending at each compatible preceding exon. The algorithm here relies on the simple fact that such highest scoring gene can be stored and updated. This requires scanning the set of predicted exons simultaneously by increasing acceptor and donor position. On the other hand, the algorithm described here does not assume an underlying gene structure model. Indeed, the definition of valid gene structures is externally defined in the so-called Gene Model. The Gene Model specifies simply which gene features are allowed immediately upstream which other gene features in valid gene structures. This allows for great flexibility in formulating the gene identification problem. In particular it allows for multiple-gene two-strand predictions and for considering gene features other than coding exons (such as promoter elements) in valid gene structures.

Spacial debris collector robot : An AI-based and autonomous debris collector satellite simulation

In this paper the core functions of an artificial intelligence (AI) for controlling a debris collector robot are designed and implemented. Using the robot operating system (ROS) as the base of this work a multi-agent system is built with abilities for task planning.

Integració d’ una unitat inercial i d’ un giroscopi de fibra òptica en un robot submarí i desenvolupament d’ un sistema de posicionament dins una piscina

El Grup de Visió per Computador i Robòtica (VICOROB) del departament d'Electrònica, Informàtica i Automàtica de la Universitat de Girona investiga en el camp de la robòtica submarina. Al CIRS (Centre d’Investigació en Robòtica Submarina), laboratori que forma part del grup VICOROB, el robot submarí Ictineu és la principal eina utilitzada per a desenvolupar els projectes de recerca. Recentment, el CIRS ha adquirit un nou sistema de sensors d' orientació basat en una unitat inercial i un giroscopi de fibra òptica. Aquest projecte pretén realitzar un estudi d' aquests dispositius i integrar-los al robot Ictineu. D' altra banda, aprofitant les característiques d’aquests sensors giroscopics i les mesures d' un sonar ja integrat al robot, es vol desenvolupar un sistema de localització capaç de determinar la posició del robot en el pla horitzontal de la piscina en temps real

Entorn de programació pel robot Stäubli mitjantçant MatLab, aplicació a un sistema de recol·lecció de peces basat en visió artificial

Els objectius del projecte són: realitzar un intèrpret de comandes en VAL3 que rebi les ordres a través d’una connexió TCP/IP; realitzar una toolbox de Matlab per enviar diferents ordres mitjançant una connexió TCP/IP; adquirir i processar mitjançant Matlab imatges de la càmera en temps real i detectar la posició d’objectes artificials mitjançant la segmentació per color i dissenyar i realitzar una aplicació amb Matlab que reculli peces detectades amb la càmera. L’abast del projecte inclou: l’estudi del llenguatge de programació VAL3 i disseny de l’ intèrpret de comandes, l’estudi de les llibreries de Matlab per comunicació mitjançant TCP/IP, per l’adquisició d’imatges, pel processament d’imatges i per la programació en C; el disseny de la aplicació recol·lectora de peces i la implementació de: un intèrpret de comandes en VAL3, la toolbox pel control del robot STAUBLI en Matlab i la aplicació recol·lectora de peces mitjançant el processament d’imatges en temps real també en Matlab

Control de posició del robot wifibot

Aquest projecte pretén presentar de forma clara i detallada l’estructura i el funcionament del robot així com dels components que el conformen. Aquesta informació és de vital importància a l’hora de desenvolupar aplicacions per al robot. Un cop descrites les característiques del robot s’analitzaran les eines necessàries i/o disponibles per poder desenvolupar programari per cada nivell de la forma més senzilla i eficient possible. Posteriorment s’analitzaran els diferents nivells de programació i se’n contrastaran els avantatges i els inconvenients de cada un. Aquest anàlisi es començarà fent pel nivell més alt i anirà baixant amb la intenció de no entrar en nivells més baixos del necessari. Baixar un nivell en la programació suposa haver de crear aplicacions sempre compatibles amb els nivells superiors de forma que com més es baixa més augmenta la complexitat. A partir d’aquest anàlisi s’ha arribat a la conclusió que per tal d’aprofitar totes les prestacions del robot és precís arribar a programar en el nivell més baix del robot. Finalment l’objectiu és obtenir una sèrie de programes per cada nivell que permetin controlar el robot i fer-lo seguir senzilles trajectòries

A randomized concave programming method for choice network revenue management

Models incorporating more realistic models of customer behavior, as customers choosing froman offer set, have recently become popular in assortment optimization and revenue management.The dynamic program for these models is intractable and approximated by a deterministiclinear program called the CDLP which has an exponential number of columns. However, whenthe segment consideration sets overlap, the CDLP is difficult to solve. Column generationhas been proposed but finding an entering column has been shown to be NP-hard. In thispaper we propose a new approach called SDCP to solving CDLP based on segments and theirconsideration sets. SDCP is a relaxation of CDLP and hence forms a looser upper bound onthe dynamic program but coincides with CDLP for the case of non-overlapping segments. Ifthe number of elements in a consideration set for a segment is not very large (SDCP) can beapplied to any discrete-choice model of consumer behavior. We tighten the SDCP bound by(i) simulations, called the randomized concave programming (RCP) method, and (ii) by addingcuts to a recent compact formulation of the problem for a latent multinomial-choice model ofdemand (SBLP+). This latter approach turns out to be very effective, essentially obtainingCDLP value, and excellent revenue performance in simulations, even for overlapping segments.By formulating the problem as a separation problem, we give insight into why CDLP is easyfor the MNL with non-overlapping considerations sets and why generalizations of MNL posedifficulties. We perform numerical simulations to determine the revenue performance of all themethods on reference data sets in the literature.

A new compact linear programming formulation for choice network revenue management

The choice network revenue management model incorporates customer purchase behavioras a function of the offered products, and is the appropriate model for airline and hotel networkrevenue management, dynamic sales of bundles, and dynamic assortment optimization.The optimization problem is a stochastic dynamic program and is intractable. A certainty-equivalencerelaxation of the dynamic program, called the choice deterministic linear program(CDLP) is usually used to generate dyamic controls. Recently, a compact linear programmingformulation of this linear program was given for the multi-segment multinomial-logit (MNL)model of customer choice with non-overlapping consideration sets. Our objective is to obtaina tighter bound than this formulation while retaining the appealing properties of a compactlinear programming representation. To this end, it is natural to consider the affine relaxationof the dynamic program. We first show that the affine relaxation is NP-complete even for asingle-segment MNL model. Nevertheless, by analyzing the affine relaxation we derive a newcompact linear program that approximates the dynamic programming value function betterthan CDLP, provably between the CDLP value and the affine relaxation, and often comingclose to the latter in our numerical experiments. When the segment consideration sets overlap,we show that some strong equalities called product cuts developed for the CDLP remain validfor our new formulation. Finally we perform extensive numerical comparisons on the variousbounds to evaluate their performance.

On the throughput-WIP trade-off in queueing systems, diminishing returns and the threshold property: A linear programming approach

We present a new unifying framework for investigating throughput-WIP(Work-in-Process) optimal control problems in queueing systems,based on reformulating them as linear programming (LP) problems withspecial structure: We show that if a throughput-WIP performance pairin a stochastic system satisfies the Threshold Property we introducein this paper, then we can reformulate the problem of optimizing alinear objective of throughput-WIP performance as a (semi-infinite)LP problem over a polygon with special structure (a thresholdpolygon). The strong structural properties of such polygones explainthe optimality of threshold policies for optimizing linearperformance objectives: their vertices correspond to the performancepairs of threshold policies. We analyze in this framework theversatile input-output queueing intensity control model introduced byChen and Yao (1990), obtaining a variety of new results, including (a)an exact reformulation of the control problem as an LP problem over athreshold polygon; (b) an analytical characterization of the Min WIPfunction (giving the minimum WIP level required to attain a targetthroughput level); (c) an LP Value Decomposition Theorem that relatesthe objective value under an arbitrary policy with that of a giventhreshold policy (thus revealing the LP interpretation of Chen andYao's optimality conditions); (d) diminishing returns and invarianceproperties of throughput-WIP performance, which underlie thresholdoptimality; (e) a unified treatment of the time-discounted andtime-average cases.

Assessing an intuitive condition for stability under a range of traffic conditions via a generalised Lu-Kumar network

We argue the importance both of developing simple sufficientconditions for the stability of general multiclass queueing networks and also of assessing such conditions under a range of assumptions on the weight of the traffic flowing between service stations. To achieve the former, we review a peak-rate stability condition and extend its range of application and for the latter, we introduce a generalisation of the Lu-Kumar network on which the stability condition may be tested for a range of traffic configurations. The peak-rate condition is close to exact when the between-station traffic is light, but degrades as this traffic increases.

Deciding analytically or trusting your intuition? The advantadges and disadvantadges of analytic and intuitive thought

Recent research has highlighted the notion that people can make judgmentsand choices by means of two systems that are labeled here tacit(or intuitive) and deliberate (or analytic). Whereas most decisionstypically involve both systems, this chapter examines the conditions underwhich each system is liable to be more effective. This aims to illuminatethe age-old issue of whether and when people should trust intuition or analysis. To do this, a framework is presented to understand how thetacit and deliberate systems work in tandem. Distinctions are also madebetween the types of information typically used by both systems as wellas the characteristics of environments that facilitate or hinder accuratelearning by the tacit system. Next, several experiments that havecontrasted intuitive and analytic modes on the same tasks are reviewed.Together, the theoretical framework and experimental evidence leads tospecifying the trade-off that characterizes their relative effectiveness.Tacit system responses can be subject to biases. In making deliberate systemresponses, however, people might not be aware of the correct rule to dealwith the task they are facing and/or make errors in executing it. Whethertacit or deliberate responses are more valid in particular circumstancesrequires assessing this trade-off. In this, the probability of making errorsin deliberate thought is postulated to be a function of the analytical complexityof the task as perceived by the person. Thus the trade-off is one of bias (inimplicit responses) versus analytical complexity (when tasks are handled indeliberate mode). Finally, it is noted that whereas much attention has beenpaid in the past to helping people make decisions in deliberate mode, effortsshould also be directed toward improving ability to make decisions intacit mode since the effectiveness of decisions clearly depends on both. Thistherefore represents an important frontier for research.

Implementing TURF analysis through binary linear programming

This paper introduces the approach of using Total Unduplicated Reach and Frequency analysis (TURF) to design a product line through a binary linear programming model. This improves the efficiency of the search for the solution to the problem compared to the algorithms that have been used to date. The results obtained through our exact algorithm are presented, and this method shows to be extremely efficient both in obtaining optimal solutions and in computing time for very large instances of the problem at hand. Furthermore, the proposed technique enables the model to be improved in order to overcome the main drawbacks presented by TURF analysis in practice.

Restless bandits, linear programming relaxations and a primal-dual index heuristic

We develop a mathematical programming approach for the classicalPSPACE - hard restless bandit problem in stochastic optimization.We introduce a hierarchy of n (where n is the number of bandits)increasingly stronger linear programming relaxations, the lastof which is exact and corresponds to the (exponential size)formulation of the problem as a Markov decision chain, while theother relaxations provide bounds and are efficiently computed. Wealso propose a priority-index heuristic scheduling policy fromthe solution to the first-order relaxation, where the indices aredefined in terms of optimal dual variables. In this way wepropose a policy and a suboptimality guarantee. We report resultsof computational experiments that suggest that the proposedheuristic policy is nearly optimal. Moreover, the second-orderrelaxation is found to provide strong bounds on the optimalvalue.