Pesquisa Operacional : SciELO Brasil - Scientific Electronic Library Online

Nota de agradecimento

Galvão,Roberto Diéguez

Nota dos Editores Convidados

Minimizing flowtime subject to optimal makespan on two identical parallel machines

Gupta,Jatinder N. D.; Ho,Johnny C.

We consider the problem of scheduling jobs on two parallel identical machines where an optimal schedule is defined as one that gives the smallest total flowtime (the sum of the completion time of all jobs) among the set of schedules with optimal makespan (the completion time of the latest job). Utilizing an existing optimization algorithm for the minimization of makespan, we propose an algorithm to determine optimal schedules for this problem. We empirically show that the proposed algorithm c...

Algoritmo de programação de máquinas individuais com penalidades distintas de adiantamento e atraso

Colin,Emerson C.; Shimizu,Tamio

Neste trabalho consideramos o problema de máquina única, com datas de entrega e penalidades de adiantamento e atraso distintas para cada ordem. Considerando que a seqüência seja predefinida, o objetivo a ser alcançado é a minimização da soma das diferenças (adiantamentos ou atrasos) penalizadas das ordens. Este trabalho é apresentado como uma generalização do algoritmo de programação de Garey et al. (1988). Através de uma estrutura computacional denominada fila de prioridade, este novo algori...

Uma heurística de trocas para o problema de sequenciamento de tarefas em processadores uniformes

Müller,Felipe Martins; Limberger,Sergio João

O sequenciamento de tarefas independentes de forma não preemptiva em sistemas de processadores uniformes, com o objetivo de minimizar o tempo total de execução (makespan), é o assunto do presente artigo. Considera-se um conjunto de n tarefas, onde cada tarefa possui um tempo de processamento, e um conjunto m > ou = 2 de processadores com velocidades de processamento sigma1 = 1£s2<= ...£sm. Sendo o problema de encontrar o mínimo makespan consid...

GRASP para o PQA: um limite de aceitação para soluções iniciais

Range,Maria Cristina; Abreu,Nair Maria Maia de; Boaventura-Netto,Paulo Oswaldo

O Problema Quadrático de Alocação (PQA) pertence à classe dos problemas NP-Hard e desafia os pesquisadores tanto em sua teoria quanto em sua parte computacional. Pela sua alta complexidade muitos métodos heurísticos têm sido desenvolvidos para tentar resolvê-lo aproximadamente. A metaheurística GRASP (greedy randomized adaptive search procedures) se mostrou bastante eficiente. Neste trabalho, uma proposta para descartar soluções iniciais supostamente ruins é apresentada com base na normalizaç...

Um modelo para analisar o problema de filas em caixas de supermercados: um estudo de caso

Morabito,Reinaldo; Lima,Flavio C. R. de

Neste estudo aplicamos teoria de filas para analisar o problema de congestão em caixas de supermercados. Estamos particularmente interessados em modelar o tempo médio de espera em fila, aqui entendido como uma componente importante do nível de serviço ao consumidor, em função da capacidade do sistema (i.e., o número de caixas num dado período de tempo). Três modelos são explorados: (i) representar o sistema por meio de um simples modelo M/M/m de fila única, onde m é o número de caixas, (ii) r...

Estimação do parâmetro "d " em modelos arfima

Trevisan,Elma Suema; Souza,Reinaldo Castro; Souza,Leonardo Rocha

Os modelos ARFIMA caracterizam-se por sua longa dependência e por possuírem o parâmetro d do modelo ARIMA (grau de diferenciação) assumindo valores fracionários. Quando no caso d Î (-0,5; 0,5), há estacionariedade. A longa dependência aparece quando d é positivo. Este trabalho visa testar e comparar duas metodologias para o processo de estimação de d, baseadas na função Periodograma e na função Periodograma Suavizado. Através de séries sintéticas geradas para este fim...

O problema de roteamento no transporte escolar

O presente trabalho aborda o problema de roteamento no transporte escolar e descreve algumas técnicas da Pesquisa Operacional que podem ser utilizadas para solucioná-lo. O problema considera além das distâncias a serem percorridas por m veículos, a disponibilidade e capacidades destes e, além disso, as demandas em cada um dos n pontos de demanda. A implementação a um problema real é estudada e os resultados analisados.

Uma análise da influência da estocasticidade das informações sobre um modelo de programação linear

Volpi,Neida Maria Patias; Carnieri,Celso; Sanquetta,Carlos Roberto

Neste trabalho foi discutido o impacto de perturbações estocásticas em um modelo de planejamento florestal. Foi desenvolvido um modelo de programação linear e uma abordagem, através de simulações estocásticas, para analisar e quantificar a variabilidade que ocorre nos valores da função objetivo, perante a natureza estocástica dos dados que alimentam o modelo. Um programa para efetuar tais simulações foi desenvolvido. O conceito de razão de variabilidade objeto-sistema foi introduzido para med...

