I denna artikel studeras problemet med att ändra beställningen av en plan för att optimera planen enligt olika kriterier. Ett av dessa kriterier är att göra en plan mindre begränsad och det andra är att minimera sin parallella genomförandetid. Tre kandidaturer föreslås för det första av dessa kriterier, som utgör en sekvens av ökande optimalitetsgarantier. Två av dessa bygger på avordningsplaner, vilket innebär att beställningsförhållanden endast kan tas bort, inte läggas till, medan den tredje använder omordning, där godtyckliga modifikationer av ordern är tillåtna. Det visas att endast den svagaste av de tre kriterierna kan uppnås, medan de andra två är NP-hårda och till och med är ungefärliga. På samma sätt studeras optimeringen av den parallella genomförandetiden för en plan både för avordning och omordning av planer. I det allmänna fallet är båda dessa beräkningar NP-hårda. Det har dock visat sig att optimal deordering kan beräknas i polynom tid för en klass av planeringsspråk baserat på begreppen producenter, konsumenter och hot, som omfattar de flesta vanliga planeringsspråk. Datoriska optimala omordningar kan potentiellt leda till ännu snabbare parallella utföranden, men detta problem är fortfarande NP-hård och di kult att approxima även under ganska stränga restriktioner.
I det allmänna fallet är detta problem NP-Hard och det är svårt att uppskatta REF.
Computational Aspects of Reordering Plans
{'venue': 'Journal Of Artificial Intelligence Research, Volume 9, pages 99-137, 1998', 'journal': None, 'mag_field_of_study': ['Computer Science']}