qué algoritmo para un programa de programación

Question

Tengo este problema de tareas de programación. Cada tarea tiene un tiempo de inicio sugerido T (debe comenzar en [T-10, T + 10]), toma L minutos para completarse y utiliza una cantidad de recursos [R1, R2, ...]. Cuando se usa un recurso, ninguna otra tarea puede usarlo. Dado que solo la hora de inicio es flexible, mi objetivo es programar las tareas para que puedan acceder a cualquier recurso que necesiten o señalar todos los conflictos que deben resolverse.

¿Qué algoritmo puedo usar para este propósito? Gracias.

Answer 1

Puesto que usted ha etiquetado esto como prolog, recomiendo implementarlo en constraint logic programming (CLP) y el uso de los algoritmos incorporados en la implementación de CLP. Ejemplo parcial:

:- use_module(library(clpfd)). 

on_time([]). 
on_time([Task|Tasks]) :- 
    Task = task(TSuggested,TActual,L,Rs), 
    TActual #>= TSuggested - 10, 
    TActual #=< TSuggested + 10, 
    on_time(Tasks). 

otro predicado comprobaría que no hay dos tareas utilizan el mismo recurso al mismo tiempo:

nonoverlap(R,Task1,Task2) :- 
    Task1 = task(_,T1,L1,Rs2), 
    Task2 = task(_,T2,L2,Rs2), 
    ((member(R,Rs1), member(R,Rs2)) -> 
     T2 #> T1+L1  % start Task2 after Task1 has finished 
     #\/    % OR 
     T1 #> T2+L2  % start Task1 after Task2 has finished 
    ; 
     true   % non-conflicting, do nothing 
    ). 

Por último, llaman labeling sobre todas las variables restringidas para darles valores consistentes. Esto usa CLP(fd), que funciona para unidades de tiempo entero. CLP(R) hace lo mismo para tiempo real pero es un poco más complicado. Los enlaces son para SWI-Prolog pero SICStus y ECLiPSe tienen bibliotecas similares.

Answer 2

Los problemas de programación de este tipo a menudo se resuelven mejor utilizando la Programación de Restricción CP o la Programación de Entero Mixto (MIP). Ambos son enfoques declarativos, por lo que solo debe centrarse en las propiedades de su problema y dejar que un motor especializado maneje el algoritmo subyacente. Más información se puede encontrar en la wikipedia:

http://en.wikipedia.org/wiki/Constraint_programming

http://en.wikipedia.org/wiki/Linear_programming

Answer 3

Si eres restricciones o su dominio del problema escalará a cabo, también se debe echar un vistazo a los algoritmos imperfectos, tales como:

• Metaheuristics tales como la búsqueda tabú y recocido simulado. Hay un par de implementaciones de código abierto, como Drools Planner.

• Algoritmos genéticos, como JGap.