Quale algoritmo (s) in grado di risolvere questo problema programmazione a vincoli?

Question

Ho bisogno di risolvere un problema di lavoro affettazione e mi piacerebbe trovare algoritmi efficienti preferibilmente per risolvere questo problema.

Diciamo che ci sono alcuni lavoratori che possono fare diversi tipi di compiti. Abbiamo anche una piscina di compiti che devono essere fatte ogni settimana. Ogni operazione richiede un certo tempo. Ogni attività deve essere presa da qualcuno. Ogni lavoratore deve lavorare tra N un'ora di P a settimana.

Questa prima parte del problema sembra essere un buon candidato per un algoritmo di programmazione a vincoli.

Ma qui è la complicazione: perché un lavoratore può fare diversi compiti possono anche avere le preferenze (o desideri). Se uno vuole soddisfare tutti i desideri per tutti non c'è soluzione al problema (troppi vincoli).

Così ho bisogno di un algoritmo per risolvere questo problema. Non voglio reinventare la ruota se la ruota perfetta esiste già.

L'algoritmo deve essere equo (se così si può definire questa parola) così per esempio dovrei essere in grado di aggiungere un vincolo come "cercare di soddisfare almeno un desiderio per le persone". Non sono sicuro che questo problema può essere risolto con metodi Constraint Gerarchie qui descritti: Constraint Herarchies . In realtà io non sono sicuro che "equità" e desideri possono essere espressi da vincoli validi per questa categoria di algoritmi.

C'è un esperto di programmazione a vincoli di darmi qualche consiglio? Ho bisogno di sviluppare una nuova ruota con alcune euristiche invece di usare algoritmi efficienti CP?

Grazie!

Answer 1

Il tuo problema è abbastanza complesso che una soluzione generale richiederà probabilmente formulare come un lineare intero problema. Se d'altra parte si è in grado di rilassarsi determinati requisiti, si può essere in grado di utilizzare un approccio più semplice. Ad esempio, bipartito corrispondenza permetterebbe di pianificare più lavoratori a più posti di lavoro, e può anche gestire preferenze, ma non sarebbe in grado di far rispettare i vincoli generali di correttezza ''. Vedi per esempio questo correlate, al fine in discussione . Vertex colorazione trovi algoritmi efficienti per far rispettare i vincoli di separazione lavoro.

Altri utenti hanno già detto simplex e negozio di job scheduling . Simplex è un algoritmo di ottimizzazione - attraversa uno spazio soluzione cercando di massimizzare qualche funzione obiettivo. Formulare la funzione obiettivo può certamente essere fatto, ma non è banale. Classica job shop scheduling, come corrispondenza bipartita, può modellare alcuni aspetti del problema, ma non tutti. Non ci sono vincoli di precedenza, per esempio. Ci sono versioni estese in grado di gestire alcuni vincoli, ad esempio ponendo limiti di tempo su compiti.

Se siete interessati a implementazioni esistenti, il Python NetworkX biblioteca ha un'implementazione di questa corrispondenza algoritmo . Un esempio di un programma di calendarizzazione open source che potrebbe essere di interesse è Tablix .

Answer 2

Ho fatto degli orari, che può essere considerato una forma di programmazione con vincoli. Hai vincoli rigidi (inviolabili) e vincoli soft (come ad esempio le preferenze di intervallo).

Programmazione lineare intera solito diventa inutile dopo più di 30 variabili, e questo può anche dire di simplex.

E 'stato trogolo ottimizzazioni specifici del dominio di algoritmi euristici che è stata trovata una soluzione.

Gli algoritmi euristici utilizzati erano simmulated ricottura , algoritmi genetici , metaeuristica algoritmi e simili, ma alla fine il miglior risultato sono stati forniti da un dominio "intelligente" personalizzato greedy algoritmo di ricerca .

In sostanza, si potrebbe ottenere alcuni risultati decenti con una delle euristiche qui, ma il problema principale è quello di essere in grado di discernere quando un problema viene sovravincolata.

Un grande strumento open-source per la ricerca è la HeuristicLab .

Answer 3

Sono d'accordo con quello che sono stati proposti qui. Tuttavia, MIP (Mixed Integer problemi di programmazione) di dimensioni molto grandi (ben oltre 30 variabili!) Sono praticamente risolti oggi grazie a codici commerciali (Xpress, CPLEX, Gurobi) o open-source (Coin-O / Cbc). Inoltre, linguaggi di modellazione di fantasia come l'OPL Studio, GAMS, AMPL, Flop ... permettono di scrivere con facilità modelli matematici invece di utilizzare le API.

È possibile usufruire di server di NEOS ( http: //neos.mcs .anl.gov / Neos / risolutori / index.html ) per provare molto esaily diversi MIP disponibili. Si invia il tuo modello in formato AMPL. Anche se AMPL si presenta come una versione gratuita limitata, NEOS in grado di gestire le istanze illimitate.

lingue di modellazione esistono anche per CP (COMET / OPL Studio) e Local Search (COMET).

Sentitevi liberi di entrare in contatto con me attraverso il mio sito web www.rostudel.com ( 'contatto' pagina)

David

Answer 4

Questo suona come negozio di Job Scheduling .