Balanceamento de linhas de produção usando algoritmos genéticos

Aquando da definição de um layout por fluxo de produto, ou linha de produção, é necessário proceder-se à melhor selecção de combinações de tarefas a serem executadas em cada estação / posto de trabalho para que o trabalho seja executado numa sequência exequível e sejam necessárias quantidades de tempo aproximadamente iguais em cada estação / posto de trabalho. Este processo é chamado de balanceamento da linha de produção. Verifica-se que as estações de trabalho e equipamentos podem ser combinados de muitas maneiras diferentes; daí que a necessidade de efectuar o balanceamento das linhas de produção implique a distribuição de actividades sequenciais por postos de trabalho de modo a permitir uma elevada utilização de trabalho e de equipamentos e a minimizar o tempo de vazio. Os problemas de balanceamento de linhas são tipicamente problemas complexos de tratar, devido ao elevado número de combinações possíveis. Entre os métodos utilizados para resolver estes problemas encontram-se métodos de tentativa e erro, métodos heurísticos, métodos computacionais de avaliação de diferentes opções até se encontrar uma boa solução e métodos de optimização. O objectivo deste trabalho passou pelo desenvolvimento de uma ferramenta computacional para efectuar o balanceamento de linhas de produção recorrendo a algoritmos genéticos. Foi desenvolvida uma aplicação que implementa dois algoritmos genéticos, um primeiro que obtém soluções para o problema e um segundo que optimiza essas soluções, associada a uma interface gráfica em C# que permite a inserção do problema e a visualização de resultados. Obtiveram-se resultados exequíveis demonstrando vantagens em relação aos métodos heurísticos, pois é possível obter-se mais do que uma solução. Além disso, para problemas complexos torna-se mais prático o uso da aplicação desenvolvida. No entanto, esta aplicação permite no máximo seis precedências por cada operação e resultados com o máximo de nove estações de trabalho.

Auditoria dos sistemas de informação das instituições financeiras

Mestrado em Contabilidade e Gestão das Instituições Financeiras

Desenvolvimento do conceito de ângulo: um estudo no 5.ºano de escolaridade

A investigação em curso visa compreender a influência da implementação de um conjunto de tarefas no desenvolvimento do conceito de ângulo em alunos do 5.º ano de escolaridade, procurando responder às seguintes questões: a) Que conceções revelam alunos do 5.º ano de escolaridade relativamente ao conceito de ângulo?; b) Que estratégias utilizam os alunos do 5.º ano de escolaridade na exploração das tarefas utilizadas?; e c) Que aspetos do conceito de ângulo são desenvolvidos pelos alunos através da realização das tarefas propostas? A presente comunicação incide na primeira questão do estudo. Optou-se por uma abordagem metodológica qualitativa de paradigma interpretativo com a modalidade de experiência de ensino. Selecionou-se quatro alunos para constituir o grupo-alvo. Procedeu-se à avaliação diagnóstica das conceções de ângulo dos quatro alunos através da realização, no 1.º Período do ano letivo de 2011/12, de entrevistas clínicas semiestruturadas individuais, gravadas em vídeo. Além das entrevistas, foram usadas, como técnicas de recolha de dados, a observação participante das aulas, videogravadas, bem como a análise de documentos. Para analisar os dados, foram elaboradas categorias analíticas. Os resultados relativos à avaliação diagnóstica evidenciam conceções erradas de ângulo e respetiva amplitude: (a) os ângulos são os lados de polígonos (1 aluna); (b) o comprimento dos segmentos representativos dos lados está relacionado com o tamanho dos ângulos (2 alunos); (c) o comprimento do arco marcando o ângulo está relacionado com o tamanho dos ângulos (3 alunos); (d) nos polígonos côncavos, sãoângulos apenas os de amplitude inferior a 1800 (3 alunos); (e) em figuras que não são polígonos, os ângulos são os espaços entre os segmentos de reta e as linhas curvas (1 aluno); (f) o ângulo é a área entre dois segmentos representativos dos lados (4 alunos); e (g) os ângulos retos são apenas os posicionados na posição usual horizontal/vertical (1 aluna).

Medidas anti-crise e a motivação : estudo no contexto de uma empresa multinacional de prestação de serviços

Mestrado em Gestão e Empreendedorismo

Supporting intra-task parallelism in real-time multiprocessor systems

