Problema de secuenciación de trabajos: minimización de pérdidas

Nos dan N trabajos numerados del 1 al N. Para cada actividad, sea Ti el número de días necesarios para completar el trabajo. Por cada día de retraso antes de comenzar a trabajar para el trabajo i, se incurre en una pérdida de Li. Estamos obligados a encontrar una secuencia para completar los trabajos de modo que se minimice la pérdida total. Solo podemos trabajar en un trabajo a la vez. Si son posibles múltiples soluciones de este tipo, entonces estamos obligados a dar la menor permutación lexicográficamente (es decir, la más antigua en el orden del diccionario). Ejemplos:

Input : L = {3, 1, 2, 4} and 
        T = {4, 1000, 2, 5}
Output : 3, 4, 1, 2
Explanation: We should first complete 
job 3, then jobs 4, 1, 2 respectively.

Input : L = {1, 2, 3, 5, 6} 
        T = {2, 4, 1, 3, 2}
Output : 3, 5, 4, 1, 2 
Explanation: We should complete jobs 
3, 5, 4, 1 and then 2 in this order.

Consideremos dos casos extremos y de ellos deduciremos la solución del caso general.

1. Todos los trabajos tardan el mismo tiempo en terminar, es decir, Ti = k para todos los i. Dado que todos los trabajos tardan el mismo tiempo en finalizar, primero debemos seleccionar trabajos que tengan una gran pérdida (Li). Deberíamos seleccionar los trabajos que tienen las pérdidas más altas y terminarlos lo antes posible. Por lo tanto, este es un algoritmo codicioso. Ordene los trabajos en orden descendente basándose únicamente en Li.
2. Todos los trabajos tienen la misma penalización. Dado que todos los trabajos tienen la misma penalización, haremos primero aquellos trabajos que llevarán menos tiempo para terminar. Esto minimizará el retraso total y, por lo tanto, también la pérdida total incurrida. Este también es un algoritmo codicioso. Ordene los trabajos en orden ascendente según Ti. O también podemos ordenar en orden descendente de 1/Ti.

De los casos anteriores, podemos ver fácilmente que debemos ordenar los trabajos no solo en base a Li o Ti. En su lugar, deberíamos clasificar los trabajos según la relación Li/Ti, en orden descendente.

Podemos obtener la permutación de trabajos lexicográficamente más pequeña si realizamos una ordenación estable en los trabajos. Un ejemplo de ordenación estable es la ordenación por fusión .

Para obtener el resultado más preciso, evite dividir Li entre Ti. En su lugar, compare las dos razones como fracciones. Para comparar a/b y c/d, compare ad y bc.

// CPP program to minimize loss using stable sort.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
#define all(c) c.begin(), c.end()
 
// Each job is represented as a pair of int and pair.
// This is done to provide implementation simplicity
// so that we can use functions provided by algorithm
// header
typedef pair<int, pair<int, int> > job;
 
// compare function is given so that we can specify
// how to compare a pair of jobs
bool cmp_pair(job a, job b)
{
    int a_Li, a_Ti, b_Li, b_Ti;
    a_Li = a.second.first;
    a_Ti = a.second.second;
    b_Li = b.second.first;
    b_Ti = b.second.second;
 
    // To compare a/b and c/d, compare ad and bc
    return (a_Li * b_Ti) > (b_Li * a_Ti);
}
 
void printOptimal(int L[], int T[], int N)
{
    vector<job> list; // (Job Index, Si, Ti)
 
    for (int i = 0; i < N; i++) {
        int t = T[i];
        int l = L[i];
 
        // Each element is: (Job Index, (Li, Ti) )
        list.push_back(make_pair(i + 1, make_pair(l, t)));
    }
 
    stable_sort(all(list), cmp_pair);
 
    // traverse the list and print job numbers
    cout << "Job numbers in optimal sequence are\n";
    for (int i = 0; i < N; i++)
        cout << list[i].first << " ";
 
}
 
// Driver code
int main()
{
    int L[] = { 1, 2, 3, 5, 6 };
    int T[] = { 2, 4, 1, 3, 2 };
    int N = sizeof(L) / sizeof(L[0]);
    printOptimal(L, T, N);
    return 0;
}

//Java program to minimize loss using stable sort.
 
import java.io.*;
import java.util.*;
 
class GFG {
     
    // compare function is given so that we can specify
    // how to compare a pair of jobs
    public static class cmp_pair implements Comparator<job>
    {
        @Override
        public int compare(job a, job b){
            int a_Li, a_Ti, b_Li, b_Ti;
            a_Li = a.li;
            a_Ti = a.ti;
            b_Li = b.li;
            b_Ti = b.ti;
           
            // To compare a/b and c/d, compare ad and bc
            return (a_Li * b_Ti) > (b_Li * a_Ti)?-1:1;
        }
    }
     
    public static void printOptimal(int L[], int T[], int N)
    {
        List<job> list = new ArrayList<>(); // (Job Index, Si, Ti)
       
        for (int i = 0; i < N; i++) {
            int t = T[i];
            int l = L[i];
       
            // Each element is: (Job Index, (Li, Ti) )
            list.add(new job(i + 1, l, t));
        }
       
        Collections.sort(list,new cmp_pair());
       
        // traverse the list and print job numbers
        System.out.println("Job numbers in optimal sequence are");
        for (int i = 0; i < N; i++)
            System.out.print(list.get(i).index+" ");  
       
    }
     
    public static void main (String[] args) {
        int L[] = { 1, 2, 3, 5, 6 };
        int T[] = { 2, 4, 1, 3, 2 };
        int N = L.length;
        printOptimal(L, T, N);
    }
}
 
// Each job is represented as a pair of int and pair.
// This is done to provide implementation simplicity
// so that we can use functions provided by algorithm
// header
class job{
    int index,ti,li;
    job(int i,int l, int t){
        this.index=i;
        this.ti=t;
        this.li=l;
    }
}
 
//This code is contributed by shruti456rawal

Job numbers in optimal sequence are
3 5 4 1 2 

Complejidad de tiempo: O(N log N)
Complejidad de espacio: O(N)

Este artículo es una contribución de Sayan Mahapatra . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org . Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.