#1です。
リアルで15分は掛かりすぎですよね。
トレースを取るなどして、何にそれほど時間が掛かっているのかを解決すべきかと思います。
（10gなので Automatic Workload Repository（AWR）辺りで）
ご質問への解としては、一案として。
（結構、込み入った事をしています）
仮に、問題のSPを SP_OSOI とします。
4発パラレルでリソースを食い合う事無く、15分で終わる事が大前提となります。
まず、制御用テーブルを作ります。
NON-UNIQUEインデックスとして2つのSESSION-IDを持ちます。
（※PKでも大丈夫かな）
この値としては、userenv('SESSIONID') が入ります。
1つは、呼び出し側セッションのSESSION-ID、もう1つは（後述する）JOB起動されたセッションのSESSION-IDです。
それ以外は、処理済みフラグです。
SP_OSOIのラッパSP_OSOI_WRAPを作ります。
ラッパの仕事は、パラメータの授受と制御用テーブルの更新。
パラメータはSP_OSOI本来のパラメータ以外に、ラッパを呼び出す側から受け取るSESSION-IDです。
ラッパの中でSP_OSOI実行前に制御用テーブルにINSERTし、実行後に制御用テーブルを処理済みとして更新します。
呼び出し側のメインSPは、DBMS_JOBと動的SQLを使ってSP_OSOI_WRAPを4発実行します。
DBMS_JOB自体が非同期で実行するセッションとなるので、4発シリアルでもスルっと一瞬で流れるはずです。
その後は、JOBの時間を即時にすれば、SP_OSOIは、DBMS_JOBによって（ほぼ）パラレルで処理が流れます。
4発実行の後、LOOPで、自分のSESSION-IDがすべて処理済みになるまで制御用テーブルをSELECTし続けます。
ここは、CPU食いまくる処理になるのでLOOP内で5分くらいずつSLEEPした方がいいでしょう。
SLEEPの閾値をどの辺にするかによりますが、パラレルなので15～20分くらいで終わるはずです。
（理論的には）
補足
utakataXEXさん、ご回答と共に また、私の至らない点を補足していただきありがとうございます。 質問に回答いたします。 ・バッチ処理なのかリアルタイムなのか ⇒リアルタイムです。１プロシージャ１５分程度かかっておりますが、 ４回動かすため６０分かかっております。 ・遅いプロシージャは1つ？ ⇒一つです。 ・それを現在4回シリアルに実行している？ ⇒シリアルで実行しています。 ・それを単純に1回のパラレル処理にして、業務要件は担保できる？ ⇒問題ありません。 何か助言していただけることがありましたら、宜しくお願い致します。 ネットなどでもチューニングについては、調べておりますが、 チューニングについては、別途相談させていただきたいと思っております。