Planificación laboral veraz

La programación veraz de trabajos es una variante de diseño de mecanismos del problema de programación de talleres de producción de la investigación operativa .

Tenemos un proyecto compuesto por varias "tareas" (trabajos). Hay varios trabajadores. Cada trabajador puede realizar cualquier tarea, pero cada uno requiere un tiempo diferente para completarla. Nuestro objetivo es asignar las tareas a los trabajadores de manera que se minimice el tiempo total de finalización del proyecto. En el problema estándar de programación de talleres, se conocen los tiempos de todos los trabajadores, por lo que tenemos un problema de optimización estándar . En cambio, en el problema de programación de tareas con información veraz, se desconocen los tiempos de los trabajadores. Preguntamos a cada trabajador cuánto tiempo necesita para realizar cada tarea, pero podrían mentirnos. Por lo tanto, debemos incentivar a los trabajadores a que nos digan sus tiempos reales pagándoles una cierta cantidad de dinero. El desafío es diseñar un mecanismo de pago que sea compatible con el incentivo .

El problema de la programación veraz de trabajos fue introducido por Nisan y Ronen en su artículo de 1999 sobre el diseño de mecanismos algorítmicos . ^{[ 1 ]}

Hay${\displaystyle n}$empleos y${\displaystyle m}$trabajadores ("m" significa "máquina", ya que el problema radica en la programación de tareas para las computadoras). Trabajador${\displaystyle i}$puede hacer el trabajo${\displaystyle j}$a tiempo${\displaystyle T_{i,j}}$. Si el trabajador${\displaystyle i}$Se le asigna un conjunto de trabajos${\displaystyle J_{i}}$, entonces podrá ejecutarlas a tiempo:

${\displaystyle T_{i}(J_{i})=\sum _{j\in J_{i}}t_{i,j}}$

Dada una asignación${\displaystyle J_{1},\dots ,J_{m}}$de empleos para trabajadores, el tiempo de finalización de un proyecto es:

${\displaystyle MakeSpan(J_{1},\dots ,J_{n})=\max _{i}{T_{i}(J_{i})}}$

Una asignación óptima es una asignación de trabajos a trabajadores en la que se minimiza el tiempo de finalización. El tiempo de finalización mínimo se denota por${\displaystyle MinMakeSpan}$.

Un mecanismo es una función que toma como entrada la matriz${\displaystyle T}$(el tiempo que cada trabajador necesita para realizar cada tarea) y devuelve como resultado:

• Una asignación de puestos de trabajo a los trabajadores,${\displaystyle J_{1},\dots ,J_{n}}$;
• Un pago a cada trabajador,${\displaystyle p_{1},\dots ,p_{n}}$.

La utilidad del trabajador${\displaystyle i}$, bajo dicho mecanismo, es:

${\displaystyle u_{i}=p_{i}-T_{i}(J_{i})}$

Es decir, el agente recibe el pago, pero pierde el tiempo que dedica a realizar las tareas. Cabe destacar que el pago y el tiempo se miden en las mismas unidades (por ejemplo, podemos suponer que los pagos son en dólares y que cada unidad de tiempo le cuesta al trabajador un dólar).

Un mecanismo se considera veraz (o compatible con los incentivos ) si cada trabajador puede alcanzar la máxima utilidad informando su verdadero vector de tiempos (es decir, ningún trabajador tiene incentivos para mentir sobre sus tiempos).

El factor de aproximación de un mecanismo es la mayor relación entre${\displaystyle Makespan}$y${\displaystyle MinMakespan}$(cuanto menor, mejor; un factor de aproximación de 1 significa que el mecanismo es óptimo).

La investigación sobre la planificación veraz de tareas tiene como objetivo encontrar límites superiores (positivos) e inferiores (negativos) para los factores de aproximación de los mecanismos veraces.

La primera solución que viene a la mente es el mecanismo VCG , que es un mecanismo genérico y veraz. Un mecanismo VCG se puede utilizar para minimizar la suma de los costos. Aquí, podemos usar VCG para encontrar una asignación que minimice el "total de producción", definido como:

${\displaystyle MakeTotal(J_{1},\dots ,J_{n})=\sum _{i}{T_{i}(J_{i})}}$

Aquí, la minimización de la suma se puede lograr simplemente asignando cada trabajo al trabajador que necesite el menor tiempo para realizarlo. Para mantener la veracidad del mecanismo, a cada trabajador que acepta un trabajo se le paga el segundo menor tiempo para realizarlo (como en una subasta de Vickrey ).

Sea OPT una asignación que minimiza el tiempo de finalización. Entonces:

${\displaystyle MakeSpan[VCG]\leq MakeTotal[VCG]\leq MakeTotal[OPT]\leq m\cdot MakeSpan[OPT]}$

(donde la última desigualdad se deduce del principio del palomar ). Por lo tanto, el factor de aproximación de la solución VCG es como máximo${\displaystyle m}$– el número de trabajadores.

El siguiente ejemplo muestra que el factor de aproximación de la solución VCG puede ser exactamente${\displaystyle m}$. Supongamos que hay${\displaystyle n=m}$Los puestos de trabajo y los horarios de los trabajadores son los siguientes:

• El trabajador 1 puede hacer todos los trabajos en 1 tiempo.
• Los demás trabajadores pueden hacer todo el trabajo a tiempo.${\displaystyle 1+\epsilon }$, dónde${\displaystyle \epsilon >0}$es una pequeña constante.

Luego, el mecanismo VCG asigna todas las tareas al trabajador 1. Tanto el "make-total" como el makespan son${\displaystyle n=m}$. Pero, cuando cada trabajo se asigna a un trabajador diferente, el tiempo de finalización es${\displaystyle 1+\epsilon }$.

Un factor de aproximación de${\displaystyle m}$No es muy bueno, y muchos investigadores han intentado mejorarlo en los años siguientes.

Por otro lado, existen algunos resultados de imposibilidad que demuestran que el factor de aproximación no puede ser demasiado pequeño.

El factor de aproximación de todo mecanismo determinista veraz es al menos 2. ^{[ 1 ] : 177-}

La demostración es típica de los límites inferiores en el diseño de mecanismos. Verificamos escenarios específicos (en nuestro caso, tiempos específicos de los trabajadores). Por veracidad, cuando un trabajador modifica su declaración, no debe obtener ningún beneficio de ello. Esto impone ciertas restricciones a las asignaciones que devuelve el mecanismo en los diferentes escenarios.

En el siguiente esbozo de demostración, para simplificar asumimos que hay 2 trabajadores y que el número de trabajos es par,${\displaystyle n=2k}$Consideramos los siguientes escenarios:

1. Los tiempos de ambos trabajadores para todos los trabajos son 1. Dado que el mecanismo es determinista, debe devolver una asignación única.${\displaystyle J_{1},J_{2}}$Supongamos, sin pérdida de generalidad , que${\displaystyle |J_{1}|\leq |J_{2}|}$(Al trabajador 1 se le asignan como máximo tantos trabajos como al trabajador 2).
2. Los horarios del trabajador 1 para los trabajos en${\displaystyle J_{1}}$son${\displaystyle \epsilon }$(una constante positiva muy pequeña); los tiempos del trabajador 1 para los trabajos en${\displaystyle J_{2}}$son${\displaystyle 1+\epsilon }$; y los tiempos del trabajador 2 para todos los trabajos siguen siendo 1. El trabajador 1 sabe que, si miente y dice que sus tiempos para todos los trabajos son 1, el mecanismo (determinista) le asignará los trabajos en${\displaystyle J_{1}}$y su costo será muy cercano a 0. Para permanecer veraz, el mecanismo debe hacer lo mismo aquí, para que el trabajador 1 no se beneficie de mentir. Sin embargo, el tiempo de finalización se puede reducir a la mitad dividiendo los trabajos en${\displaystyle J_{2}}$equitativamente entre los agentes.

Por lo tanto, el factor de aproximación del mecanismo debe ser al menos 2.

Consideremos el caso especial de la programación de máquinas uniformes , en la que los trabajadores son monoparamétricos: para cada trabajador existe una velocidad, y el tiempo que tarda el trabajador en realizar una tarea es la duración de la tarea dividida por la velocidad. La velocidad es información privada del trabajador, y queremos incentivar a las máquinas a revelar sus velocidades reales. Archer y Tardos ^{[ 2 ]} demuestran que un algoritmo de programación es veraz si y solo si es monótono . Esto significa que, si una máquina informa una velocidad mayor, y todas las demás entradas permanecen iguales, entonces el tiempo total de procesamiento asignado a la máquina aumenta ligeramente. Para este problema:

• Auletta, De Prisco, Penna y Persiano ^{[ 3 ]} presentaron un algoritmo monótono de 4 aproximaciones, que se ejecuta en tiempo polinomial cuando el número de máquinas es fijo.
• Ambrosio y Auletta ^{[ 4 ]} demostraron que el algoritmo de tiempo de procesamiento más largo es monótono siempre que las velocidades de las máquinas sean potencias de algún c ≥ 2, pero no cuando c ≤ 1,78. Por el contrario, la planificación de listas no es monótona para c > 2.
• Andelman, Azar y Sorani ^{[ 5 ]} presentaron un algoritmo monótono de 5 aproximaciones, que se ejecuta en tiempo polinomial incluso cuando el número de máquinas es variable.
• Kovacz ^{[ 6 ]} presentó un algoritmo monótono de 3 aproximaciones.

Balkanski, Gkatzelis y Tan ^{[ 7 ]} estudian la planificación veraz de máquinas no relacionadas cuando, además de los informes de los agentes sobre sus tiempos de procesamiento, el algoritmo tiene acceso a predicciones de dichos tiempos. En este marco, el objetivo es obtener aproximaciones mejoradas cuando las predicciones son precisas ("consistencia") y aproximaciones casi óptimas en el peor de los casos cuando las predicciones son erróneas ("robustez"). Presentan un mecanismo veraz determinista politemporal que es 6-consistente y 2n-robusto. También demuestran que ningún mecanismo veraz determinista 1-consistente puede alcanzar una robustez acotada.