Don't have your page do so much.
If there are tasks that you can't cut out completely, create some sort of queueing mechanism. Have the page that's timing out add the jobs to the queue rather than performing the task itself. Process jobs from the queue periodically with a cron script.
The details of creating a queueing mechanism depend on the nature of the tasks, but the general aspects are fairly simple: you need a data store for job information and ways of adding, getting and removing jobs. Usually you store the data necessary to the job in a database table or a file (though in the latter case you'll need to handle concurrent access using e.g.
flock).
