Sporadic multiprocessor scheduling with few preemptions

Consider the problem of scheduling n sporadic tasks so as to meet deadlines on m identical processors. A task is characterised by its minimum interarrival time and its worst-case execution time. Tasks are preemptible and may migrate between processors. We propose an algorithm with limited migration, configurable for a utilisation bound of 88% with few preemptions (and arbitrarily close to 100% with more preemptions).

Collision-free prioritized medium access in the presence of hidden nodes without relying on out-of-band signaling

Consider the problem of sharing a wireless channel between a set of computer nodes. Hidden nodes exist and there is no base station. Each computer node hosts a set of sporadic message streams where a message stream releases messages with real-time deadlines. We propose a collision-free wireless medium access control (MAC) protocol which implements staticpriority scheduling. The MAC protocol allows multiple masters and is fully distributed. It neither relies on synchronized clocks nor out-of-band signaling; it is an adaptation to a wireless channel of the dominance protocol used in the CAN bus. But unlike that protocol, our protocol does not require a node having the ability to receive an incoming bit from the channel while transmitting to the channel. Our protocol has the key feature of not only being prioritized and collision-free but also dealing successfully with hidden nodes. This key feature enables schedulability analysis of sporadic message streams in multihop networks.

A genetic algorithm for the resource constrained multi-project scheduling problem

This paper presents a genetic algorithm for the resource constrained multi-project scheduling problem. The chromosome representation of the problem is based on random keys. The schedules are constructed using a heuristic that builds parameterized active schedules based on priorities, delay times, and release dates defined by the genetic algorithm. The approach is tested on a set of randomly generated problems. The computational results validate the effectiveness of the proposed algorithm.

Analysis of the domain of applicability of an algorithm for a resources system selection problem for Distributed/Agile/Virtual Enterprises integration

The process of resources systems selection takes an important part in Distributed/Agile/Virtual Enterprises (D/A/V Es) integration. However, the resources systems selection is still a difficult matter to solve in a D/A/VE, as it is pointed out in this paper. Globally, we can say that the selection problem has been equated from different aspects, originating different kinds of models/algorithms to solve it. In order to assist the development of a web prototype tool (broker tool), intelligent and flexible, that integrates all the selection model activities and tools, and with the capacity to adequate to each D/A/V E project or instance (this is the major goal of our final project), we intend in this paper to show: a formulation of a kind of resources selection problem and the limitations of the algorithms proposed to solve it. We formulate a particular case of the problem as an integer programming, which is solved using simplex and branch and bound algorithms, and identify their performance limitations (in terms of processing time) based on simulation results. These limitations depend on the number of processing tasks and on the number of pre-selected resources per processing tasks, defining the domain of applicability of the algorithms for the problem studied. The limitations detected open the necessity of the application of other kind of algorithms (approximate solution algorithms) outside the domain of applicability founded for the algorithms simulated. However, for a broker tool it is very important the knowledge of algorithms limitations, in order to, based on problem features, develop and select the most suitable algorithm that guarantees a good performance.

Adaptive tackling of the swinging problem for a 2 DOF crane – payload system

The control of a crane carrying its payload by an elastic string corresponds to a task in which precise, indirect control of a subsystem dynamically coupled to a directly controllable subsystem is needed. This task is interesting since the coupled degree of freedom has little damping and it is apt to keep swinging accordingly. The traditional approaches apply the input shaping technology to assist the human operator responsible for the manipulation task. In the present paper a novel adaptive approach applying fixed point transformations based iterations having local basin of attraction is proposed to simultaneously tackle the problems originating from the imprecise dynamic model available for the system to be controlled and the swinging problem, too. The most important phenomenological properties of this approach are also discussed. The control considers the 4th time-derivative of the trajectory of the payload. The operation of the proposed control is illustrated via simulation results.

A biased random-key genetic algorithm with forward-backward improvement for the resource constrained project scheduling problem

This paper presents a biased random-key genetic algorithm for the resource constrained project scheduling problem. The chromosome representation of the problem is based on random keys. Active schedules are constructed using a priority-rule heuristic in which the priorities of the activities are defined by the genetic algorithm. A forward-backward improvement procedure is applied to all solutions. The chromosomes supplied by the genetic algorithm are adjusted to reflect the solutions obtained by the improvement procedure. The heuristic is tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.

