Resumen

En esta nota técnica presentamos los resultados de pruebas computacionales de la implementación de un algoritmo exacto propuesto en la literatura para resolver un problema de secuenciación que surge en algunos entornos de producción en los que se desea minimizar los pedidos pendientes de clientes. A partir de los resultados computacionales observamos que los criterios de dominancia incorporados en el proceso enumerativo de este algoritmo reducen el espacio de búsqueda, haciéndolo más eficiente en términos de tiempo de ejecución.

1. INTRODUCCIÓN

Consideremos una fábrica que produce varios tipos de artículos. Debido a sus peculiares características, la fábrica sólo puede producir un tipo de artículo a la vez. Una vez que se decide qué artículo producir, se fabrica la demanda de todo el mes de ese tipo de artículo debido a los elevados costes de preparación. Por lo tanto, sólo se produce un lote de cada tipo de artículo en el mes.

Consideremos que esta fábrica tiene cada mes una cartera de pedidos de varios clientes. En el cuadro 1 presentamos una cartera hipotética de estos pedidos.

La tabla 1 muestra que en esta fábrica se producen 11 tipos de artículos (a, b, c, d, e, f, g, h, i, j, k). Cada cliente solicitó un subconjunto de estos productos. Por ejemplo, el cliente 7 solicitó los artículos b, d y g, el cliente 13 solicitó los artículos a, b y h, y el cliente 12 solicitó los artículos j y k.

Si la fábrica produce los artículos a, b, c, d, e, f, g, h, i, j, k, en esta secuencia, los pedidos de los clientes se cumplirán parcialmente según la tabla 2.

Con la producción de los artículos en la secuencia indicada, el primer cliente al que se completó su pedido fue el cliente 1, después el cliente 11, 10, 2, 6, y así sucesivamente (véase la tercera columna del cuadro 2). En la segunda columna del cuadro 2, observamos la evolución de cómo se van completando los pedidos de los clientes. Por ejemplo, tras la fabricación del artículo de tipo b, tenemos nueve pedidos parcialmente cumplimentados de los clientes 1, 2, 3, 5, 7, 9, 10, 11 y 13. Al resto de clientes aún no se les ha fabricado ningún artículo pedido.

Los pedidos incompletos pueden ser un inconveniente para la fábrica, por ejemplo, por la dificultad de manipular los artículos fabricados, las dificultades de almacenamiento por la limitación del espacio físico, los recursos financieros inmovilizados en existencias, etc. En cambio, un pedido completo puede entregarse inmediatamente al cliente y facturarse.

En este contexto, interesa determinar una secuencia de fabricación de los artículos que evite este gran número de pedidos parcialmente cumplidos, es decir, queremos minimizar el número máximo de pedidos parcialmente cumplidos durante la fabricación de los artículos.

• Materias:Estudio de tiempos Algoritmos de optimización Programación de la producción
• Subjects:Time study Optimization algorithms Production scheduling
• Palabras claves:Secuenciación de trabajos; Enumeración
• Keywords:Job sequencing; Enumeración