Denna uppgift är enkel. Det gäller helt enkelt att hitta en tid TA då summan av antalet jobb alla A-maskiner har hunnit göra >= N. Antalet jobb varje maskin har hunnit göra är TA / tid_per_jobb (avrundat nedåt).
Subtask B
Du ska hitta en tid då både process A och B är gjorda
för alla jobb. Du kan anta följande:
*Alla B-maskiner slutar med sitt sista jobb precis vid denna tid.
*Ingen B-maskin gör någon paus mellan två jobb.
Anledningen till att du kan anta detta är att om du har något
hål mellan två jobb eller mellan det sista jobbet och sluttiden
kan du alltid skjuta jobb mot framtiden så att hålen täcks
igen, det förlorar du ingenting på eftersom det bara är
sluttiden som räknas.
Observera nu att eftersom det inte finns några pauser mellan B-jobben och alla slutar samtidigt kan du använda precis samma algoritm som i Subtask A (fast för B-maskinerna) för att göra fördelningen av jobben. Då får du en minimal tid att utföra B för alla jobb. Kalla denna tid för TB. Du vill nu hitta en fördröjning d då du kan sätta igång det första B-jobbet, och sedan vill du bara kunna köra på och få en sluttid på d + TB.
Jag visar med en bild. Antag 3 A-maskiner (tider 2, 3 och 5), 4 B-maskiner (tider 3, 5, 6 och 8) och 7 jobb
A
B
........................tidsskala
[][][][] { }{ }{ }
[ ][ ] { }{ }
[ ]
{ }
{ }
TA = 8, TB = 10
I denna bild börjar inte B förrän A har avslutat sina jobb, d.v.s. d > TA. Så vill vi inte ha det. Vi vill minimera d, vilket betyder att vi ska skjuta ihop figuren ovan så mycket det går. Det villkoret som ska vara uppfyllt är att för varje t, där d <= t <= TA, ska det finnas minst lika många jobb i mellancontainern som det påbörjas jobb i B-maskinerna. Antalet som påbörjas i B-maskinerna vid en viss tidpunkt d + t är precis samma sak som antalet jobb som skulle avslutas vid en viss tidpunkt TB - t om alla jobb påbörjades vid 0 (inses om du vänder på tidsskalan). Detta värde kan alltså lätt beräknas genom ett tillägg i algoritmen i subtask A.
Hur många jobb finns det då i mellancontainern vid en viss tidpunkt. Jo, det är ju alla som A-maskinerna har avslutat vid den tidpunkten minus de som redan har använts av B-maskinerna. Man skulle kunna säga att man för ett visst d går igenom alla t och ökar mellanantalet när någon A-maskin är färdig med ett jobb och minskar mellanantalet med så många jobb som B börjar med vid denna tidpunkt. Ett d som är OK är då när mellanantalet aldrig går under 0.
Detaljerna återstår att implementera, men förhoppningsvis gav detta lite idéer. Avslutningsvis exemplet ovan med minimerat d-värde.
A B
...............tidsskala
[][][][]
[ ][ ]
[ ]
{ }{ }{ }
{ }{ }
{ }
{ }
001111311100 - antalet i mellancontainern innan B tar några
jobb
001110210100 - antalet som behövs i B-maskinerna
000001101000 - antalet som blir över i mellan-containern,
får aldrig gå under 0
d = 2, totaltid 12