Pinwheel schemaläggning

Inom matematik och datavetenskap är pinwheel-schemaläggningsproblemet ett problem i realtidsschemaläggning med upprepade uppgifter av enhetslängd och hårda begränsningar för tiden mellan repetitioner.

Definition

Indata till schemaläggning av pinwheel består av en lista med uppgifter, som var och en antas ta tidsenhet per instansiering. Varje uppgift har ett associerat positivt heltalsvärde, dess minsta upprepningstid (minsta tiden från början av en instansiering av uppgiften till nästa). Endast en uppgift kan utföras åt gången.

Den önskade utmatningen är en oändlig sekvens som anger vilken uppgift som ska utföras i varje tidsenhet. Varje inmatningsuppgift bör visas oändligt ofta i sekvensen, med det största gapet mellan två på varandra följande instansieringar av en uppgift som högst lika med uppgiftens repeteringstid.

Till exempel skulle den oändligt upprepade sekvensen abacabacabac... vara ett giltigt pinwheel-schema för tre uppgifter a , b , och c med upprepningstider som är minst 2, 4 respektive 4.

Densitet

Om uppgiften som ska schemaläggas är numrerad från $1$ till $n$ , låt $t_{i}$ beteckna upprepningstiden för uppgiften $i$ . Då tätheten för ett pinwheel-schemaläggningsproblem $\textstyle \sum 1/t_{i}$ . För att en lösning ska existera krävs att densiteten är högst $1$ .

Detta villkor om densitet är också tillräckligt för att ett schema ska existera i det speciella fallet att alla upprepningstider är multiplar av varandra (till exempel om alla är två potenser ), eftersom man i det här fallet kan lösa problemet med hjälp av en osammanhängande täckning system . Att ha densitet högst $1$ är också tillräckligt när det finns exakt två distinkta upprepningstider. Det räcker dock inte i andra fall. I synnerhet finns det inget schema för tre poster med upprepningstider $t_{1}=2$ , $t_{2}=3$ och $t_ {3}$ , oavsett hur stor ${\displaystyle t_{3}} kan$$\displaystyle 5/6+1/t_{ 3}}$ , även om densiteten för detta system bara är .

$displaystyle 5/6} har$ högst $3/4$ har en lösning, och det har antagits att varje instans med densitet som mest lösning. Varje instans med tre distinkta upprepningstider och densitet högst $\displaystyle 5/6}$ har en lösning

Periodicitet och komplexitet

När det finns en lösning kan lösningen antas vara periodisk, med en period som högst är lika med produkten av upprepade gånger. Det är dock inte alltid möjligt att hitta ett upprepande schema med subexponentiell längd.

Med en kompakt ingångsrepresentation som anger, för varje distinkt upprepningstid, antalet objekt som har den repeteringstiden, är pinwheel-schemaläggning NP-hård .

Ansökningar

Tillämpningar av pinwheel-schemaläggning inkluderar schemaläggning av kommunikation mellan satelliter och en markstation, schemaläggning av underhåll av en samling objekt (som oljebyten för bilar), datorbehandling av multimediadata och konfliktlösning i trådlösa datornätverk i realtid.

externa länkar

• Pinwheel scheduling (1989) , Douglas B. West, University of Illinois