| Journal: | Pesquisa operacional |
| Database: | PERIÓDICA |
| System number: | 000312991 |
| ISSN: | 0101-7438 |
| Authors: | Colin, Emerson C1 Shimizu, Tamio |
| Institutions: | 1Universidade de Sao Paulo, Escola Politecnica, Sao Paulo. Brasil |
| Year: | 2000 |
| Season: | Jun |
| Volumen: | 20 |
| Number: | 1 |
| Pages: | 19-30 |
| Country: | Brasil |
| Language: | Portugués |
| Document type: | Artículo |
| Approach: | Analítico, descriptivo |
| English abstract | 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²) |
| Portuguese abstract | 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²) |
| Disciplines: | Ingeniería, Administración y contaduría, Ciencias de la computación |
| Keyword: | 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 |
| Full text: | Texto completo (Ver HTML) |
