El tiempo de procesamiento más largo primero (LPT) es un algoritmo codicioso para la programación de trabajos . La entrada al algoritmo es un conjunto de trabajos , cada uno de los cuales tiene un tiempo de procesamiento específico. También hay un número m que especifica el número de máquinas que pueden procesar los trabajos. El algoritmo LPT funciona de la siguiente manera:
El paso 2 del algoritmo es esencialmente el algoritmo de programación de listas (LS). La diferencia es que LS recorre los trabajos en un orden arbitrario, mientras que LPT los ordena previamente por tiempo de procesamiento descendente.
LPT fue analizado por primera vez por Ronald Graham en la década de 1960 en el contexto del problema de programación de máquinas idénticas . [1] Posteriormente, se aplicó a muchas otras variantes del problema.
LPT también se puede describir de una manera más abstracta, como un algoritmo para la partición de números de múltiples vías . La entrada es un conjunto S de números y un entero positivo m ; la salida es una partición de S en m subconjuntos. LPT ordena la entrada de mayor a menor y coloca cada entrada en la parte con la suma más pequeña hasta el momento.
Si el conjunto de entrada es S = {4, 5, 6, 7, 8} y m = 2, entonces la partición resultante es {8, 5, 4}, {7, 6}. Si m = 3, entonces la partición de 3 vías resultante es {8}, {7, 4}, {6, 5}.
Es posible que LPT no encuentre la partición óptima. Por ejemplo, en el caso anterior, la partición óptima {8,7}, {6,5,4}, donde ambas sumas son iguales a 15. Sin embargo, su subóptimo está acotado tanto en el peor de los casos como en el caso promedio; consulte Garantías de rendimiento a continuación.