Journal: | Ingeniería y desarrollo |
Database: | PERIÓDICA |
System number: | 000369083 |
ISSN: | 0122-3461 |
Authors: | Niño, Elías D1 Ardila, Carlos J1 |
Institutions: | 1Universidad del Norte, Departamento de Ingeniería de Sistemas, Barranquilla, Atlántico. Colombia |
Year: | 2009 |
Season: | Ene-Jun |
Number: | 25 |
Pages: | 99-114 |
Country: | Colombia |
Language: | Español |
Document type: | Artículo |
Approach: | Experimental, aplicado |
Spanish abstract | 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 |
English abstract | 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 |
Disciplines: | Ingeniería |
Keyword: | Ingeniería de sistemas, Autómatas finitos, Algoritmos, Optimización combinatoria |
Keyword: | Engineering, Systems engineering, Finite automata, Algorithms, Combinatorial optimization |
Full text: | Texto completo (Ver HTML) |