Coffman-Graham-algoritm

Coffman -Graham-algoritmen är en algoritm för att arrangera elementen i en delvis ordnad uppsättning i en sekvens av nivåer. Algoritmen väljer ett arrangemang så att ett element som kommer efter det andra i ordningen tilldelas en lägre nivå, och så att varje nivå har ett antal element som inte överstiger en fast breddgräns W . När W = 2 använder den minsta möjliga antal distinkta nivåer, och i allmänhet använder den högst 2 − 2/ W gånger så många nivåer som nödvändigt.

Den är uppkallad efter Edward G. Coffman, Jr. och Ronald Graham , som publicerade den 1972 för en ansökan inom schemaläggning av jobb . I den här applikationen är de element som ska beställas jobb, det bundna W är antalet jobb som kan schemaläggas vid en viss tidpunkt, och delordern beskriver förutsättningsrelationer mellan jobben. Målet är att hitta ett schema som slutför alla jobb på minimal total tid. Därefter har samma algoritm även använts vid grafritning , som ett sätt att placera spetsarna på en riktad graf i lager med fasta bredder så att de flesta eller alla kanter är riktade konsekvent nedåt.

För en partiell ordning som ges av dess transitiva reduktion (täckande relation), kan Coffman-Graham-algoritmen implementeras i linjär tid med hjälp av partitionsförfiningsdatastrukturen som en subrutin. Om den transitiva reduktionen inte är given tar det polynomtid att konstruera den.

Problembeskrivning och tillämpningar

I versionen av jobbbutikens schemaläggningsproblem som lösts av Coffman–Graham-algoritmen, ges man en uppsättning av n jobb J ₁ , J ₂ , ..., J _n , tillsammans med ett system av prioritetsbegränsningar J _i < J _j kräver att jobbet J _i slutförs innan jobbet J _j börjar. Varje jobb antas ta enhetstid att slutföra. Schemaläggningsuppgiften är att tilldela vart och ett av dessa jobb till tidsluckor i ett system med W identiska processorer, vilket minimerar tilldelningens längd (tiden från början av det första jobbet tills slutförandet av det sista jobbet). Sammanfattningsvis definierar prioritetsbegränsningarna en delordning på jobben, så problemet kan omformuleras till att tilldela elementen i denna delordning till nivåer (tidsluckor) på ett sådant sätt att varje tidslucka har högst lika många jobb som processorer (högst W- element per nivå), med respekt för prioritetsbegränsningarna. Denna applikation var den ursprungliga motivationen för Coffman och Graham att utveckla sin algoritm.

I det skiktade grafritningsramverket som beskrivs av Sugiyama, Tagawa & Toda (1981) är inmatningen en riktad graf , och en ritning av en graf är konstruerad i flera steg:

1. En återkopplingsbågeuppsättning väljs, och kanterna på denna uppsättning omkastas, för att omvandla ingången till en riktad acyklisk graf med (om möjligt) få omvända kanter.
2. Grafens hörn ges heltal y -koordinater på ett sådant sätt att, för varje kant, startpunkten på kanten har en högre koordinat än slutpunkten, med som mest W -hörn som delar samma y -koordinat. På detta sätt kommer alla kanter på den riktade acykliska grafen och de flesta kanterna på den ursprungliga grafen att orienteras konsekvent nedåt.
3. Dummy-hörn införs inom varje kant så att de uppdelade kanterna alla förbinder par av hörn som är i angränsande nivåer av ritningen.
4. Inom varje grupp av hörn med samma y -koordinat, permuteras hörnen för att minimera antalet korsningar i den resulterande ritningen, och hörnen tilldelas x -koordinater i enlighet med denna permutation.
5. Topparna och kanterna på grafen ritas med koordinaterna tilldelade dem.

I detta ramverk innebär y -koordinattilldelningen återigen att gruppera element av en delvis ordnad uppsättning (grafens hörn, med nåbarhetsordningen på vertexuppsättningen) i lager (uppsättningar av hörn med samma y -koordinater), vilket är problemet löst av Coffman-Graham-algoritmen. Även om det finns alternativa tillvägagångssätt än Coffman-Graham-algoritmen till skiktningssteget, kan dessa alternativ i allmänhet antingen inte införliva en gräns för den maximala bredden på en nivå eller förlita sig på komplexa heltalsprogrammeringsprocedurer .

