BOLT: apprendimento guidato da limiti inferiori basati su più colli di bottiglia per la schedulazione flessibile del job shop con ritardi temporali e trasporto accoppiato alle risorse

Abstract degli autori

La schedulazione flessibile del job shop diventa accoppiata alle risorse quando una flotta limitata di veicoli sposta i lavori tra le stazioni, perché è la schedulazione a determinare i tempi di attesa per il trasporto. BOLT (apprendimento orientato ai bound per la schedulazione con trasporto accoppiato) costruisce un limite inferiore a partire da rilassamenti delle catene, della capacità delle macchine e della capacità della flotta. Al termine, il limite coincide con il makespan, quindi le sue variazioni a ogni passaggio generano una ricompensa che, sommata, equivale a una costante meno il makespan. Poiché non supera mai il makespan raggiungibile, l’aumento del limite per ogni candidato corrisponde a un incremento dimostrabile del limite inferiore del makespan, che la policy interpreta come un prezzo. Il limite del nodo radice certifica il gap di subottimalità di una schedulazione completata senza ricorrere a un solver. Negli esperimenti su istanze di costruzione prefabbricata a 10 moduli, ispirate all’industria, l’accoppiamento esplicito del trasporto supera una policy basata su penalità per il trasporto in tutte le celle testate in cui i trasferimenti con carico occupano almeno il 66% del tempo della flotta, e in nessuna di quelle in cui ne occupano al massimo il 56%. In cinque lotti di produzione zero-shot da 50 e 80 moduli, BOLT supera la migliore coppia di regole di dispatching in quattro casi e la policy basata su penalità nei tre casi con trasferimenti lunghi. Nel lotto a 80 moduli con tre veicoli, il makespan medio di BOLT è inferiore del 13,0% rispetto a quello della migliore coppia e del 4,2% rispetto a quello di un solver di programmazione con vincoli con un budget di un’ora, il cui gap dimostrato è in media del 34%. BOLT prende decisioni in 2,3–5,9 ms per evento su un singolo core del processore e ripianifica un’interruzione in pochi secondi.