Os sistemas de tempo real modernos geram, cada vez mais, cargas computacionais pesadas e dinâmicas, começando-se a tornar pouco expectável que sejam implementados em sistemas uniprocessador. Na verdade, a mudança de sistemas com um único processador para sistemas multi- processador pode ser vista, tanto no domínio geral, como no de sistemas embebidos, como uma forma eficiente, em termos energéticos, de melhorar a performance das aplicações. Simultaneamente, a proliferação das plataformas multi-processador transformaram a programação paralela num tópico de elevado interesse, levando o paralelismo dinâmico a ganhar rapidamente popularidade como um modelo de programação. A ideia, por detrás deste modelo, é encorajar os programadores a exporem todas as oportunidades de paralelismo através da simples indicação de potenciais regiões paralelas dentro das aplicações. Todas estas anotações são encaradas pelo sistema unicamente como sugestões, podendo estas serem ignoradas e substituídas, por construtores sequenciais equivalentes, pela própria linguagem. Assim, o modo como a computação é na realidade subdividida, e mapeada nos vários processadores, é da responsabilidade do compilador e do sistema computacional subjacente. Ao retirar este fardo do programador, a complexidade da programação é consideravelmente reduzida, o que normalmente se traduz num aumento de produtividade. Todavia, se o mecanismo de escalonamento subjacente não for simples e rápido, de modo a manter o overhead geral em níveis reduzidos, os benefícios da geração de um paralelismo com uma granularidade tão fina serão meramente hipotéticos. Nesta perspetiva de escalonamento, os algoritmos que empregam uma política de workstealing são cada vez mais populares, com uma eficiência comprovada em termos de tempo, espaço e necessidades de comunicação. Contudo, estes algoritmos não contemplam restrições temporais, nem outra qualquer forma de atribuição de prioridades às tarefas, o que impossibilita que sejam diretamente aplicados a sistemas de tempo real. Além disso, são tradicionalmente implementados no runtime da linguagem, criando assim um sistema de escalonamento com dois níveis, onde a previsibilidade, essencial a um sistema de tempo real, não pode ser assegurada. Nesta tese, é descrita a forma como a abordagem de work-stealing pode ser resenhada para cumprir os requisitos de tempo real, mantendo, ao mesmo tempo, os seus princípios fundamentais que tão bons resultados têm demonstrado. Muito resumidamente, a única fila de gestão de processos convencional (deque) é substituída por uma fila de deques, ordenada de forma crescente por prioridade das tarefas. De seguida, aplicamos por cima o conhecido algoritmo de escalonamento dinâmico G-EDF, misturamos as regras de ambos, e assim nasce a nossa proposta: o algoritmo de escalonamento RTWS. Tirando partido da modularidade oferecida pelo escalonador do Linux, o RTWS é adicionado como uma nova classe de escalonamento, de forma a avaliar na prática se o algoritmo proposto é viável, ou seja, se garante a eficiência e escalonabilidade desejadas. Modificar o núcleo do Linux é uma tarefa complicada, devido à complexidade das suas funções internas e às fortes interdependências entre os vários subsistemas. Não obstante, um dos objetivos desta tese era ter a certeza que o RTWS é mais do que um conceito interessante. Assim, uma parte significativa deste documento é dedicada à discussão sobre a implementação do RTWS e à exposição de situações problemáticas, muitas delas não consideradas em teoria, como é o caso do desfasamento entre vários mecanismo de sincronização. Os resultados experimentais mostram que o RTWS, em comparação com outro trabalho prático de escalonamento dinâmico de tarefas com restrições temporais, reduz significativamente o overhead de escalonamento através de um controlo de migrações, e mudanças de contexto, eficiente e escalável (pelo menos até 8 CPUs), ao mesmo tempo que alcança um bom balanceamento dinâmico da carga do sistema, até mesmo de uma forma não custosa. Contudo, durante a avaliação realizada foi detetada uma falha na implementação do RTWS, pela forma como facilmente desiste de roubar trabalho, o que origina períodos de inatividade, no CPU em questão, quando a utilização geral do sistema é baixa. Embora o trabalho realizado se tenha focado em manter o custo de escalonamento baixo e em alcançar boa localidade dos dados, a escalonabilidade do sistema nunca foi negligenciada. Na verdade, o algoritmo de escalonamento proposto provou ser bastante robusto, não falhando qualquer meta temporal nas experiências realizadas. Portanto, podemos afirmar que alguma inversão de prioridades, causada pela sub-política de roubo BAS, não compromete os objetivos de escalonabilidade, e até ajuda a reduzir a contenção nas estruturas de dados. Mesmo assim, o RTWS também suporta uma sub-política de roubo determinística: PAS. A avaliação experimental, porém, não ajudou a ter uma noção clara do impacto de uma e de outra. No entanto, de uma maneira geral, podemos concluir que o RTWS é uma solução promissora para um escalonamento eficiente de tarefas paralelas com restrições temporais.

