Resumen

Consideramos un problema competitivo de programación de dos agentes en múltiples máquinas idénticas con fechas de liberación y anticipación. En el modelo de programación, hay dos agentes a y b con sus propios conjuntos de trabajos 𝒥a={J1a,...,Jnaa} y 𝒥b={J1b,...,Jnbb}, respectivamente. Cada trabajo Jj∈𝒥a∪𝒥b tiene una fecha de lanzamiento ri y los trabajos n=na nb deben programarse de forma preventiva en m máquinas idénticas. Para m=2, demostramos que la curva de compensación de todos los puntos óptimos de Pareto puede caracterizarse en tiempo polinómico. Cuando m es de entrada, mostramos que P|rj,pmtn|Lmaxa:Lmaxb≤Q puede resolverse en tiempo fuertemente polinómico.

• Materias:Matemáticas Análisis Matemático Álgebra Ingeniería Matemática aplicada Lógica matemática
• Subjects:mathematics Mathematical Analysis Algebra Engineering Applied Mathematics Mathematical logic
• Palabras claves:tiempo polinómico, problema de programación de agentes, m máquinas idénticas, múltiples máquinas idénticas, conjuntos de trabajos propios, fecha de liberación ri, trabajos na nb, puntos óptimos, fechas de liberación, modelo de programación
• Keywords:polynomial time, agent scheduling problem, m identical machines, multiple identical machines, own job sets, release date ri, na+nb jobs, optimal points, release dates, scheduling model