Izpitno vprašanje RAČ2PRA 15300

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka Sandra Perko.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.


Vprašanje

V podjetju Mutex d.o.o. izdelujejo kable za proizvajalce računalnikov. Ker nimajo najmodernejše opreme, kable izdelujejo kar delavci za tekočim trakom. Postopek izdelave izgleda takole: na trak položijo sestavine za kabel. Te pobere prvi delavec in naredi svoj košček dela. Ko konča, nadaljuje delo za njim drugi in tako do zadnjega delavca, ki dokonča izdelek. Dela so razporejena tako, da lahko delavci opravljajo delo v poljubnem vrstnem redu in delo posameznega delavca traja različno dolgo.

Nekega lepega dne pa so delavci zaprli tovarno in začeli stavkati. Nekateri izmed njih so namreč opazili, da nekateri neprestano delajo, medtem ko drugi skoraj ves čas počivajo - seveda ni mogoče, da bi tako še naprej delali! Kot svetovalec v podjetju pomagaj direktorju rešiti nastali problem tako, da zagotoviš, da bo kar najmanj delavcev čakalo na delo. To stori tako, da jih primerno razporediš za tekoči trak.


Odgovor

Ta primer rešimo po principu požrešne metode, za katero velja:

  • na vsakem koraku bi radi čimveč / čimmanj
  • zmeraj izberemo najboljše ta hip


Ker delavci opravljajo delo v poljubnem vrstnem redu, to pomeni, da nimamo že vnaprej nekih zahtev po razporeditvi. O delavcih je zato ključni podatek le, koliko časa potrebujejo, da opravijo svoj del za tekočim trakom.

Podatke o času delavcev shranimo v spremenljivke ti, za delavca di, potem pa ti uredimo naraščajoče za vsak i. Ker delavec na mestu k na traku čaka t1 + t2 + ... + tk-1, bo res čakal najmanj časa, če bodo pred njim delavci, ki porabijo manj ali enako časa kot dk.


Primer:

Imamo 8 delavcev, v spremenljivki t pa hranimo njihove čase za trakom, kjer vsaka komponenta t ustreza določenemu delavcu (di = t(i)). t=(2,6,8,1,9,10,3,15) in d=(d0, d1, d2, d3, d4, d5, d6, d7).

Vrednosti t-ja uredimo naraščajoče in dobimo vrstni red delavcev za trakom: d' = (d3, d0, d6, d1, d2, d4, d5, d7).

  • To pomeni, da bi prvi moral začeti z delom na traku 4. delavec, ki dela 1 enoto (skupen cas = 1)
  • drugi bi začel 1. delavec, ki čaka 1 enoto in dela 2 enoti (skupen čas = 1 + 2 = 3)
  • tretji bi začel 7. delavec, ki čaka 3 enote in dela 3 enote (skupen čas = 3 + 3 = 6)
  • četrti bi začel 2. delavec, ki čaka 6 enot in dela 6 enot (skupen čas = 6 + 6 = 12)
  • peti bi začel 3. delavec, ki čaka 12 enot in dela 8 enot (skupen čas = 12 + 8 = 20)
  • šesti bi začel 5. delavec, ki čaka 20 enot in dela 9 enot (skupen čas = 20 + 9 = 29)
  • sedmi bi začel 6. delavec, ki čaka 29 enot in dela 10 enot (skupen čas = 29 + 10 = 39)
  • in zadnji, osmi, bi začel 8. delavec, ki čaka 39 enot in dela 15 enot (skupen čas = 39 + 15 = 54)
Osebna orodja