| Journal: | Pesquisa operacional |
| Database: | PERIÓDICA |
| System number: | 000312992 |
| ISSN: | 0101-7438 |
| Authors: | Muller, Felipe Martins1 Limberger, Sergio Joao2 |
| Institutions: | 1Universidade Federal de Santa Maria, Centro de Tecnologia, Santa Maria, Rio Grande do Sul. Brasil 2Universidade Federal de Santa Maria, Centro de Processamento de Dados, Santa Maria, Rio Grande do Sul. Brasil |
| Year: | 2000 |
| Season: | Jun |
| Volumen: | 20 |
| Number: | 1 |
| Pages: | 31-42 |
| Country: | Brasil |
| Language: | Portugués |
| Document type: | Artículo |
| Approach: | Aplicado, descriptivo |
| English abstract | This paper examines the nonpreemptive assignment of independent jobs to a system of uniform processors with the objective of reducing makespan, or the time required from the start of execution until all jobs are completed. We consider a set of n jobs, each having an execution time and a set of m³2 processors which are assumed to have different speeds (say s1 = 1£s2£ ... £sm). Since the problem of finding a minimal makespan has been show to be NP-hard, we develop a powerful interchange heuristic. The heuristic proposed is composed by three phases: initial assignment, job reassignment and job interchange. The main feature of this method is not perform a pre-classification of the tasks. Some comparison are made with other heuristic schemes and a lower bound that validates the results obtained. The heuristic achieve optimal solutions for several instances in a short computational time |
| Portuguese abstract | 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³2 de processadores com velocidades de processamento s1 = 1£s2£ ...£sm. Sendo o problema de encontrar o mínimo makespan considerado NP-difícil, desenvolveu-se uma heurística de trocas poderosa para resolvê-lo. A heurística proposta é composta de três fases: alocação inicial, balanceamento de carga e fase de dupla troca. A principal característica desta nova heurística é a de prescindir de uma pré-ordenação das tarefas. A heurística desenvolvida foi comparada com um limitante inferior da solução ótima e também com outras três heurísticas apresentando um desempenho superior, encontrando a solução ótima em um grande número de casos as custas de um baixo esforço computacional |
| Disciplines: | Ciencias de la computación, Matemáticas |
| Keyword: | Procesamiento de datos, Matemáticas aplicadas, Problemas de secuenciamiento, Optimización combinatoria, Heurística |
| Keyword: | Computer science, Mathematics, Data processing, Applied mathematics, Scheduling problems, Combinatorial optimization, Heuristics |
| Full text: | Texto completo (Ver HTML) |
