No conozco la literatura sobre problemas como este. Supongo que hay algunos, sin embargo, ya que la teoría de colas es una gran área académica, y esto no suena como una situación ridículamente artificial. Eso sí, el hecho de que te preocupes por la latencia promedio, en lugar de la latencia del peor de los casos o la latencia del percentil N, podría ponerte en minoría.
Mi primer instinto es que, dado que parece que hay muchos trabajos disponibles, una buena solución tendría varios trabajadores "flexibles" empleados continuamente. Este es un conjunto de trabajadores que, entre ellos, puede completar la mayoría de los tipos de trabajos comunes con una latencia aceptable. Cuanto menor sea el nivel de latencia, más recursos habrá en este conjunto y más tiempo pasarán inactivos. Además, cuanto más "ráfaga" sea su entrada (suponiendo que las ráfagas sean impredecibles), más tiempo inactivo necesitará para evitar una alta latencia durante las ráfagas.
A continuación, en dos ocasiones se contratan trabajadores "especializados" adicionales:
1) Un raro tipo de trabajo en el que viene el conjunto actual de contrataciones sólo puede manejar a un costo más alto o nada en absoluto. Así que contratas (hablando en términos generales) a cualquiera que pueda cambiarlo y luego haces la mayor cantidad posible del resto de tu cola.
2) No existe tal trabajo, pero se ve la oportunidad de contratar a alguien que resulta ser capaz de tomar una combinación de trabajos de la fila actual, y hacerlos más baratos que sus empleados actuales, pero sin salir tus contrataciones actuales inactivas. Entonces contratas ese recurso.
En cuanto al algoritmo real: es casi seguro que no sea computacionalmente factible encontrar la mejor solución, por lo que la respuesta correcta depende de los recursos de procesamiento y de que está viendo la heurística y la solución de problemas parciales. Mientras que todos los que contrates estén ocupados, y no puedes contratar a nadie más sin causar un tiempo de inactividad significativo en algún momento en el futuro, probablemente estés cerca de una buena solución, y en algún lugar cerca de la "mayor explosión por cada dólar". "punto de la latencia/costo de intercambio. Contratar más recursos después de eso da rendimientos decrecientes, pero eso no significa que no esté dispuesto a hacerlo por una latencia específica y/o un presupuesto específico.
Pero depende de cómo sean los trabajos entrantes: si tiene un recurso que solo puede hacer un tipo de trabajo y ese trabajo solo se realiza una vez al día/semana/año, entonces es mejor contratarlo una vez un día que esperar hasta que tenga suficiente de ese trabajo para llenar su mínimo horario posible (que es por lo que los bomberos pasan la mayor parte de su tiempo jugando juegos de cartas, mientras que los mecanógrafos pasan la mayor parte de su tiempo escribiendo. Siempre hay suficiente tipeo para mantener al menos uno mecanógrafo ocupado, pero los incendios son raros. Además, no queremos la solución de "más explosión por cada dólar" para los incendios, queremos una latencia menor que eso). Por lo tanto, probablemente haya oportunidades para ajustar el algoritmo para su conjunto particular de recursos y patrón de trabajos entrantes, si está resolviendo una instancia particular del problema en lugar de escribir un software de programación general.
Además, presumiblemente si los recursos son humanos, no se puede garantizar que la contratación tenga éxito.No se quedarán todo el día sentados solo cobrando cuando sucede que hay trabajo minuto a minuto, ¿o sí?
Una nota sobre los valores numéricos anteriores, no son restricciones duras, sino promedios. – sehugg
Ah, y los trabajos tienen prioridades definidas (solo unos pocos). Voy a callarme ahora :) – sehugg
No entiendo completamente. ¿La "latencia" significa el tiempo de espera del trabajo o la capacidad de recursos no utilizados? Si el primero, simplemente recluta todos los recursos que puedas tener. Si es el último, recluta solo 1 recurso por restricción difícil para su idoneidad. ¿Falta alguna pieza o simplemente estoy malinterpretando el problema? –