Localização de páginas web do conceito ao processo

Conceitos como Globalização, Internacionalização, Localização e Tradução surgem, na realidade da indústria da língua, com uma grande interligação, mas com perspectivas nem sempre concordantes. O nosso trabalho analisa, por isso, as diferentes definições propostas dedicando especial atenção ao conceito de localização, uma vez que o nosso projecto analisa o processo de localização de uma página Web desenvolvido num contexto empresarial real. O nosso enfoque recai mais específicamente sobre a localização de páginas Web, objecto do nosso projecto, identificando não só as suas particularidades, como também os intervenientes e o tipo de competências necessárias para o desenvolvimento de um trabalho nesta área da tradução e as ferramentas disponíveis para o profissional da tradução/ localização, de que se destacam as freeware. O processo de localização impõe metas de qualidade exigentes, pelo que, partindo da definição do conceito de qualidade, analisamos o tipo de requisitos necessários a uma correcta definição de tarefas e objectivos no contexto da localização. Esta definição de conceitos e a análise do processo de localização suportaram, em seguida, o desenvolvimento do objecto do nosso projecto - o processo de localização da página Web da empresa Pinto & Cruz, ao mesmo tempo que permitiram uma prévia identificação de todos os passos a desenvolver e do tipo de dificuldades e problemas a enfrentar. Assim, e em função das condicionantes impostas pelo modelo de gestão da página, definimos um fluxo de trabalho, em que identificamos as diferentes fases e intervenientes, mediante a utilização de uma plataforma de trabalho disponibilizada pelo webmaster do sítio em questão. O processo seguido para a localização da página é descrito, as suas especificidades documentadas e as dúvidas e dificuldades identificadas. Pretendeu-se, com o desenvolvimento deste projecto e com a descrição feita sistematizar uma abordagem ao processo e alertar para o tipo de dificuldades inerentes à sua prossecução, sobretudo para quem se dispõem a fazê-lo pela primeira vez.

Aplicação prática dos pilares da gestão numa fundação: melhoria de processos e procedimentos

Mestrado em Controlo de Gestão e dos Negócios

Laxity dynamics and LLF schedulability analysis on multiprocessor platforms

LLF (Least Laxity First) scheduling, which assigns a higher priority to a task with a smaller laxity, has been known as an optimal preemptive scheduling algorithm on a single processor platform. However, little work has been made to illuminate its characteristics upon multiprocessor platforms. In this paper, we identify the dynamics of laxity from the system’s viewpoint and translate the dynamics into LLF multiprocessor schedulability analysis. More specifically, we first characterize laxity properties under LLF scheduling, focusing on laxity dynamics associated with a deadline miss. These laxity dynamics describe a lower bound, which leads to the deadline miss, on the number of tasks of certain laxity values at certain time instants. This lower bound is significant because it represents invariants for highly dynamic system parameters (laxity values). Since the laxity of a task is dependent of the amount of interference of higher-priority tasks, we can then derive a set of conditions to check whether a given task system can go into the laxity dynamics towards a deadline miss. This way, to the author’s best knowledge, we propose the first LLF multiprocessor schedulability test based on its own laxity properties. We also develop an improved schedulability test that exploits slack values. We mathematically prove that the proposed LLF tests dominate the state-of-the-art EDZL tests. We also present simulation results to evaluate schedulability performance of both the original and improved LLF tests in a quantitative manner.

Convex optimization framework for intermediate deadline assignment in soft and hard real-time distributed systems

It is generally challenging to determine end-to-end delays of applications for maximizing the aggregate system utility subject to timing constraints. Many practical approaches suggest the use of intermediate deadline of tasks in order to control and upper-bound their end-to-end delays. This paper proposes a unified framework for different time-sensitive, global optimization problems, and solves them in a distributed manner using Lagrangian duality. The framework uses global viewpoints to assign intermediate deadlines, taking resource contention among tasks into consideration. For soft real-time tasks, the proposed framework effectively addresses the deadline assignment problem while maximizing the aggregate quality of service. For hard real-time tasks, we show that existing heuristic solutions to the deadline assignment problem can be incorporated into the proposed framework, enriching their mathematical interpretation.

Adding local priority-based dispatching mechanisms to P-NET networks: a fixed priority approach

