NP completo o NP hard problemi nella vita reale

Alcune delle cose che posso pensare (la maggior parte di queste sono state coinvolte in più o meno):

• Ambienti di sviluppo per linguaggi e compilatori. Domande come: questa grammatica genera un linguaggio ambiguo? (Questo problema è in realtà indecidibile!)
• Recupero dati. Riassemblaggio di pacchetti di dati parzialmente persi o recupero di file frammentati. (Complessità fattoriale)
• Sicurezza del software. Valutazione di tutti i possibili percorsi di esecuzione attraverso un pezzo di software per determinare se un comportamento osservato può essere attribuito ad esso. (Problema di interruzione?)
• Logistica. Ottimizzare l'uso dei trasporti basati sui pacchetti da trasportare, le loro dimensioni e il loro percorso. (Almeno esponenziale)

Esistono molti esempi standard come la ricerca del percorso più breve, la pianificazione degli infermieri, ecc. ma se si è interessati all'ottimizzazione combinatoria, si conoscono tutti questi aspetti:)

Ho usato la ricottura simulata a tempo limitato per risolvere un saleman itinerante come un problema nella produzione di touch panel. Ogni millisecondo che potremmo radere dal tempo di ciclo dell'incisione laser di ciascun pannello aumenterebbe il rendimento, l'utilizzo e quindi la redditività della macchina, quindi ho fatto un grande sforzo per ridurre al minimo i tempi morti (percorsi non di scrittura) tra tracciati di ovviamente non può essere ottimizzato)

Ho usato un algoritmo limitato nel tempo per aggirare la durezza NP del problema, in quanto non potevamo permetterci il rischio che il calcolo dell'ottimizzazione potesse richiedere più tempo del tempo risparmiato dal percorso più ottimale. Mentre la macchina spostava il pannello dalla posizione di caricamento alla posizione in cui la testa del laser si trovava sopra l'angolo più vicino, ho avuto il tempo di eseguire alcune simulazioni. L'algoritmo non arrivava quasi mai a completamento entro le poche centinaia di millisecondi del movimento, ma quasi sempre restituiva un percorso di scriba migliore di qualsiasi dei modelli semplici e non adattivi che avevamo sempre usato prima (come un percorso a spirale o un serpente).

Sto lavorando (proprio ora, in realtà) sul problema bioinformatico dell'allineamento di sequenze multiple di DNA locale. Il punto è che se un sacco di sequenze di geni con qualche proprietà comune (profilo di espressione simile o lo stesso fattore di trascrizione in un esperimento con chip ChIP) si allineano strongmente ad un certo punto, allora probabilmente hai trovato la ragione del loro comune proprietà. Poi di nuovo, sono più interessato agli aspetti statistici del problema. Anche se è NP-hard, non perdi molto usando l'euristica in pratica. La parte interessante del problema, IMHO, è un problema di rapporto segnale-rumore.

Non lo so, cosa NP completa / difficile significa, ma penso che fornire l'autoplanning sia un genere di questo.

Hai un piano di domanda di 90 giorni per 100 SKU di prodotto: birra! Il codice prodotto di 100 proviene da:

• ci sono 10-15 tipi di materiale grezzo di base di livello 1, sono prodotti in migliaia di lattine grandi e ci vuole un giorno;
• dopo la preparazione, alcuni materiali devono essere aggiunti (lievito?), e deve essere riposato per 10-15 giorni, quindi hai 15-20 tipi di materiale di livello 2;
• infine, quando è pronto, alcuni materiali dovrebbero essere aggiunti, è il materiale di livello 3, chiamato birra bevibile, ci sono cc. 30 tipi di birre;
• la birra può essere imbottigliata come 3 dl, 5 dl, a volte diventa necklacigng speciale (livello 4), quindi può essere confezionata in scatola 5x4, confezione da 6 (livello 5).

Ci sono "linee" di macchine per ogni operazione: dalla preparazione alla confezione. Le macchine possono eseguire più operazioni, ad esempio, alcune confezionatrici possono produrre 6-pack e 3-pack, ma altri possono fare solo 6-pack. Ci sono dei vincoli, ad es. velocità, o il grande bollitore è per la preparazione min. 6000, max, 8000 l di birra, (ma se il tipo di birra è leggero, il minimo è 5000 l e il massimo è 7000 l). E così via, ad ogni livello.

Il compito: come ho detto, c'è un piano di domanda, per il 100 tipo di livello-5 (il materiale in bottiglia, confezionato). Crea un piano di produzione ottimale per tutti i 5 livelli, tutte le macchine. Riduci al minimo gli interruttori macchina (ad esempio l'imbottigliamento .5, .5, .5, .3, .3, .3 è migliore di .3, .5, .3, .5, .3, .5, ci sono meno swithc, meno tempo morto per le macchine di imbottigliamento). Priorità per cliente: alcuni clienti richiedono di spedire la birra solo con più del 50% del tempo di scadenza rimanente. Ecc, ecc.

Scopri i colli di bottiglia (eh), crea piani alternativi con l'aggiunta di macchine inesistenti a questi punti, quindi il miglior scenario virtuale può essere usato per suggerire di acquistare una nuova macchina.

È abbastanza difficile, o dovrei dirti come funziona una fabbrica tessile ?

(Nota personale: il web, la banca e la logistica sono aree impegnative, ma sono giocattoli per bambini rispetto ai problemi di fabbricazione.)

Disclaimer: i numeri sono distorti per ragioni di sicurezza, l'ordine di grandezza è reale.