Mer abstrakt kan båda dessa problem formaliseras som ett problem där indata består av en delvis ordnad mängd och ett heltal W . Den önskade utgången är en tilldelning av heltalsnivånummer till elementen i den delvis ordnade uppsättningen så att, om x < y är ett ordnat par av relaterade element i den partiella ordningen, är numret som tilldelas x mindre än talet som tilldelas y , så att som mest W- element tilldelas samma nummer som varandra, och minimerar skillnaden mellan de minsta och de största tilldelade talen.

Algoritmen

Coffman–Graham-algoritmen utför följande steg.

1. Representera den partiella ordningen genom dess transitiva reduktion eller täckande relation , en riktad acyklisk graf G som har en kant från x till y närhelst x < y och det inte finns något tredje element z i den partiella ordningen för vilket x < z < y . I grafritningsapplikationerna för Coffman–Graham-algoritmen kanske den resulterande riktade acykliska grafen inte är densamma som den graf som ritas, och i schemaläggningsapplikationerna kanske den inte har en kant för varje prioritetsbegränsning för inmatningen: i båda fallen , tar den transitiva reduktionen bort redundanta kanter som inte är nödvändiga för att definiera delordningen.
2. Konstruera en topologisk ordning av G där hörnen är ordnade lexikografiskt efter uppsättningen av positioner för deras inkommande grannar. För att göra det, lägg till hörnen en i taget till beställningen, välj i varje steg en vertex v att lägga till så att de inkommande grannarna till v alla redan är en del av den partiella ordningen, och så att den senast tillagda inkommande granne till v v är tidigare än den senast tillagda inkommande granne till någon annan vertex som skulle kunna läggas till i stället för v . Om två hörn har samma senast tillagda inkommande granne, bryter algoritmen ställningen till förmån för den vars näst senast tillagda inkommande granne är tidigare osv.
3. Tilldela topparna av G till nivåer i omvänd ordning av den topologiska ordning som konstruerats i föregående steg. För varje vertex v , lägg till v till en nivå som är minst ett steg högre än den högsta nivån för någon utgående granne till v , som inte redan har W -element tilldelade, och som är så låg som möjligt beroende på dessa två begränsningar.

Analys

Utgångskvalitet

Som Coffman & Graham (1972) ursprungligen bevisade, beräknar deras algoritm en optimal tilldelning för W = 2 ; det vill säga för schemaläggningsproblem med enhetslängdsjobb på två processorer, eller för skiktade grafritningsproblem med högst två hörn per lager. En närbesläktad algoritm hittar också den optimala lösningen för att schemalägga jobb med varierande längder, vilket möjliggör företräde för schemalagda jobb, på två processorer. För W > 2 använder Coffman–Graham-algoritmen ett antal nivåer (eller beräknar ett schema med en makespan) som ligger inom en faktor 2 − 2/ W av optimal. Till exempel, för W = 3 betyder detta att den använder högst 4/3 gånger så många nivåer som är optimalt. När begränsningarna för partiell prioritetsordning är en intervallordning eller tillhör flera relaterade klasser av partiella ordningar, hittar Coffman–Graham-algoritmen en lösning med det minsta antalet nivåer oavsett dess breddgräns.

Förutom att hitta scheman med litet intervall, minimerar Coffman–Graham-algoritmen (modifierad från presentationen här så att den topologiskt ordnar den omvända grafen av G och placerar hörnen så tidigt som möjligt snarare än så sent som möjligt) den totala flödestiden av två-processorscheman, summan av slutförandetiderna för de enskilda jobben. En relaterad algoritm kan användas för att minimera den totala flödestiden för en version av problemet där förbud mot jobb är tillåtet.

Tidskomplexitet

Coffman & Graham (1972) och Lenstra & Rinnooy Kan (1978) anger tidskomplexiteten för Coffman-Graham-algoritmen, på en partiell ordning av n -element, till O ( n ² ) . Denna analys utelämnar dock tiden för att konstruera den transitiva reduktionen, vilket inte är känt för att vara möjligt inom denna gräns. Sethi (1976) visar hur man implementerar det topologiska ordningsstadiet för algoritmen i linjär tid , baserat på idén om partitionsförfining . Sethi visar också hur man implementerar nivåtilldelningssteget för algoritmen effektivt genom att använda en disjunkt-uppsättning datastruktur . I synnerhet, med en version av denna struktur publicerad senare av Gabow & Tarjan (1985) , tar detta steg också linjär tid.