Revue: | Ingeniería y desarrollo |
Base de datos: | PERIÓDICA |
Número de sistema: | 000369083 |
ISSN: | 0122-3461 |
Autores: | Niño, Elías D1 Ardila, Carlos J1 |
Instituciones: | 1Universidad del Norte, Departamento de Ingeniería de Sistemas, Barranquilla, Atlántico. Colombia |
Año: | 2009 |
Periodo: | Ene-Jun |
Número: | 25 |
Paginación: | 99-114 |
País: | Colombia |
Idioma: | Español |
Tipo de documento: | Artículo |
Enfoque: | Experimental, aplicado |
Resumen en español | En este artículo se propone un Autómata Finito Determinista de Intercambio (AFD - I) que permite modelar el espacio de soluciones factibles a problemas de naturaleza combinatoria, específicamente a problemas asociados con el orden de elementos. Con la estructura AFD - I definida, se diseña e implementa un algoritmo con cuyo uso se obtiene un óptimo global a problemas combinatorios. El problema que aquí se trata puede ser extrapolado a cualquiera de los siguientes casos: asignación de n procesos a n máquinas que trabajan en paralelo, selección de la ruta óptima en el problema del agente viajero y el problema del bin packing |
Resumen en inglés | This article states a Deterministic Finite Automaton of Exchange (DFA - E). It allows modeling of the space of feasible solutions to combinatorial problems, specifically, the problems associated with the order of elements. With the structure DFA - E defined, we designed and implemented an algorithm that uses it for obtaining a global solution of combinatorial problems. The problem we treat here can be extrapolated to any of the following: an allocation of n processes machines working in parallel, selecting the optimal route in the traveling salesman problem (TSP) and the problem of Bin Packing |
Disciplinas: | Ingeniería |
Palabras clave: | Ingeniería de sistemas, Autómatas finitos, Algoritmos, Optimización combinatoria |
Keyword: | Engineering, Systems engineering, Finite automata, Algorithms, Combinatorial optimization |
Texte intégral: | Texto completo (Ver HTML) |