An algorithm for determining the K-best solutions of the one-dimensional Knapsack problem

Yanasse,Horacio Hideki; Soma,Nei Yoshihiro; Maculan,Nelson

In this work we present an enumerative scheme for determining the K-best solutions (K > 1) of the one dimensional knapsack problem. If n is the total number of different items and b is the knapsack's capacity, the computational complexity of the proposed scheme is bounded by O(Knb) with memory requirements bounded by O(nb). The algorithm was implemented in a workstation and computational tests for varying values of the parameters were performed.

Sistemas computacionais para o gerenciamento estratégico da logística

Ferreira Filho,Virgílio José Martins

Carta do editor

Yanasse,Horacio Hideki

Linear one-dimensional cutting-packing problems: numerical experiments with the sequential value ...

Mukhacheva,E.A.; Belov,G.N.; Kartack,V.M.; Mukhacheva,A.S.

Two algorithms for the one-dimensional cutting problem, namely, a modified branch-and-bound method (exact method) and a heuristic sequential value correction method are suggested. In order to obtain a reliable assessment of the efficiency of the algorithms, hard instances of the problem were considered and from the computational experiment it seems that the efficiency of the heuristic method appears to be superior to that of the exact one, taking into account the computing time of the latter....

Um método de projeção para problemas de complementaridade linear

Pissarra,Cristiane Maria Alves; Pulino,Petronio

Este artigo apresenta um algoritmo de dois passos para a resolução numérica de problemas de complementaridade linear (LCP). O algoritmo que apresentaremos combina a estratégia de conjunto ativo aliada ao método dos gradientes conjugados quadrático para a resolução do sistema linear reduzido. O desenvolvimento deste método de dois passos foi baseada em um outro, também de dois passos, desenvolvido por Kocvara & Zowe (1994), que combina o método de super relaxação sucessiva simétrica com projeç...

Um modelo de minimização de custos em diagnósticos com um caso de aplicação em um banco de sangue

Epprecht,Eugenio K.; Brasil,Gutemberg Hespanha; Santos Jr.,Mário Cezar dos

O problema aqui tratado é, dado um conjunto de testes para determinação de um diagnóstico, determinar a seqüência de execução destes testes com custo esperado mínimo. Assumindo algumas hipóteses simplificadoras, apresenta-se uma solução que fornece diretamente a seqüência ótima, eliminando a necessidade de busca. A solução se estende também a uma versão do problema com uma estrutura hierárquica de testes. O modelo é genérico, podendo aplicar-se a diagnósticos nos mais diversos contextos: de p...

Um método heurístico baseado em relaxação Lagrangiana para o problema de carregamento de paletes ...

Farago,Randal; Morabito,Reinaldo

Neste trabalho desenvolvemos um método heurístico, baseado em relaxação Lagrangiana e surrogate, para resolver o problema de carregamento de paletes do produtor. Tal problema consiste em arranjar o máximo número de caixas por camada sobre o palete, otimizando, assim, o aproveitamento da superfície do palete. Aplicamos um método de redução do problema e uma heurística Lagrangiana no procedimento de otimização do subgradiente. Comparamos as soluções encontradas com soluções produzidas por outro...

Suinocultura no Estado de Goiás: aplicação de um modelo de localização

Lopes,Ricardo Luis; Caixeta Filho,José Vicente

Esta pesquisa teve como principal objetivo a análise da distribuição mais eficiente de granjas suinícolas no Estado de Goiás. O modelo de localização desenvolvido envolveu uma estrutura de programação inteira mista. Os fatores considerados para o objetivo do estudo foram os custos de transporte de grãos (milho e soja) até a granja, o custo de transporte de suínos até o abatedouro e o custo de transporte de carcaça de suíno até o mercado consumidor. Definiu-se como mercado consumidor o próprio...

The sequential value correction method for the two-dimensional irregular cutting stock problem

Verkhoturov,M.A.; Sergeyeva,O.Y.

This paper regards the problem of the two-dimensional irregular cutting stock problem (ICSP), where the pieces to be cut out may be of any shape. The sequential value correction method has been developed to solve this problem. This method is based on dual values (variables), which is the essential concept of linear programming. We suggest a technique of value calculation for such pieces. The algorithms are included. We also describe a computing experiment whose results are the evidence of the...

SART: an intelligent assistant system for subway control

Brézillon,P.; Naveiro,R.; Cavalcanti,M.; Pomerol,J.-Ch.

One of the main characteristics of a subway line is its large transport capacity (e.g., about 60000 travelers per hour in the Parisian subway) combined with a regular transport supply. The regularity is particularly important at rush time - peak hours - when an incident can provoke important delays. Experience shows that the consequences of an incident are highly dependent on the context in which the incident occurs (e.g., peak hours or not). The decisions taken by the operators are heavily r...