Microsoft Solver è in grado di risolvere problemi di pianificazione complessi

1

Sto scrivendo un'applicazione che deciderà il piano di pianificazione per alcune decine di persone in base alla loro occupazione (ruolo) e disponibilità (giorno della settimana e ore).

Ho usato un foglio di calcolo Excel per aiutare a risolvere questo problema, sono stato quindi in grado di ideare un approccio logico e basato sulle decisioni per assegnare queste persone a turni e ruoli, seguendo alcuni set di vincoli.

Quando stavo per scriverlo in codice, mi è stato suggerito di provare Risolutore Microsoft . Ho letto un po 'sulle sue capacità, ma non ho familiarità con alcuni termini incontrati.

Bene, basti dire che non ho mai usato il Risolutore Microsoft e non so nemmeno se il seguente problema di pianificazione possa essere risolto con esso o meno. Finora ho trovato pochissimi esempi sui problemi di programmazione e anche quelli sono semplici al confronto.

Quindi la mia domanda è: Microsoft Solver può risolvere il seguente problema di programmazione?

Problema di pianificazione

Assegna le persone ai turni per un'intera settimana in base alla loro disponibilità e al ruolo che sono qualificati a ricoprire in seguito a una serie di vincoli e obiettivi.

Struttura

  • Le settimane sono composte da sette giorni.
  • I giorni sono composti da turni (l'alba, la mattina, il pomeriggio e la notte sono i più comuni). I turni sono specificati in questo modo:
    • Dawn: 00:00 AM - > 08:00
    • Mattina: 08:00 - > 12:00 AM
    • Pomeriggio: 01:00 PM - > 07:00
    • Notte: 07:00 PM - > 00:00 AM
  • Ci sono alcuni giorni della settimana che potrebbero non avere turni mentre altri possono averne uno, due o più.
  • Ogni persona ha una disponibilità settimanale che segue lo stesso giorno della settimana / struttura del turno.
    • Esempio: Peter è disponibile solo il lunedì sera (lunedì alle 19:00 - > 00:00 AM).
  • A volte le persone hanno due o più giorni in cui sono disponibili e vorrebbero che il loro programma ruoti attraverso questi.
    • Esempio: Kyle è disponibile solo mercoledì sera e giovedì mattina, inoltre vorrebbe ruotarli. Una settimana, mercoledì, un'altra settimana, giovedì.
  • Ogni persona ha una serie di ruoli che può riempire (uno o più).
    • driver
    • Medic
    • Dottore

obiettivi

  1. Ogni turno deve avere almeno: due autisti, un medico e tre medici.
  2. Ogni persona con disponibilità deve essere assegnata a un turno, non importa se uno spostamento ha tre piloti mentre un altro ne ha solo due.

Vincoli

  • Una persona può riempire solo un ruolo per turno.
  • Una persona può essere assegnata a un turno solo se ha la disponibilità per eseguirlo.
  • Una persona può essere assegnata a un ruolo solo se è qualificata per eseguirla.
  • Una persona può essere assegnata a un turno solo a settimana, a meno che l'organizzazione non sia a corto di personale (a corto di personale significa che abbiamo bisogno di più persone per riempire i turni per raggiungere l'obiettivo n. 1) . Se questo è il caso, si applica una condizione aggiuntiva quando si assegnano le persone ai turni dopo il primo.
    • Una persona assegnata a un secondo turno nella stessa settimana deve essere la persona che non ha eseguito un secondo turno per il tempo più lungo, pur soddisfacendo la disponibilità della persona e la capacità di ruolo.

Nota del moderatore: impossibile trovare i tag appropriati.

    
posta Fábio Antunes 26.06.2014 - 07:21
fonte

1 risposta

5

Se il Risolutore è appropriato dipende principalmente da come si costruisce il modello per il problema dato e se la dimensione del problema rimane entro i limiti del risolutore. Secondo questo sito , il limite per Il Risolutore Excel è composto da 200 variabili decisionali e 100 vincoli (promuovono anche il loro prodotto risolutore premium per problemi di dimensioni maggiori). Ma quando si utilizza Microsoft Solver Foundation direttamente da C # e non il componente aggiuntivo di Excel, i limiti sono molto più elevati, a seconda della variante del Risolutore su meno 5000 termini di vincoli .

Alcune idee su come costruire un modello:

  • puoi creare un modello che coinvolge una matrice 0-1 con una riga per "persona" e 28 colonne "turni della settimana" (supponiamo che ci siano 4 turni al giorno). I ruoli possono essere aggiunti estendendo l'intervallo del valore della matrice da 0-1 a 0-3, (0 = non assegnato, 1-3 assegnato per un ruolo specifico) quindi senza variabili decisionali aggiuntive.

  • o presumi che ogni persona prenda al massimo 3 turni alla settimana (anche nel caso di "carenza di personale"), puoi costruire il tuo modello in un modo diverso, usando le colonne per gli indici da 0 a 28, indicando a "primo turno della settimana, secondo turno, terzo turno" (0="non assegnato"). L'aggiunta dei ruoli a questo secondo modello può comportare 3 colonne di matrice aggiuntive per i ruoli del primo / secondo / terzo turno.

Quindi devi costruire i tuoi vincoli di conseguenza. Ad esempio il vincolo "ruoli minimi necessari per turno" comporterà almeno 3 x 28 vincoli di risolutore (3 per turno, sommando il numero di "ruoli" assegnati per quel turno e dicendo al risolutore quante persone sono attese al minimo per quel ruolo). Ciascuno dei quattro vincoli elencati sopra per le persone avrà bisogno di almeno un vincolo del risolutore corrispondente,

Spero che tu abbia avuto l'idea di come stimare la dimensione del problema da quanto sopra. Con questa stima, decidi tu stesso se questi limiti sono sufficienti per risolvere il tuo problema e quale variante del risolutore ti serve.

    
risposta data 26.06.2014 - 10:09
fonte

Leggi altre domande sui tag