Qual è il modo migliore per ordinare algoritmicamente le scatole fisiche?

Question

Lavoro a tempo parziale all'UPS. Parte del mio lavoro consiste nel prendere scatole davanti a me, determinare se la gabbia corretta (1 su 6 gabbie in movimento) è dietro di me (vero circa il 50% delle volte) e quindi mettere la scatola nella gabbia o Di fronte a me. Possono esserci 6-20 scatole davanti a me in qualsiasi momento a seconda della dimensione della scatola (essenzialmente l'archiviazione disponibile per l'algoritmo di ordinamento). Ogni volta che una scatola viene rimossa viene sostituita con un'altra scatola a caso, se c'è spazio per quella scatola. Se la scatola successiva è particolarmente grande, potrebbe essere necessario rimuovere per prime 3-4 scatole (il che significa che la rimozione di una scatola non garantisce che una nuova scatola apparirà a meno che il numero totale di scatole non sia sufficientemente piccolo). Il numero di scatole può essere considerato infinito (UPS spedisce quasi tutte le scatole di Amazon, dopo tutto).

Sto cercando di capire la migliore strategia per ordinare queste scatole, parzialmente per lavorare più velocemente e in parte per divertimento.

---

Qualche altro dettaglio

• 2 scatole non possono essere ritirate contemporaneamente (possono essere fino a 70 libbre). Le scatole possono, tuttavia, essere scivolate lateralmente. Ciò significa che una scatola può essere raccolta e inserita tra altre scatole, ma due scatole non adiacenti non possono essere scambiate in un singolo movimento.
• Le scatole possono essere impilate. Tuttavia, lo stack deve ancora essere messo nelle gabbie una per una. Lo stacking può ridurre il numero di confronti necessari (perché conosci tutte le scatole in un determinato stack vanno in una determinata gabbia), ma non il numero di movimenti richiesti.
• Le scatole devono essere prelevate per essere valutate
• 1 gabbia scomparirà e una nuova gabbia apparirà ogni 10 secondi, in un ordine prevedibile
• Se la gabbia corretta non è dietro di me, devo attendere la gabbia o impostare la scatola sullo scaffale e selezionare una nuova scatola

Tempo computazionale (secondi)

• Raccogliere una scatola: 1
• Valutazione di una scatola: 2
• Posizionare una scatola nella sua posizione originale: 0
• Posizionare una scatola in una nuova posizione: 1

Esempi:

• Raccogliere una scatola, determinando che la gabbia corretta non è dietro di me e rimettendo la scatola da dove proviene: 3 secondi
• Raccogliere una scatola, determinare la gabbia corretta è dietro di me, posizionando la scatola nella gabbia: 4 secondi
• Raccogliere una scatola da una pila presortata e posizionarla nella gabbia corretta: 2 secondi
• Raccogliere una scatola e posizionarla in una gabbia senza ordinare: 2 secondi (più il tempo per trovare un nuovo lavoro)

Per il contesto, la tariffa corrente è di circa 700 scatole all'ora (5,14 secondi/scatola). Quindi ridurre il tempo medio per scatola di soli 0,5 secondi è un cambiamento abbastanza significativo.

Qual è il modo più efficiente in termini di tempo per spostare le scatole dallo scaffale alla gabbia corretta? Anche le soluzioni alle versioni semplificate di questo problema sono benvenute.