Algoritmo da utilizzare per l'allestimento del negozio?

8

Mi sono imbattuto in un problema di classe ieri (classe business oriented, non informatica) e l'ho trovato interessante da una prospettiva algoritmica.

Il problema è simile a questo:
Supponiamo che ci sia un piano di produzione con N stanze diverse e che tu abbia N reparti diversi che devono andare in quelle stanze. I reparti e le stanze sono tutti della stessa dimensione, quindi ogni reparto potrebbe andare in qualsiasi stanza. C'è una distanza di viaggio nota da ogni stanza all'altra stanza. C'è anche una quantità nota di viaggi necessari da un dipartimento all'altro (i viaggi vengono conteggiati allo stesso modo indipendentemente da quale stanza provengono, quindi un viaggio da A a B equivale a un viaggio da B a A). Dati tali input, determina un layout dei reparti in stanze che riduce al minimo il tempo di viaggio.

Qual è il modo migliore per affrontare questo problema algoritmicamente? Esiste già un particolare algoritmo o una classe di algoritmi progettati per risolvere questo tipo di problema? Questo tipo di problema ha un nome in informatica?

Non ti sto cercando di progettare un algoritmo per risolvere questo problema, anche se sentiti libero di farlo se vuoi. Mi chiedo se si tratta di uno spazio problema che è già stato ben definito e studiato algoritmicamente e in tal caso ottenere alcuni collegamenti per ulteriori ricerche. Riesco a vedere molte strutture e algoritmi di dati diversi che potrebbero applicarsi a questo e sono curioso di sapere quale approccio sarebbe "migliore".

E non preoccuparti, non stai facendo i miei compiti per me. Questo non è un problema per i compiti di per sé, poiché si tratta di un corso di business e stavamo semplicemente discutendo i concetti e non tentando di risolvere il problema in modo algoritmico.

    
posta RationalGeek 03.10.2012 - 16:18
fonte

3 risposte

13

Questo è chiamato Problema della posizione della struttura , che è un NP-hard problema. La tipica soluzione algoritmica a tale problema sta utilizzando gli algoritmi di approssimazione .

    
risposta data 03.10.2012 - 16:26
fonte
-1

Una soluzione pragmatica:

1) distribuire tutti i reparti a caso (mettere i nomi dei dipartimenti in una scatola e tirare fuori combinando con i numeri delle stanze); 2) dare a tutti i dipendenti nuove scarpe 3) misurare il consumo di scarpe (suole e talloni) dopo due settimane 4) metti i reparti le cui scarpe degli impiegati mostrano i maggiori consumi direttamente nelle vicinanze 5) ripetere questo metodo n volte (n = numero di reparti) 6) dopo n prove misurerai la media del consumo di scarpe e saprai qual è la migliore distribuzione dei reparti. Ma se fossi nei tuoi panni farei questa prova come esperienza mentale con l'aiuto di algoritmi (devi solo formalizzare questa procedura, se sei bravo in matematica, indovina già come ... se non lo trovi)

    
risposta data 31.12.2013 - 11:35
fonte
-2

Il modo più semplice è: ottenere il layout civile dell'edificio, contrassegnare le aree del dipartimento in modo pittorico utilizzando un foglio grafico (il modo migliore è usare Auto CAD o qualsiasi altro software 2D / 3D). Quindi devi valutare quanto spazio hai e come vuoi posizionare i reparti. Dal foglio, puoi ottenere le distanze di viaggio tra i dipartimenti.

    
risposta data 26.12.2012 - 13:22
fonte

Leggi altre domande sui tag