>Смотрите на бэкенд (apache, fastcgi или что у вас там). Видимо ему нужно
увеличить число процессов

тут проблема с алгоритмом: Надо запустить простенький скрипт, который положит в очередь команду на исполнение другого громоздкого скрипта. Кроном проверять очередь и если в ней есть команда на запуск тяжелого скрипта - то запускать его. И будет все летать.

Второй вариант, я использую для запуска в бэдграунде такую вот поделку http://code.google.com/p/php-forker
Он запускает тяжелый скрипт в бэдграунде и по аяксу я могу отследить прогрес исполнения тяжелого скрипта (если это конечно нужно и мы знаем кол-во циклов исполнения тяжелого скрипта)