Trasformazione grafica vincolata nelle applicazioni di pianificazione

Question

Sto lavorando a un'applicazione di pianificazione del lavoro interattiva. Dato un insieme di risorse con i relativi profili di capacità/disponibilità, un insieme di lavori da eseguire su queste risorse e una serie di vincoli che determinano la sequenza del lavoro e le ore di inizio/fine più recenti/più recenti per i lavori che voglio consentire all'utente di spostarsi manualmente lavori in giro Essenzialmente voglio che l'utente sia in grado di "afferrare" un nodo della rete di lavoro e trascinarlo avanti/indietro nel tempo senza violare nessuno dei vincoli.

L'immagine mostra una semplice configurazione di esempio. Il lavoro triangolare alla fine indica il tempo di fine ultimo per tutti i lavori, le linee di collegamento tra i lavori impongono un ordine sui lavori e le barre grigio/verde indicano la disponibilità e il carico delle risorse.

È possibile trascinare uno qualsiasi dei lavori per comprimere la pianificazione. Si noti che i lavori cambieranno di lunghezza a causa di diversi profili di capacità.

Ho implementato un algoritmo ad-hock che funziona. Tuttavia ci sono ancora casi in cui fallirà e violerà alcuni vincoli. Tuttavia, dal momento che la pianificazione del job-shop è un campo ben studiato con molti algoritmi ed euristiche per trovare una soluzione ottimale (o piuttosto buona) per il problema generale NP-rigido, penso che le soluzioni dovrebbero esistere per il mio sottoinsieme più facile. Ho esaminato argomenti di programmazione di vincoli e anche soluzioni basate sulla fisica (corpi rigidi collegati tramite giunti statici) ma finora non ho trovato nulla di adatto. Qualche suggerimento/suggerimento/consiglio/ricerca parole chiave per me?

Answer 1

Probabilmente è possibile modificare l'algoritmo di propagazione del vincolo di Valzer per gestire i vincoli di modifica per scoprire rapidamente se una determinata soluzione è valida. Non ho un riferimento a portata di mano, ma questo potrebbe puntare nella giusta direzione: http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYF-41C30BN-5&_user=809099&_rdoc=1&_fmt=&_orig=search&_sort=d&_docanchor=&view=c&_searchStrId=1102030809&_rerunOrigin=google&_acct=C000043939&_version=1&_urlVersion=0&_userid=809099&md5=696143716f0d363581a1805b34ae32d9

Answer 2

consiglio vivamente di dare un'occhiata a Mozart Oz, se le tue offerte problema solo con i numeri interi. Oz ha un eccellente supporto per la specifica del vincolo di dominio finito , l'inferenza e l'ottimizzazione. Nel tuo caso tipicamente si dovrebbe effettuare le seguenti operazioni:

1. specificare il vostro vincoli in maniera dichiarativa. In questo, devi specificare tutte le variabili e i relativi domini (ad esempio V1: 1 # 100, significa che la variabile V2 può assumere valori nell'intervallo 1-100). Alcune variabili potrebbero avere valori direttamente, ad esempio V1: 99. Inoltre, specificare tutti i vincoli sulle variabili.

2. Chiedere al sistema una soluzione: qualsiasi soluzione che soddisfi i limiti o una soluzione ottimale. Quindi visualizzerai questa soluzione nell'interfaccia utente.

3. Diciamo che l'utente modifica il valore di una variabile, potrebbe essere l'ora di inizio di attività. Ora puoi andare al passaggio 1 per inviare il problema al solutore Oz . Questa volta, la risoluzione del problema molto probabilmente non richiederà lo tanto prima quanto tutte le variabili sono già state istanziate.

   È possibile che l'utente abbia scelto un valore incoerente. In questo caso , il risolutore restituisce null. Quindi, è possibile portare l'interfaccia utente alla precedente soluzione .

Se Oz adatta alle proprie esigenze e ti piace la lingua, quindi si consiglia di scrivere un vincolo risolutore come un server in ascolto su un socket. In questo modo, è possibile mantenere il risolutore dei vincoli separato dal resto del codice, compresa l'interfaccia utente.

Spero che questo aiuti.

Answer 3

Avete considerato di utilizzare un motore di programmazione lineare intero (come lp_solve)? È abbastanza adatto per la pianificazione delle applicazioni.

Answer 4

vorrei votare a favore della programmazione con vincoli per diversi motivi:

1) CP sarà presto dire se non v'è alcun programma che risponde con efficienza i vostri vincoli

2) Sembrerebbe che si vuole dare voi utenti una soluzione fattibile per iniziare, ma consentire loro di manipolare i lavori al fine di migliorare la soluzione. CP è bravo anche in questo.

3) Un approccio MILP è solitamente complesso e difficile da formulare e devi creare artificialmente una funzione obiettivo.

4) CP non è così difficile da imparare in particolare per i programmatori esperti - in realtà viene più dalla comunità di informatica che dai ricercatori delle operazioni (come me).

Buona fortuna.