@techreport{R-94-22, PSURL = {/publications/cgi-bin/tr-fetch.pl?r-94-22+ps}, TITLE = {Executing Parallel Plans Faster by Adding Actions}, AUTHOR = {Christer B{\"a}ckstr{\"o}m}, YEAR = {1994}, NUMBER = {R-94-22}, INSTITUTION = ida, ADDRESS = idaaddr, ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-94-22+abstr}, ABSTRACT = {If considering only sequential execution of plans, the execution time of a plan will increase if adding actions to it. However, if also considering parallel execution of plans, then the addition of actions to a plan may sometimes decrease the execution time. It is further shown that plans which are sub-optimal in this way are likely to be frequently generated by standard partial-order planners. Unfortunately, optimizing the execution time of a plan by adding actions is NP-hard and cannot even be approximated within a constant ratio.}, IDANR = {LiTH-IDA-R-94-22}, NOTE = {This paper will appear in the proceedings of the 11th European Conference on Artificial Intelligence, Amsterdam, Netherlands, August 1994. Wiley}