Devo risolvere un problema nel campo della ricerca di operazioni . Voglio raccogliere alcuni approcci generali per valutarli e scegliere i più promettenti per progettare un programma relativo ai problemi.
Definizione del problema
Azienda ACME che vende collage personalizzati e ha una produzione che aderisce ai principi di personalizzazione di massa.
Produzione
-
Un desk D dove vengono creati i collage (forse ci saranno più desk in futuro, ma non per ora)
-
Un collage C è composto da ...
- Diverse foto quadrate P
Possiamo considerare il collage come creato, quando viene creata l'ultima immagine quadrata necessaria.
- Indicatore M di colore T e capacità c_m
Una immagine viene disegnata con uno o più marker (s) dello stesso colore . Ogni immagine consuma una certa quantità di capacità del marcatore . È possibile che le immagini consumino più di un marker. I marcatori vuoti possono essere ricaricati, ma ciò richiede un tempo fisso.
Il cassetto è un androide che funziona 24 ore su 24 (dal momento che gli androidi non hanno ancora diritti umani) e può contenere marcatori più piccoli (c'è un limite, possiamo supporre 2 per ora), se un marker è vuoto, può passare al successivo e non perde tempo a causa del rabbocco. Cambiare il marker perché è necessario un altro colore , ci vuole anche del tempo.
I marcatori sono non sulla scrivania di Android, solo quella che usa attualmente. Arrivano al momento in cui sono in programma.
Il problema ora è pianificare le specifiche assegnazioni di quadri quadrati , le assegnazioni degli marcatori , ricariche marker e interruttori colore in modo che ogni singolo passo della produzione di collage sia pianificato considerando un alto tasso di output (che include il minimaziton degli interruttori di colore).
Domanda
Ho bisogno di aiuto per trovare algoritmi e idee per risolvere il problema. Forse ci sono alcune buone pratiche o istanze di problemi da mappare a cui non ho pensato. Per esempio. TSP , dove non sono sicuro di come applicarlo in questo caso speciale.
Le mie soluzioni / idee fino ad ora
- Ricottura simulata Le assegnazioni di Quadri quadri, assegnazioni di marcatori, ecc. sono considerate come eventi. Trova una permutazione degli eventi che minimizza la funzione di costo globale.
- Algoritmi delle classi d'asta Ogni assegnazione di quadri quadrati ottiene un bilancio in base al valore di ritorno di una funzione di costo per assegnazione . I compiti possono acquistare le risorse necessarie in una casa d'aste. Dopo un acquisto valido, la risorsa e il compito sono pianificati.
- Mappa per istanza del grafico (non so ancora come farlo) e trova il percorso con il peso minimo.
Informazioni aggiuntive
Esiste un livello di meta con un sistema di ERP (Enterprise resource planning) di livello superiore, che già esegue una pianificazione approssimativa. L'attività qui è la progettazione dettagliata come farebbe un MES (Manufacturing Execution System). Ma non conosco il numero di collage che devo pianificare in un dato periodo di tempo. So solo che si tratta di un problema in corso e che non è necessario utilizzare un algoritmo online. Il programma che intendo sviluppare viene chiamato su richiesta per programmare la produzione per alcuni giorni.
Ho trovato un modo per mappare il problema alla ricottura simulata e un altro approccio seguendo gli algoritmi della classe d'asta. Ho bisogno di aiuto per valutare questi approcci, o anche raccogliere nuove idee, le migliori pratiche per risolvere questo problema, dal momento che non ho mai affrontato un'istanza di problemi come questa prima. Per esempio. una risposta come dare un'occhiata all'algoritmo xyz potrebbe aiutarmi, o primi approcci a una mappatura del grafico.