Modellazione di un programma di lavoro complesso

10

Ho un problema del mondo reale che sto cercando di rappresentare e automatizzare. L'ho semplificato e riassunto in basso:

  • Ci sono n posti di lavoro (P1, P2, ..., Pn).
  • Ogni luogo, Pn ha una chiave, Kn.
  • Ci sono m lavoratori, (W1, W2, ..., Wm).
  • Per lavorare in Pn, un lavoratore deve tenere premuto Kn.
  • Ogni chiave può essere conservata da un lavoratore o lasciata allo scambio, E.
  • Un lavoratore può effettuare un viaggio nello scambio in qualsiasi momento per prelevare alcune chiavi non reclamate o rilasciare alcune chiavi che altri possono usare.

  • Ora, c'è un programma di lavoro esogeno che deve essere completato in un ordine rigoroso. Ad esempio:

    • 2016-04-21 W1 deve funzionare su P6
    • 2016-04-21 W2 deve funzionare su P3
    • ** necessario lo scambio di chiavi **
    • 2016-04-22 W3 deve funzionare su P3
    • 2016-04-22 W2 deve funzionare a P6
  • Un numero qualsiasi di lavoratori potrebbe dover lavorare a Pn in qualche momento nel loro pianificazione, anche se mai nello stesso giorno

Sappiamo:

  • La posizione iniziale di tutte le chiavi, sia con worker che con E
  • I futuri ordini di lavoro che ciascun lavoratore dovrà soddisfare

Quindi, sto lottando per modellare questa intera situazione. Puoi suggerire strutture e algoritmi di dati che dovrei guardare per controllarlo e iniziare a ottimizzare i viaggi nello scambio per ciascun lavoratore?

Quello che voglio minimizzare è il numero totale di viaggi verso E. Un obiettivo secondario sarebbe quello di garantire che nessun lavoratore faccia un numero sproporzionato di viaggi.

Grazie in anticipo !!

    
posta Gareth Lloyd 21.04.2016 - 13:50
fonte

1 risposta

1

La domanda è un po 'ambigua su un punto chiave: quali elementi stiamo cercando di risolvere. Stiamo cercando di ottimizzare l'ordine in cui le risorse sono delegate? Ridurre al minimo i viaggi nello scambio? Massimizzare il throughput degli ordini di lavoro?

Con questo in mente, assumerò che potremmo fare qualsiasi miscela di queste cose e mantenere la risposta ad un livello abbastanza alto.

La prima cosa che mi viene in mente è che i problemi interconnessi che questo tenta di risolvere sono per lo più incentrati sulla gestione delle dipendenze. Lavoratori, chiavi e luoghi possono essere pensati come dipendenze che devono essere risolti per completare i lavori di lavoro.

Portandolo al livello successivo, vorrei esaminare un adattamento dell'ordinamento topologico ( link ). Modella lo spazio dei problemi come un grande grafico (i database dei grafi moderni potrebbero essere un buon mezzo anche per alcune di queste analisi) e quindi utilizzare vari tipi topologici per risolvere i diversi aspetti dello spazio dei problemi.

Su una leggera tangente, sembra un progetto davvero divertente. Oggi ti invidio signore.

    
risposta data 23.09.2016 - 21:09
fonte

Leggi altre domande sui tag