Revista: | Pesquisa operacional |
Base de datos: | PERIÓDICA |
Número de sistema: | 000312991 |
ISSN: | 0101-7438 |
Autores: | Colin, Emerson C1 Shimizu, Tamio |
Instituciones: | 1Universidade de Sao Paulo, Escola Politecnica, Sao Paulo. Brasil |
Año: | 2000 |
Periodo: | Jun |
Volumen: | 20 |
Número: | 1 |
Paginación: | 19-30 |
País: | Brasil |
Idioma: | Portugués |
Tipo de documento: | Artículo |
Enfoque: | Analítico, descriptivo |
Resumen en inglés | In this work we consider the one machine problem, with distinct due-dates and penalties for earliness and tardiness. For a previously defined sequence, we utilize the sum of weighted lateness (earliness or tardiness) as objective function. This work is presented as a generalization of the Garey et al. (1988) scheduling algorithm. Using a computational structure called heap, this algorithm allows a schedule construction in O(nlogn) time while the best found in literature runs in O(n²) |
Resumen en portugués | 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 algoritmo permite a elaboração de um programa em tempo O(nlogn), enquanto que o melhor encontrado na literatura atualmente é de tempo O(n²) |
Disciplinas: | Ingeniería, Administración y contaduría, Ciencias de la computación |
Palabras clave: | Ingeniería industrial, Administración de la producción, Procesamiento de datos, Programación de la producción, Inserción de ociosidad, Programación JIT, Algoritmos |
Keyword: | Engineering, Management and accounting, Computer science, Industrial engineering, Production management, Data processing, Production scheduling, Idle time insertion, JIT scheduling, Algorithms |
Texto completo: | Texto completo (Ver HTML) |