A two-level genetic algorithm for the multi-mode resource-constrained project scheduling problem

This paper presents a genetic algorithm for the multimode resource-constrained project scheduling problem (MRCPSP), in which multiple execution modes are available for each of the activities of the project. The objective function is the minimization of the construction project completion time. To solve the problem, is applied a two-level genetic algorithm, which makes use of two separate levels and extend the parameterized schedule generation scheme by introducing an improvement procedure. It is evaluated the quality of the schedule and present detailed comparative computational results for the MRCPSP, which reveal that this approach is a competitive algorithm.

Reverse problem-based learning - a case study with a Braille machine

Engineering Education includes not only teaching theoretical fundamental concepts but also its verification during practical lessons in laboratories. The usual strategies to carry out this action are frequently based on Problem Based Learning, starting from a given state and proceeding forward to a target state. The possibility or the effectiveness of this procedure depends on previous states and if the present state was caused or resulted from earlier ones. This often happens in engineering education when the achieved results do not match the desired ones, e.g. when programming code is being developed or when the cause of the wrong behavior of an electronic circuit is being identified. It is thus important to also prepare students to proceed in the reverse way, i.e. given a start state generate the explanation or even the principles that underlie it. Later on, this sort of skills will be important. For instance, to a doctor making a patient?s story or to an engineer discovering the source of a malfunction. This learning methodology presents pedagogical advantages besides the enhanced preparation of students to their future work. The work presented on his document describes an automation project developed by a group of students in an engineering polytechnic school laboratory. The main objective was to improve the performance of a Braille machine. However, in a scenario of Reverse Problem-Based learning, students had first to discover and characterize the entire machine's function before being allowed (and being able) to propose a solution for the existing problem.

Positive radial solutions of the Dirichlet problem for the Minkowski-Curvature equation in a ball

