2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2017

 

Picerija „Bebrynė“

Taškai: 9

Picerijoje „Bebrynė“ tėra maža orkaitė, kurioje kepėjas vienu metu gali iškepti tik kelis patiekalus. Lentelėse parodyti visi įmanomi patiekalų kepimo „Bebrynės“ orkaitėje deriniai ir jų laikai.

Galimi deriniai

3 čiabatos

1 čiabata

1 didelė pica

1 maža pica

2 čiabatos

Kepimo laikas

Maža pica

10 min

Didelė pica

15 min

Čiabata

20 min

Picerija gauna daug užsakymų. Kepėjas turi suplanuoti kepimo laiką taip, kad svečiai galėtų pavalgyti kuo greičiau. Picos ir čiabatos gali būti dedamos į orkaitę kepti bet kuria eile. Patiekalas gali būti ištrauktas iš orkaitės tik visiškai iškepęs.

Šiuo metu užsakyta viena maža pica, dvi didelės ir 4 čiabatos. Kiek mažiausiai laiko truks užsakytų patiekalų kepimas? Įrašykite skaičių.
Paaiškinimas

Planuojant, kaip optimaliai naudoti išteklių (šiuo atveju pica, orkaitė), svarbu trumpiausias laikas.

Įprastas planavimo algoritmas yra ciklo algoritmas (angl. round robin algorithm). Procesas vykdomas „laukimo“ ciklu: kiekvienai užduočiai skiriamas fiksuotas procesoriaus laikas ir, jei šiai užduočiai reikia ilgesnio laiko, ji nustumiama į eilės galą.

Tokia strategija šiame uždavinyje neturi prasmės, nes negalima iš orkaitės išimti nebaigto kepti kepinio ir po kurio laiko jį kepti toliau.

Geriausia strategija – planuoti kepimą taip, kad visada orkaitė būtų užpildyta kepiniais. Tokiu atveju pasiekiamas trumpiausias laikas.

Raktiniai žodžiai: eilė, ištekliai, planavimas.

Atsakymas

Šį uždavinį galima spręsti keliais būdais. Svarbu pastebėti, kad 2 čiabatoms atskirai ir mažai picai iškepti reikia tiek pat laiko, kiek reikia dviem didelėms picoms atskirai ir dviem čiabatoms kartu iškepti. Tai trunka 50 min. ir visą šį laiką orkaitė yra užimta, kitaip tariant, tai trumpiausias kepimo laikas. Paveikslas kaip tik rodo galimą sprendimą.

Interaktyvi užduotis