A bit more explanation...
The script pulls a number of rows from the database, it loops through this data in a while loop.
Within this while loop, using the data, it adds information to a PDF page, created using PDF::API2, at the end it closes the database connection and saves the PDF. The time consuming bit is actually creating the PDF.
My thoughts at the moment, following on from suggestions here, are that the script is hogging the database connection, not allowing another instance of the script to access the database until the connection is closed by the other script. Secondly, perhaps however PDF:API2 works requires some other resource that is being locked by the system, and so each script has to wait. Or is the PDF creation simply so CPU intensive that it has no choice but to take more time.