Sistema múltiplo de apoio à decisão para a programação de sistemas do tipo Job-Shop

Mestrado em Engenharia Electrotécnica e de Computadores

Job phasing aware preemption deferral

Preemptions account for a non-negligible overhead during system execution. There has been substantial amount of research on estimating the delay incurred due to the loss of working sets in the processor state (caches, registers, TLBs) and some on avoiding preemptions, or limiting the preemption cost. We present an algorithm to reduce preemptions by further delaying the start of execution of high priority tasks in fixed priority scheduling. Our approaches take advantage of the floating non-preemptive regions model and exploit the fact that, during the schedule, the relative task phasing will differ from the worst-case scenario in terms of admissible preemption deferral. Furthermore, approximations to reduce the complexity of the proposed approach are presented. Substantial set of experiments demonstrate that the approach and approximations improve over existing work, in particular for the case of high utilisation systems, where savings of up to 22% on the number of preemption are attained.

A genetic algorithm for the job shop scheduling with a new local search using Monte Carlo method

This paper presents a methodology for applying scheduling algorithms using Monte Carlo simulation. The methodology is based on a decision support system (DSS). The proposed methodology combines a genetic algorithm with a new local search using Monte Carlo Method. The methodology is applied to 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 methodology is tested on a set of standard instances taken from the literature and compared with others. The computation results validate the effectiveness of the proposed methodology. The DSS developed can be utilized in a common industrial or construction environment.

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.

Wii-Workouts on Chronic Pain, Physical Capabilities and Mood of Older Women: A Randomized Controlled Double Blind Trial

Chronic Low Back Pain (CLBP) is a public health problem and older women have higher incidence of this symptom, which affect body balance, functional capacity and behavior. The purpose of this study was to verifying the effect of exercises with Nintendo Wii on CLBP, functional capacity and mood of elderly. Thirty older women (68 ± 4 years; 68 ± 12 kg; 154 ± 5 cm) with CLBP participated in this study. Elderly individuals were divided into a Control Exercise Group (n = 14) and an Experimental Wii Group (n = 16). Control Exercise Group did strength exercises and core training, while Experimental Wii Group did ones additionally to exercises with Wii. CLBP, balance, functional capacity and mood were assessed pre and post training by the numeric pain scale, Wii Balance Board, sit to stand test and Profile of Mood States, respectively. Training lasted eight weeks and sessions were performed three times weekly. MANOVA 2 x 2 showed no interaction on pain, siting, stand-up and mood (P = 0.53). However, there was significant difference within groups (P = 0.0001). ANOVA 2 x 2 showed no interaction for each variable (P > 0.05). However, there were significant differences within groups in these variables (P < 0.05). Tukey's post-hoc test showed significant difference in pain on both groups (P = 0.0001). Wilcoxon and Mann-Whitney tests identified no significant differences on balance (P > 0.01). Capacity to Sit improved only in Experimental Wii Group (P = 0.04). In conclusion, physical exercises with Nintendo Wii Fit Plus additional to strength and core training were effective only for sitting capacity, but effect size was small.

Estudo e análise do sequenciamento de tarefas de produção: job shop scheduling

Esta dissertação apresenta um estudo sobre os problemas de sequenciamento de tarefas de produção do tipo job shop scheduling. Os problemas de sequenciamento de tarefas de produção pretendem encontrar a melhor sequência para o processamento de uma lista de tarefas, o instante de início e término de cada tarefa e a afetação de máquinas para as tarefas. Entre estes, encontram-se os problemas com máquinas paralelas, os problemas job shop e flow shop. As medidas de desempenho mais comuns são o makespan (instante de término da execução de todas as tarefas), o tempo de fluxo total, a soma dos atrasos (tardiness), o atraso máximo, o número de tarefas que são completadas após a data limite, entre outros. Num problema do tipo job shop, as tarefas (jobs) consistem num conjunto de operações que têm de ser executadas numa máquina pré-determinada, obedecendo a um determinado sequenciamento com tempos pré-definidos. Estes ambientes permitem diferentes cenários de sequenciamento das tarefas. Normalmente, não são permitidas interrupções no processamento das tarefas (preemption) e pode ainda ser necessário considerar tempos de preparação dependentes da sequência (sequence dependent setup times) ou atribuir pesos (prioridades) diferentes em função da importância da tarefa ou do cliente. Pretende-se o estudo dos modelos matemáticos existentes para várias variantes dos problemas de sequenciamento de tarefas do tipo job shop e a comparação dos resultados das diversas medidas de desempenho da produção. Este trabalho contribui para demonstrar a importância que um bom sequenciamento da produção pode ter na sua eficiência e consequente impacto financeiro.