流水作業のスケジュール--動的計画
問題の説明:
n個の作業{1,2,…,n}は、機械M 1とM 2からなる流水ラインで加工を完了する.
各作業加工の手順は、まずM 1に加工し、次にM 2に加工する.M 1とM 2の加工作業iに要する時間は、それぞれaiとbiである.
このn個の作業の最適な加工順序は、第1の作業から機械M 1において加工を開始し、最後の作業が機械M 2において加工が完了するまでに要する時間が最も少ないように決定することが要求される.
問題分析:直感的に、最適なスケジューリングは、マシンM 1に空き時間がなく、マシンM 2の空き時間が最も少ないようにしなければならない.一般的には、マシンM 2には、マシンの空きと作業の溜まりの2つがある.全ジョブの集合をN={1,2,...,n}とする.SはNのジョブサブセットである.通常、機械M 1がS中の作業を開始すると、機械M 2は他の作業を加工しており、時間tが経過してから利用できる.この場合Sでの作業完了に要する最短時間をT(S,t)と記す.流水作業スケジューリング問題の最適値はT(N,0)である.プロセス:1.{a 1,a 2,...,an,b 1,b 2,...,bn}を非減算シーケンスに配列する.2.シーケンスから最小要素mを順次抽出し、m=ajでジョブjがスケジューリングテーブルにまだ組み込まれていない場合は、ジョブjをスケジューリングテーブルが到達可能な一番左の空席に配置する(n個のジョブのスケジューリングテーブルにn項目があり、すべて空になる).3.m=bjであり、ジョブjがスケジューリングテーブルに組み込まれていない場合、ジョブjは、スケジューリングテーブルの最も右側の空席に配置される.4.ジョブjがスケジュール表に並べられている場合、シーケンスの次の最小要素mを取り、要素が取り出されるまで上記の方法でスケジュールを継続する.最後に得られたスケジューリングテーブルにおけるジョブの順序が各ジョブの加工順序である.例として、n=4、(a 1,a 2,a 3,a 4)=(3,4,8,10),(b 1,b 2,b 3,b 4)=(6,2,9,15)とし、ソート後(b 2,a 1,a 2,b 1,a 3,b 3,a 4,b 4)=(2,3,4,6,8,9,10,15)とする.セットσ1,σ2,σ3,σ4は最適なスケジューリングです.最小数はb 2なのでσ4= 2.次の小さい数はa 1で、置くσ1= 1.次はa 2で、宿題2はすでにスケジューリングされています.次にb 1ジョブ1もスケジューリングされている.次はa 3、置σ2=3、順次σ3= 4.アルゴリズム複雑度分析:アルゴリズムの主な計算時間はジョブセットのソートに費やされる.したがって,最悪の場合アルゴリズムに要する計算時間はO(nlogn)である.必要な空間はO(n)である.
コード実装:
サンプルと答え:
62 5 7 10 5 23 8 4 11 3 4答え1552 4 3 6 15 2 3 7答え19
n個の作業{1,2,…,n}は、機械M 1とM 2からなる流水ラインで加工を完了する.
各作業加工の手順は、まずM 1に加工し、次にM 2に加工する.M 1とM 2の加工作業iに要する時間は、それぞれaiとbiである.
このn個の作業の最適な加工順序は、第1の作業から機械M 1において加工を開始し、最後の作業が機械M 2において加工が完了するまでに要する時間が最も少ないように決定することが要求される.
問題分析:直感的に、最適なスケジューリングは、マシンM 1に空き時間がなく、マシンM 2の空き時間が最も少ないようにしなければならない.一般的には、マシンM 2には、マシンの空きと作業の溜まりの2つがある.全ジョブの集合をN={1,2,...,n}とする.SはNのジョブサブセットである.通常、機械M 1がS中の作業を開始すると、機械M 2は他の作業を加工しており、時間tが経過してから利用できる.この場合Sでの作業完了に要する最短時間をT(S,t)と記す.流水作業スケジューリング問題の最適値はT(N,0)である.プロセス:1.{a 1,a 2,...,an,b 1,b 2,...,bn}を非減算シーケンスに配列する.2.シーケンスから最小要素mを順次抽出し、m=ajでジョブjがスケジューリングテーブルにまだ組み込まれていない場合は、ジョブjをスケジューリングテーブルが到達可能な一番左の空席に配置する(n個のジョブのスケジューリングテーブルにn項目があり、すべて空になる).3.m=bjであり、ジョブjがスケジューリングテーブルに組み込まれていない場合、ジョブjは、スケジューリングテーブルの最も右側の空席に配置される.4.ジョブjがスケジュール表に並べられている場合、シーケンスの次の最小要素mを取り、要素が取り出されるまで上記の方法でスケジュールを継続する.最後に得られたスケジューリングテーブルにおけるジョブの順序が各ジョブの加工順序である.例として、n=4、(a 1,a 2,a 3,a 4)=(3,4,8,10),(b 1,b 2,b 3,b 4)=(6,2,9,15)とし、ソート後(b 2,a 1,a 2,b 1,a 3,b 3,a 4,b 4)=(2,3,4,6,8,9,10,15)とする.セットσ1,σ2,σ3,σ4は最適なスケジューリングです.最小数はb 2なのでσ4= 2.次の小さい数はa 1で、置くσ1= 1.次はa 2で、宿題2はすでにスケジューリングされています.次にb 1ジョブ1もスケジューリングされている.次はa 3、置σ2=3、順次σ3= 4.アルゴリズム複雑度分析:アルゴリズムの主な計算時間はジョブセットのソートに費やされる.したがって,最悪の場合アルゴリズムに要する計算時間はO(nlogn)である.必要な空間はO(n)である.
コード実装:
#include
#include
using namespace std;
class Jobtype
{
public:
int key;
int index;
bool job;
int operator >(Jobtype a) const
{
return (key>a.key);
}
};
void Shellsort(Jobtype *a,int n)
{
for(int dk=n/2;dk>0;dk/=2)
{
for(int i=dk;i=0 && a[j]>a[j+dk];j-=dk)
{
Jobtype t=a[j];
a[j]=a[j+dk];
a[j+dk]=t;
}
}
}
}
int FlowShop(int n,int a[],int b[],int c[])
{
Jobtype *d=new Jobtype [n];
for(int i=0;ib[i]?b[i]:a[i];
d[i].job=(a[i]<=b[i]);
d[i].index=i;
}
Shellsort(d,n);
for(int i=0;i>n;
for(int i=0;i>a[i];
for(int i=0;i>b[i];
int k=FlowShop(n,a,b,c);
cout< サンプルと答え:
62 5 7 10 5 23 8 4 11 3 4答え1552 4 3 6 15 2 3 7答え19