Ändrad heuristik för schemaläggning för förfallodatum
Schemaläggningsheuristiken för modifierad förfallodatum (MDD) är en girig heuristik som används för att lösa problemet med enstaka maskins totala viktade försening (SMTWTP).
Presentation
Den modifierade schemaläggningen för förfallodatum är en schemaläggningsheuristik, skapad 1982 av Baker och Bertrand, som används för att lösa problemet med NP-hårda enstaka maskins totalviktade försening. Detta problem är centrerat kring att minska den globala försening av en lista över uppgifter som kännetecknas av deras handläggningstid, förfallodatum och vikt genom att beställa dem igen.
Algoritm
Princip
Denna heuristik fungerar på samma sätt som andra giriga algoritmer. Vid varje iteration hittar den nästa jobb att schemalägga och lägga till det i listan. Denna operation upprepas tills inga jobb lämnas oplanerade. MDD liknar heuristiken för tidigaste förfallodatum (EDD) förutom att MDD tar hänsyn till den delsekvens av jobb som redan har konstruerats, medan EDD bara tittar på jobbens förfallodatum.
Genomförande
Här är en implementering av MDD-algoritmen i pseudokod. Den tar in en osorterad lista med uppgifter och returnerar listan sorterad efter ökande ändrat förfallodatum:
funktion mdd(bearbetad, uppgift) returnerar max(bearbetad + uppgift.processtid, uppgift.förfallodatum) funktion mddSort(uppgifter) unsortedTasks = copy(uppgifter) sortedTasks = lista behandlad = 0 medan osorterade uppgifter inte är tom bestTask = unsortedTasks().getFir bestMdd = mdd(bearbetad, bästa Uppgift) för uppgift i osorterade uppgifter mdd = mdd(bearbetad, uppgift) om mdd < bestMdd då bestMdd = mdd bästa Uppgift = uppgift sorterade Uppgifter. pushBack (bestTask) osorterade uppgifter. remove (bestTask) processed += bestTask.processTime return sortedTasks
Praktiskt exempel
I det här exemplet kommer vi att schemalägga flygavgångar. Varje flygning kännetecknas av:
- ett förfallodatum: Den tid efter vilken planet förväntas ha lyft
- en bearbetningstid: Hur lång tid det tar för planet att lyfta
- a vikt: Ett godtyckligt värde för att specificera flygningens prioritet.
Vi måste hitta en order för flygningen att lyfta som kommer att resultera i minsta totala viktade försening. För detta exempel kommer vi att använda följande värden:
| Nr | Förfallodatum | Behandlingstid | Vikt |
|---|---|---|---|
| 1 | 12 | 8 | 2 |
| 2 | 18 | 9 | 5 |
| 3 | 10 | 5 | 2 |
| 4 | 14 | 6 | 8 |
I standardordningen är den totala viktade fördröjningen 136.
Det första steget är att beräkna det ändrade förfallodatumet för varje flygning. Eftersom den aktuella tiden är 0 och vi i vårt exempel inte har någon flygning vars förfallodatum är mindre än dess behandlingstid, är mdd för varje flyg lika med dess förfallodatum:
| Nr | Ändrad förfallodatum |
|---|---|
| 1 | 12 |
| 2 | 18 |
| 3 | 10 |
| 4 | 14 |
Flygningen med den minsta MDD (flyg nr 3) bearbetas sedan och det nya ändrade förfallodatumet beräknas. Klockan är nu 5.
| Nr | Förfallodatum | Behandlingstid | Ändrad förfallodatum |
|---|---|---|---|
| 3 | 10 | 5 | N/A |
| 1 | 12 | 8 | 13 |
| 2 | 18 | 9 | 18 |
| 4 | 14 | 6 | 14 |
Operationen upprepas tills inga fler flyg lämnas oplanerade. Vi får följande resultat:
| Nr | Förfallodatum | Behandlingstid |
|---|---|---|
| 3 | 10 | 5 |
| 1 | 12 | 8 |
| 4 | 14 | 6 |
| 2 | 18 | 9 |
I den här ordningen är den totala viktade fördröjningen 92.
Detta exempel kan generaliseras för att schemalägga vilken lista som helst med jobb som kännetecknas av ett förfallodatum och en handläggningstid.
Prestanda
Användning av denna heuristik kommer att resultera i en sorterad lista över uppgifter som inte kan minskas med en intilliggande parvis växling. MDD:s komplexitet är .
Variationer
Det finns en version av MDD som kallas viktad modifierad förfallodatum (WMDD) som tar hänsyn till vikterna. I ett sådant fall ersätts utvärderingsfunktionen med:
funktion wmdd(bearbetad, uppgift) return (1 / task.weight) * max (task.processTime, task.dueDate - processed)