gyártási sorrend meghatározás

Algoritmusok

Sziasztok!

Kicsit aggasztó problémával küzdök itt, amire eddig nem sikerült kielégítő megoldást kiötlenem.

Adott n darab megmunkálandó anyag a megmunkálásához szükséges idővel és egy db gép, amely egyszerre k db anyagot tud megmunkálni, úgy, hogy a munkafolyamat akkor fejeződik be, amikor a gépben levő legnagyobb megmunkálási idejű anyag is elkészült. A gépbe az anyagokat kizárólag sorban lehet betenni (pl. 1. ; 2.3.4. ; 5..n; n+1..k)
Olyan algoritmus kellene, aminek segítségével a maximális megmunkálási időket minimalizálni kell, úgy, hogy a gépbe kizárólag sorban lehet betenni a megmunkálandó anyagokat és valahogy a csoportokat is nyilván kellene tartani.

Példa

anyagok: 10 15 30 5 20
gép kapacitás: 3
minimális összidő erre: 45 a sorrend {10 15} {30 5 20} -> 45=30+15

Az én ötletem az volt, hogy minden munkadarabra megnézem, hogy a körülötte levő k-1 sugarú környezetben melyik a legnagyobb munkaidejű anyag és ahhoz húzom hozzá (pl. a 10-es 30-ashoz, 15 is 30hoz, 30 a 20-hoz, 5->30, 20->30), így ki lehet alakítani egy sorrendet, azonban ez igencsak sok ideig tart nagy elemszám esetén, illetve a széleken lévő elemek kezelése nem biztos hogy működik.

Minden segítséget köszönök!

  • 2456 megtekintés

( Elbandi v | 2006. 10. 11., sze – 12:00 )

nemjo amit irtam

--
A vegtelen ciklus is vegeter egyszer, csak kelloen eros hardver kell hozza!

( coNP | 2006. 10. 11., sze – 12:18 )

"a maximális megmunkálási időket minimalizálni lehet": ezen pontosan mit is értesz?

( Morzel | 2006. 10. 11., sze – 13:15 )

Így, első ránézésre, amennyiben pontos a feladatleírás, és nem akarsz gondolkodni sem a megoldáson, tudom ajánlani a mesterséges intelligencia tárgy alap algoritmusait (a megoldáskereső algoritmusokat), bár ez egy kicsit ágyúval verébre megoldás is lehet. Ha egyszer lesz időm, és eszembe jut, megkukkantom a dolgot.

Morzel

( maszili | 2006. 10. 11., sze – 13:31 )

Az ilyen feladatot gráfalgoritmussal szokás megoldani...

Tegyük fel, hogy egy összetett tevékenység (pl.: egy termék előállítása, a továbbiakban nevezzük gyártásnak) felbontható résztevékenységekre. Szeretnénk készíteni egy gyártási technológiát, azaz a résztevékenységek olyan szekvenciális sorozatát, amelyet mintegy "receptet" végrehajtva, az összetett tevékenység elvégezhető (elkészíthetjük a terméket). Vegyük figyelembe, hogy a szekvenciális sorrendben bizonyos tevékenységeknek meg kell előzniük más tevékenységeket, különben fizikailag ellentmondásos lenne a technológiai leírás (pl.: a palacsintát addig nem tölthetjük meg, míg a tésztát meg nem sütöttük).

http://people.inf.elte.hu/fekete/docs_2/grafalg/grafalg.htm#dagtopmodell

--
maszili

( strangelove | 2006. 10. 11., sze – 15:20 )

NP-nehéz, legalábbis első lövésre, mélyebb meggondolás nélkül.

Speciális halmazfedési feladattal ekvivalensnek tűnik.
Illetve halmazpartícionálási problémának.
Kell-e még segítség?

Hi!

Sztem is halmazparticio ekvivalens. Egyebkent a Pannon Egyetem (Veszpremi Egyetem) Muszaki Informatikai Karanak Szamitastudomany Alkalmazasa Tanszeken az egyik kutatocsport hasonlo problemak algoritmikus megoldasaval foglalkoznak, az o altaluk hasznat eszkoz utemezesre az S-graf. A weboldal: http://www.s-graph.com/. Magam is foglalkoztam egy kis ideig a temaval.

( Galadh Ereb | 2006. 10. 18., sze – 22:35 )

Ahogy azt korábban mondták a probléma valóban tekinthető egy halmazefedési problémának, ahol halmazoknak súlyai is vannak. Ugyanakkor olyan könnyen nem kijelenthető, hogy ekvivalens is vele, mivel itt a halmazoknak azért van egy pár plusz speciális tulajdonsága, mint pl a max méret, illetve nincs olyan halmazrendszer,hogy a metszésgráfjuk tartalazzon egy legalább 3 hosszúságú olyan kört, melynek csúcsai között a kör éleit leszámítva nincs más él. (Az ilyen halmazrendszereknek van egy szép neve, de az most nem jut eszembe), ... Szóval így első ránézésre azért nem egy szimpla súlyozott halmazlefedési feladat (feltéve ha mindenki úgy gondolta ekvivalenssé tenni, ahogy én, de ezt most inkább hagyjuk), mert vannak plusz információink. Ettől függetlenül a többiekkel egyetértve a sejtésem nekem is az, hogy ezek a plusz infók nem segítenek annyit, hogy már ne legyen NP teljes a probéma. De ennek majd még utánagondolok, tetszik a feladat.

Ha megkérhetlek, privi üzenetben küldj el nekem több infót is a dologgal kacsolatban, mert tényleg érdekel maga a probléma. Gondolok itt olyanra, hogy az életben hol fordul elő pontosan, ott milyen kiegészítések kellhetnek, meg ilyesmik.

Csak annyi, hogy a halmazrendszer metszésgráfja merevkörű gráf, így hívják azokat a gráfokat, melyekben nincsen 3nál hosszabb feszített kör, ez a szép szó nem jutott eszembe. De egyébként a halmazrendszerünk alapból intervallumrendszer, tehát a metszésgráfja perfekt is. Nade mára ennyi elég is.

( fincsi | 2006. 10. 23., h – 14:22 )

Ha nem tevedek, akkor siman grafba rajzolod fuggosegeket, aztan PERT. (Program Evaluation and Review Technique)