En problema de secuenciación de trabajos, el objetivo es encontrar la secuencia de trabajos,que se completa dentro de sus plazos y dar el máximo beneficio.
Si se da un conjunto de n trabajos que están asociados con fechas límite y se obtienen beneficios y un trabajo se completa antes de su fecha límite. Estos puestos de trabajo deben ordenarse de tal manera que se obtenga el máximo beneficio.
Tomemos un ejemplo. Como se muestra en la figura 1.1, se muestra una matriz de trabajos en los que cada trabajo tiene una fecha límite y un beneficio asociado si el trabajo se termina antes de la fecha límite. También se da que cada trabajo toma una sola unidad de tiempo, por lo que el plazo mínimo posible para cualquier trabajo es 1. Cómo maximizar el beneficio total si solo se puede programar un trabajo a la vez.
Una solución simple es generar todos los subconjuntos de un conjunto de trabajos dado y verificar la viabilidad de los trabajos en ese subconjunto. Lleve un registro del máximo beneficio entre todos los subconjuntos viables. La complejidad temporal de esta solución es exponencial.También podemos resolver este problema utilizando el método codicioso, que es más óptimo que una solución simple.Así que vamos a resolver este problema a través del método codicioso.
Para resolver el problema de secuenciación de trabajos a través del método greedy, siga estos pasos:
- Ordena todos los trabajos en orden decreciente de ganancias.
- Inicialice la secuencia de resultados como primer trabajo en trabajos ordenados.
- Haga lo siguiente para los trabajos n-1 restantes.
- Si el trabajo actual puede caber en la secuencia de resultados actual sin perder la fecha límite, agregue el trabajo actual al resultado. De lo contrario, ignore el trabajo actual.
Como puede ver en la figura 1.1, los trabajos ya están en orden decreciente de ganancias.Aquí el trabajo 1 tiene el beneficio más alto y la fecha límite es 3, así que establezca ese trabajo entre 2 y 3, como se muestra en la figura 1.2.El trabajo 2 tiene el segundo mayor beneficio y la fecha límite es 4, así que establezca ese trabajo entre 3 y 4 y haga lo mismo para todos jobs.So la secuencia final es J4-J3-J1-J2 y el beneficio total es de 110.
Puede preferir el código para este algoritmo en https://www.geeksforgeeks.org/job-sequencing-problem.
La complejidad temporal de esta solución es O (n2). Se puede optimizar mediante una Estructura de Datos Disjunta.
Espero que te guste el artículo.Gracias 🙂