In this paper we address the real-time capabilities of P-NET, which is a multi-master fieldbus standard based on a virtual token passing scheme. We show how P-NET’s medium access control (MAC) protocol is able to guarantee a bounded access time to message requests. We then propose a model for implementing fixed prioritybased dispatching mechanisms at each master’s application level. In this way, we diminish the impact of the first-come-first-served (FCFS) policy that P-NET uses at the data link layer. The proposed model rises several issues well known within the real-time systems community: message release jitter; pre-run-time schedulability analysis in non pre-emptive contexts; non-independence of tasks at the application level. We identify these issues in the proposed model and show how results available for priority-based task dispatching can be adapted to encompass priority-based message dispatching in P-NET networks.

Projecto de avaliação de interfaces – PAI

Para obtenção do grau de Doutor pela Universidade de Vigo com menção internacional Departamento de Informática

Software transactional memory as a building block for parallel embedded realtime systems

The recent trends of chip architectures with higher number of heterogeneous cores, and non-uniform memory/non-coherent caches, brings renewed attention to the use of Software Transactional Memory (STM) as a fundamental building block for developing parallel applications. Nevertheless, although STM promises to ease concurrent and parallel software development, it relies on the possibility of aborting conflicting transactions to maintain data consistency, which impacts on the responsiveness and timing guarantees required by embedded real-time systems. In these systems, contention delays must be (efficiently) limited so that the response times of tasks executing transactions are upper-bounded and task sets can be feasibly scheduled. In this paper we assess the use of STM in the development of embedded real-time software, defending that the amount of contention can be reduced if read-only transactions access recent consistent data snapshots, progressing in a wait-free manner. We show how the required number of versions of a shared object can be calculated for a set of tasks. We also outline an algorithm to manage conflicts between update transactions that prevents starvation.

A capacity sharing and stealing strategy for open real-time systems

This paper focuses on the scheduling of tasks with hard and soft real-time constraints in open and dynamic real-time systems. It starts by presenting a capacity sharing and stealing (CSS) strategy that supports the coexistence of guaranteed and non-guaranteed bandwidth servers to efficiently handle soft-tasks’ overloads by making additional capacity available from two sources: (i) reclaiming unused reserved capacity when jobs complete in less than their budgeted execution time and (ii) stealing reserved capacity from inactive non-isolated servers used to schedule best-effort jobs. CSS is then combined with the concept of bandwidth inheritance to efficiently exchange reserved bandwidth among sets of inter-dependent tasks which share resources and exhibit precedence constraints, assuming no previous information on critical sections and computation times is available. The proposed Capacity Exchange Protocol (CXP) has a better performance and a lower overhead when compared against other available solutions and introduces a novel approach to integrate precedence constraints among tasks of open real-time systems.

Linearizability and schedulability

Consider the problem of scheduling a set of tasks on a single processor such that deadlines are met. Assume that tasks may share data and that linearizability, the most common correctness condition for data sharing, must be satisfied. We find that linearizability can severely penalize schedulability. We identify, however, two special cases where linearizability causes no or not too large penalty on schedulability.

Management Structure and Work Team Processes; Responsibilities and Responsiveness

This paper explores the management structure of the team-based organization. First it provides a theoretical model of structures and processes of work teams. The structure determines the team’s responsibilities in terms of authority and expertise about specific regulation tasks. The responsiveness of teams to these responsibilities are the processes of teamwork, in terms of three dimensions, indicating to what extent teams indeed use the space provided to them. The research question that this paper addresses is to what extent the position of responsibilities in the team-based organization affect team responsiveness. This is done by two hypotheses. First, the effect of the so-called proximity of regulation tasks is tested. It is expected that the responsibility for tasks positioned higher in the organization (i.e. further from the team) generally has a negative effect on team responsiveness, whereas tasks positioned lower in the organization (i.e. closer to the team) will have a positive effect on the way in which teams respond. Second, the relationship between the number of tasks for which the team is responsible with team responsiveness is tested. Theory suggests that teams being responsible for a larger number of tasks perform better, i.e. show higher responsiveness. These hypotheses are tested by a study of 109 production teams in the automotive industry. The results show that, as the theory predicts, increasing numbers of responsibilities have positive effects on team responsiveness. However, the delegation of expertise to teams seems to be the most important predictor of responsiveness. Also, not all regulation tasks show to have effects on team responsiveness. Most tasks do not show to have any significant effect at all. A number of tasks affects team responsiveness positively, when their responsibility is positioned lower in the organization, but also a number of tasks affects team responsiveness positively when located higher in the organization, i.e. further from the teams in the production. The results indicate that more attention can be paid to the distribution of responsibilities, in particular expertise, to teams. Indeed delegating more expertise improve team responsiveness, however some tasks might be located better at higher organizational levels, indicating that there are limitations to what responsibilities teams can handle.