sitelogo
工場での作業スケジューリングその１
MINERVA superseeded IF/Prolog. Please see http://www.ifcomputer.co.jp/MINERVA for details.

We discontinued to sell IF/Prolog Dec 31. 2003. For current customers, we continue to provide professional support for IF/Prolog until Dec 31, 2008.

工場での作業行程スケジューリング問題は、複数の機械で複数の異なる作業を行う環境において常に必要です。 工場では、複数の作業が同時に複数の機械で処理が可能ですが、できる限り速く目標とする作業をすべて仕上げるためのスケジュールが必要となります。

以下の例における「生産工場」では、M1型の機械が１台とM2型が２台、合計３台の機械が備えられています。　以下の表には、生産計画が表示されています。作業（ジョブ）は、JaからJdまであり、それぞれより細かい作業（タスク)に分類されます。タスクは異なる機械が決まった順序で、決められた時間をかけて処理します。 

           Job | Task | Machine | Duration
           ----|------|---------|---------
           Ja  | Ta1  |    M1   |    2
           Ja  | Ta2  |    M2   |    6
           Jb  | Tb1  |    M2   |    5
           Jb  | Tb2  |    M1   |    3
           Jb  | Tb3  |    M2   |    3
           Jc  | Tc   |    M2   |    4
           Jd  | Td1  |    M1   |    5
           Jd  | Td2  |    M2   |    2

以下に、上の制約を満たすスケジューリングの解を導く制約処理のプログラムを紹介します。 

:- import(const_domain).


program :- Jobs = [Ja,Jb,Jc,Jd],


M1_Tsk = [Ta1,Tb2,Td1],     M2_Tsk = [Ta2,Tb1,Tb3,Tc,Td2],
M1_Dur = [Da1,Db2,Dd1],     M2_Dur = [Da2,Db1,Db3,Dc,Dd2],
M1_Dur = [  2,  3,  5],     M2_Dur = [  6,  5,  3, 4,  2],


append(M1_Tsk,M2_Tsk,Tasks),
           append(M1_Dur,M2_Dur,Durations),


         Tasks in 0..100,      Jobs in 0..100,


           Ta2 ?>= Ta1 + Da1,    Tb2 ?>= Tb1 + Db1,
           Td2 ?>= Td1 + Dd1,    Tb3 ?>= Tb2 + Db2,


           Ja ?= Ta2 + Da2,      Jc ?= Tc + Dc,
           Jb ?= Tb3 + Db3,      Jd ?= Td2 + Dd2,


cumulative(M1_Tsk,M1_Dur,[1,1,1],1),
cumulative(M2_Tsk,M2_Dur,[1,1,1,1,1],2),
minimize_maximum(label(Tasks),Jobs),
print((Tasks,Durations,Jobs)).

プログラムでは、すべてのジョブとその所用時間に変数が割り当てられています。ジョブおよびタスクの所用時間には限界が設定されています。これは通常0-100にします。

第１の一連の制約では、各タスク間の依存関係を決定します。これは、プロジェクト計画例では通常すべてのタスクが正確な順序で行われることによります。

第２の一連の制約では、各ジョブの最後のタスクが終了したときに、ジョブ変数（Ja, Jb, Jc, Jd）が完了すると定めています。

cumulative/4の述語は、２つ型のマシンに対応しています。cumulative/4は内蔵制約述語で、様々な方法で使用することができますが、ここでは各機械が一度に一つのタスクしか行わないように制限をしています。cumulative/4は、タスク・その持続時間・その必要とする資源のデータのリストを受け取り、利用可能な資源の数に対して資源利用を制約します。

M1の機械上で行われるタスクのスケジュールは、M2のマシン上で行われるタスクのスケジュールとははっきりと切り離されています。ただ、M1とM2両方のマシンで行われねばならないタスクがある場合、ジョブ内のタスク間の依存関係により制約が生じます。

各ジョブの完了時間として定められている時間は、最適化が望まれている時間です。Ja-Jd変数の完了時間を最小に抑え、最終的なジョブが終了する時間を早くするようにします。minimize_maximimum/2 の述語は、繰り返し、タスク変数に様々な値を割り当てることにより、すべてのジョブ変数の最大完了時間を可能な限り短くし、上記の課題を達成します。

プログラムの実行により以下の結果が導き出されます。（0.01秒で結果がでます。） 

[user] ?- program.
[0,7,2,2,0,10,5,8] , [2,3,5,6,5,3,4,2]
, [8,13,9,10]
yes

結果として出てくるリストは、最適化されたタスク開始時間、必要時間、ジョブ完了時間に対応します。また、この結果は以下のように図の形式でも表すことができます。

戻る 続く..
冒頭へ managed with ubiCMS