Asignación de tareas: Pastelería
Este problema parte de \(n\) pasteleros que son capaces de preparar \(m\) tipos diferentes de pasteles pero con distinto nivel de destreza para cada tipo de pastel. El algoritmo asigna los próximos \(n\) pedidos, uno para cada pastelero, de forma que se minimice el coste total.
Los datos de entrada del algoritmo son:
- La tabla de costes \(C[1..n,1..m]\) que indica el coste de que el pastelero \(i\) realice el pastel \(j\).
- La lista de los tipos de los próximos \(n\) pedidos, almacenados en un vector, \(pedidos[1..n\]).
Este problema no puede resolverse mediante un algoritmo voraz, por lo tanto es adecuado para el esquema de ramificación y poda.
Vemos el siguiente ejemplo, con los siguientes datos de entrada:
En este caso el coste mínimo sería 20 y se correspondería con la asignación \([1,3,5,2,4]\).
Las estructuras de datos que se van a utilizar son:
- Los nodos que utilizaremos para recorrer el espacio de búsqueda, contendrán:
- Un vector que almacena el pedido asignado a cada pastelero.
- Un vector que almacena si se le ha asignado un pedido a un pastelero o no.
- Un entero que almacena la posición del último pedido asignado.
- El coste total de los pedidos almacenados hasta ese momento.
- La estimación optimista del coste de la solución.
- Además, estos nodos se almacenan en un montículo de mínimos, de forma que el primer nodo en ser extraido será el que tenga menor coste total estimado.
Además, para podar los nodos utilizaremos las estimaciones:
- Estimación pesimista: Al coste de la solución parcial se le suma el coste máximo de los pendientes de asignar.
- Estimación optimista: al coste de la solución parcial se le suma el costa mínimo de los pendientes de asignar.
En la pantalla de visualización podrás aprender el funcionamiento de este algoritmo. En primer lugar introduce el número de pasteleros y el número de tipos diferentes de pastel y pulsa RESET. A continuación introduce en la tabla el coste de hacer cada tipo de pastel por cada pastelero y pulsa ACTUALIZAR. Podrás ver cómo evoluciona el algoritmo y las estructuras de datos implicadas utilizando los botones de control de la parte superior.