We study the existence and multiplicity of positive radial solutions of the Dirichlet problem for the Minkowski-curvature equation { -div(del upsilon/root 1-vertical bar del upsilon vertical bar(2)) in B-R, upsilon=0 on partial derivative B-R,B- where B-R is a ball in R-N (N >= 2). According to the behaviour off = f (r, s) near s = 0, we prove the existence of either one, two or three positive solutions. All results are obtained by reduction to an equivalent non-singular one-dimensional problem, to which variational methods can be applied in a standard way.

A random key based genetic algorithm for the resource constrained project scheduling problem

This paper presents a genetic algorithm for the Resource Constrained Project Scheduling Problem (RCPSP). The chromosome representation of the problem is based on random keys. The schedule is constructed using a heuristic priority rule in which the priorities of the activities are defined by the genetic algorithm. The heuristic generates parameterized active schedules. The approach was tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.

Otimização do processo produtivo de extrusão de pisos na E06

O presente trabalho foi elaborado no âmbito da Dissertação Final de Mestrado do curso de Engenharia Mecânica – Gestão Industrial do Instituto Superior de Engenharia do Porto. Este foi realizado numa empresa da indústria de pneus, a Continental Mabor S.A.. Nos dias atuais, a indústria esta cada vez mais competitiva, os custos e os prazos da entrega são cada vez mais reduzidos e a qualidade cada vez mais exigente, assim sendo, é imprescindível uma constante melhoria do sistema produtivo. Este fato fez com que o presente trabalho tivesse como principal objetivo determinar o estado atual e delinear um plano de melhoria para um equipamento (Extrusora de pisos nº6), recentemente instalado na fábrica mas oriundo de outra fábrica do grupo, recorrendo para tal ao Lean Manufacturing e a ferramentas que lhe estão associadas. Inicialmente realizou-se uma análise e diagnóstico ao processo de extrusão de pisos na Extrusora nº6, com o intuito de avaliar todas as suas ineficiências e ainda formular um plano de melhorias para a ineficiência de maior impacto no sistema produtivo. Esta análise foi realizada em diferentes turnos e diferentes equipas de trabalho de forma a se obter uma amostra mais representativa da realidade global. Após esta análise verificou-se que as principais ineficiências eram Setup, conformidade do material, dimensões e encravamentos, entre outros. Sendo que os Setup provocam um tempo de paragem de 101 minutos por turno, escolheu-se esta perturbação como o foco do plano de melhorias a realizar posteriormente. De forma a reduzir os tempos de mudança (Setup), o autor no presente trabalho utilizou ferramentas Lean Manufacturing, principalmente o SMED. Conjuntamente com o SMED ainda foram utilizadas outras ferramentas Lean Manufacturing tais como: 5S, Gestão Visual, Problem Solving e Normalização do Método de Trabalho. Após a implementação de todas estas ferramentas obteve-se uma redução de tempos de mudança de 43% com 1 operador e 71% com 2 operadores, ou seja, reduziu-se de 40,5 minutos gastos por turno para a mudança de fieira para 23,13 min e 11,79 min respetivamente, o que corresponde a um ganho monetário anual de 63.621€ ou 105.045€, respetivamente. Com este trabalho conclui-se que a utilização de ferramentas Lean Manufacturing contribuem para a redução dos desperdícios do processo produtivo. Por isso, espera-se que este estudo seja aplicado na Extrusora nº6 e nas restantes Extrusoras de pisos existentes na fábrica, e num futuro próximo que se realize estudos semelhantes em máquinas com diferentes funções.

Integrando problem frames com aspectos

Dissertação apresentada na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para obtenção do grau de Mestre em Engenharia Informática

An optimization approach for the job shop scheduling problem

This paper presents an optimization approach for the job shop scheduling problem (JSSP). The JSSP is a difficult problem in combinatorial optimization for which extensive investigation has been devoted to the development of efficient algorithms. The proposed approach is based on a genetic algorithm technique. The scheduling rules such as SPT and MWKR are integrated into the process of genetic evolution. The chromosome representation of the problem is based on random keys. The schedules are constructed using a priority rule in which the priorities and delay times of the operations are defined by the genetic algorithm. Schedules are constructed using a procedure that generates parameterized active schedules. After a schedule is obtained a local search heuristic is applied to improve the solution. The approach is tested on a set of standard instances taken from the literature and compared with other approaches. The computation results validate the effectiveness of the proposed approach.

A new approach to the initial value problem

5th Portuguese Conference on Automatic Control, September, 5-7, 2002, Aveiro, Portugal

Avaliação da satisfação do utente na comunicação com os profissionais de saúde construção e validação de um instrumento

A satisfação do utente na comunicação com profissionais de saúde é um indicador de qualidade dos serviços ou instituições. Na literatura não encontramos instrumentos padronizados e validados, que avaliem a satisfação do utente na comunicação com os profissionais de saúde. O presente estudo tem como objetivo construir e validar um instrumento para avaliar a satisfação do utente na comunicação com os profissionais de saúde. Desenvolvemos este estudo em três ciclos. Um primeiro, revisão da literatura, para identificar dimensões e itens da comunicação interpessoal na saúde. No segundo ciclo, conduzimos um método de Delphi modificado em três rondas, com recurso à plataforma informática de questionários Survey Monkey, no qual participou um painel de 25 peritos; estabelecemos como critério mínimo de retenção para a ronda seguinte os itens que recebessem 70% do consenso por parte do painel. Após as três rondas, obtivemos um instrumento com seis dimensões comunicacionais (comunicação verbal, comunicação não verbal, empatia, respeito, resolução de problemas e material de apoio), vinte e cinco itens específicos, e mais seis dimensões genéricas, que avaliam cada uma das dimensões. No terceiro ciclo avaliamos as características psicométricas, em termos de sensibilidade, validade do construto e fidelidade, numa amostra de 348 participantes. Os resultados mostram que todas as categorias de resposta estavam representadas em todos os itens. Validade do construto- a análise fatorial identificou uma solução de seis componentes que explicam 71% da variância total. Fiabilidade - os valores da correlação item-total variam entre 0,387 e 0,722, existindo uma correlação positiva moderada a forte. O valor de alfa de Cronbach (α=0,928) indica que a consistência interna é excelente. O instrumento construído apresenta boas propriedades psicométricas. Fica assim disponível uma nova ferramenta para auxiliar na gestão e no processo de planeamento necessários ao incremento da qualidade nos serviços e instituições de saúde.