Hola kiko,

Entre 1991 y 1992 en Object Style hicimos una aplicación que "servía"
para determinar la forma mas eficiente de cortar chapas metálicas bajo
pedidos dinámicos.
Es decir, uno tiene chapas inmensas de metal a las que puede cortar en
forma horizontal o vertical, pero de cualquier tamaño y en cualquier
orden (podes cortar una chapa ya cortada).
Dicho así el problema parece parecido al tuyo... un problema difícil.
Para resolverlo formulamos un framework bidimensional de recorte,
que uno o dos años después usamos en parte (como guías iniciales)
en sistemas de mapas.
Recuerdo que nos llevó una o dos semanas darnos cuenta en que
problema nos habíamos metido :-)
Y recuerdo que, entre 3 y 6 meses lograr resolver el problema
"decorosamente" (eramos tres personas ocupadas intermitentemente
en ese tema).

El problema mas importante al comienzo parecía ser el "cómo cortar ?".
Luego del primer prototipo comprobamos que era un problema :-P
pero además nos dimos cuenta de un problema mayor aún.

Al cortar chapas, se generan retazos que se desean usar para cortar
otras chapas!
Y además un pedido que esta aprobado puede ser revocado justo
antes de cortar... invalidando el análisis que habías hecho e invalidando
otros pedidos!

Es decir, el problema no solo era complejo de resolver por única vez,
sino que además, en nuestro caso, el problema se replantea dinámicamente...
Lo mismo ocurriría si, alguien empieza a sacar cajas en dónde vos
estas poniéndolas... (en tu caso espero que esto no pueda ocurrir :-)

Al analizar esta problemática y encontrar que el sistema era un sistema
que no tenía un "tiempo cero" ni un fin; intentamos no resolverlo.
Es decir, dejamos de intentar la "vía fácil" y empezamos a buscar
cómo resolver el problema, sin importar que sea la mas eficiente.
Pues así no parábamos la línea de corte... esperando la mejor forma de
cortar para ahorrar, por ejemplo, un 1% de material y dejar (en muchos
casos) recortes inusables/invendibles (es decir, mas basura).

Poco recuerdo de los detalles de la implementacion (fue en Smalltalk/V)
y no se si tendré aún un backup (en diskettes).
Si recuerdo que:
- la solución funcionaba con una cinética apropiada para
satisfacer los pedidos.
- el software se usó por poco tiempo (creo, no mas de un año)
y en modo de asistente; con "metidas de mano" periódicas
(es decir, priorizar pedidos a mano para que corte mejor, etc;
las personas no dejaban hacer al sistema, sino que lo usaban
como si fuera el mas bobo del equipo... creo que eso es lógico,
ya que el sistema no puede defenderse :-) ).
- el hacer ese sistema nos reforzó como equipo (a Leo, Xavi y a mi)
y reforzó la "fe" en que hay cosas que cuesta formular en términos
de objetivos (el objetivo para el cliente era cortar de la mejor
forma, pero en realidad lo que mas importaba era no afectar a la
cinética del proceso)

Espero sirvan de algo los comentarios y te animen en tus
ensayos sobre la problemática.

hasta pronto,
Ale.




----- Original Message -----
From: "kikote gregoris" <kikogregoris@...>
To: <smalltalking@...>
Sent: Friday, May 19, 2006 11:34 AM
Subject: Re: [objetos] Backtraking


> Hola segio
>
> Que es un problema NP ??.
>
> Lo voy a replantear, en principio lo queria hacer en 3d , ahora lo voy a
plantear en 2d que creo es un poco mas simple , si es que lo es .
> Luego pienso que hacerlo en 3d puede resultar mas simple.
>
> Debo aclarar que el problema en 2d es llenar un área rectangular con la
maxima cantidad de formas rectangulares.
>
> saludos kiko
>
> Sergio Fedi <sergio.fedi@...> escribió:
> La solución va por el lado del backtracking, tengo la idea
general de cómo hacer esto pero quisiera saber si alguien realizo algo de
este tipo.
> Tengan en cuenta que necesito que puedan ingresar la mayor cantidad de
paquetes dentro de la caja.
>
>
>
> Si mal no recuerdo, eso es un problema NP.
>
> Y backtracking es una posible solucion, y dudo que sea la mejor.
>
> Fijate papers sobre el tema.
>
> Es probable que una heuristica apropiada sea mejor.
>
>
>
>
> Para más información sobre la Asociación escribir a info@...
>
> Smalltalking es un espacio colaborativo creado para el estudio y
desarrollo en Ambientes de Objetos.
> Se sustenta gracias a la participación de sus socios.
>
> Las reglas de etiqueta sobre la lista están en
http://www.smalltalking.net/join/netiquete.htm
>
>
>
>
> ---------------------------------
> Enlaces de Yahoo! Grupos
>
> Para visitar el sitio web del grupo, andá a:
> http://ar.groups.yahoo.com/group/smalltalking/
>
> Para cancelar tu suscripción a este grupo, enviá un mensaje a:
> smalltalking-unsubscribe@...
>
> El uso de Yahoo! Grupos está sujeto a las Condiciones del servicio de
Yahoo!.
>
>
>
>
> ---------------------------------
> 1GB gratis, Antivirus y Antispam
> Correo Yahoo!, el mejor correo web del mundo
> Abrí tu cuenta aquí