このフォーラムではガントチャートとソートのプログラムを作成したのでその二つのプログラムと解説を発表することにします。
ソートはプログラムの勉強にうってつけの例ではないかと、私は思っています。でも、自分でそのように思っている割にはソートについての知識はほとんどありません。まあ、付け焼き場の知識ではありますが、一緒に簡単なソートについて勉強してみましょう。
ソートとはデータを大きい順(昇順)あるいは小さい順(降順)に並べ替えることです。どんな時に使うかというと、例を挙げればきりがないと思います。例えば、試験の結果を得点の高い順(降順)に並べ替えたり、パソコンの中に記憶されているファイルを新しいもの順に並べ替えたり、体育の時間なんかでは背の低い順に並ばせたりしますね。色々なことに活用できるわけです。 今回は、幾つかある数値データを昇順に並べ替えるもので選択法と呼ばれるプログラムを作ってみたいと思います。
今、ここに、「50,21,2,24,10」という5つの数値データがあるとしましょう。これを小さい順に並べ替えてみて下さい。並べ替えましたか?頭の中で結構ですから、実際に並べ替えてみてください。 並べ変えると「2,10,21,24,50」となります。合ってましたか?では、ここで一つ質問です。あなたはどういう考え方に基づいて数字の並べ替えを行いましたか? えっ?!と思いますよね。こんな簡単な事は考え方なんかほとんど意識すること無くやってのけることが出来ますね。では、今度は意識しながらやってみましょう。小さい順に並べるわけですから、やっぱりまず最初に一番小さい数を選び出そうと考えます。そしてそれは2ですね。 2を一番左に持ってきて、今度は二番目に小さい数(10)を選んで次は三番目に小さい数・・・というぐあいにあなたはやってきたわけです(ィそらく)。このアルゴリズムを図を使って説明します。
50 21 2 24 10 50と21を入れ替える
┗━━┛
比較
21 50 2 24 10 21と2を入れ替える
┗━━━━━┛
比較
2 50 21 24 10 2と24は入れ替えない
┗━━━━━━━━┛
比較
2 50 21 24 10 2と10も入れ替えない
┗━━━━━━━━━━┛
比較
2 50 21 24 10 一番小さい数が決まる。
↑ ┗━━┛ 今度は2番目に小さい数を探す
最小 比較
図2.ソートの様子
1: program sort(input,output);
2: var
3: i,j,cnt,w:integer;
4: data:array [1..10] of integer;
5: begin
6: writeln(`データの個数はいくつですか?`);
7: readln(cnt);
8: writeln(`データを入力して下さい`);
9: for i:=1 to cnt do readln(data[i]);
10: writeln(`ソート前`);
11: for i:=1 to cnt do writeln(data[i]);
12: {ここからソート作業}
13: i:=1;
14: repeat
15: j:=i+1;
16: repeat
17: if data[i]>data[j] then
18: begin w:=data[i];data[i]:=data[j];data[j]:=w;end;
19: j:=j+1;
20: until j>cnt;
21: i:=i+1;
22: until i>cnt-1;
23: {ソート作業はここまで}
24: writeln(`ソート後`);
25: for i:=1 to cnt do writeln(data[i]);
26: end.
それでは次はガントチャートのプログラムです。ガントチャートのプログラムとは言っておりますが、図を表示させるところは作りませんでした。製品をN個作る場合、それにかかる時間を、ガントチャートの考え方を利用して求めるプログラムと言ったほうがいいいかも知れません。
なお、このプログラムを作成するに当たって、高橋先生の生産管理の講義を参考にさせていただきました。
ガントチャートとは、作業にかかる時間をグラフ化した物です。簡単な例を以下に示します。
例えば、ある製品を作る時、3つの工程で加工されて一つの製品が出来上がるとします。3つの工程でかかる加工時間は、それぞれ、2分、3分、4分とし、製品を3つ作ることにしたとすると、ガントチャートは図2ようになり、この一連の作業には17分かかることが分かります。
+−−−−5−−−−10−−−−15−−−−20 (分)
第1工程 |□□■■△△
第2工程 | □□□■■■△△△
第3工程 | □□□□■■■■△△△△
□:1個目の製品,■:2個目の製品,△:3個目の製品
図2.ガントチャートの例(その1)
次に、それぞれの工程にかかる加工時間が2分、4分、3分であったらどのようになるでしょうか。ガントチャートは図3のようになり、作業時間は先程と同じ17ふんですが、この場合だと遊び時間(アイドルタイム)が発生してしまいます。
+−−−−5−−−−10−−−−15−−−−20 (分)
第1工程 |□□■■△△
第2工程 | □□□□■■■■△△△△
第3工程 | □□□*■■■*△△△
□:1個目の製品,■:2個目の製品,△:3個目の製品,*:遊び時間
図3.ガントチャートの例(その2)
プログラムを組む場合は、ただ加工時間を足していけばいいのではなく、アイドルタイムが発生した時の事を考慮しなければなりません。
このガントチャートに必要な情報は、工程の数と各工程の加工時間、そして、製作する製品の個数です。これらの情報が無ければガントチャートは書けません。
以上の情報が分かったとして、先程の例を用いて実際にどのように作っていけばいいかを考えていきましょう。
まず、iを工程の番号、jを製品の番号とし、第i工程でj番目の製品に加工を始める時間をstart(i,j)とします。同様に、加工が終了する時間をfinish(i,j)と表すことにします。また、第i工程で加工にかかる時間をt(i)とします。
上記のように設定すると、第i工程でj番目の製品の加工が終わる時間は
finish(i,j) = start(i,j) + t(i)
と表すことが出来ます。
すると、第1工程に着目した場合、それぞれのstartとfinishiは 次のように表す事が出来ます。
start(1,1) = 0
finish(1,1) = start(1,1) + t(1)
start(1,2) = finish(1,1)
finish(1,1) = start(1,1) + t(1)
・
・
・
start(1,j) = finish(1,j-1)
finish(1,j) = start(1,j) + t(1)
次に1番目の製品に関する場合、第i工程では次のように表すことが出来ます。
start(1,1) = 0
finish(1,1) = start(1,1} + t(1)
start(2,1) = finish(1,1)
finish(2,1) = start(2,1) + t(2)
・
・
・
start(i,1) = finish(i-1,1)
finish(i,1) = start(i,1) + t(i)
問題は2番目以降の製品の第2工程以降での加工開始時間の求め方です。図2および図3を見てもらうと分かりますが、アイドルタイムが発生する時と発生しない時では求め方が異なります。
アイドルタイムが発生しない場合、第i工程でj番目の製品に加工し始める時間は素直に、
start(i,j) = finish(i,j-1)
としてやっても大丈夫ですが、アイドルタイムが発生する場合は、
start(i,j) = finish(i-1,j)
としなければなりません(図4をジーっと眺めて下さい)。
要はfinish(i,j-1)とfinish(i-1,j)のどちらか大きい方を採用すればいいのです。
1: program gantt(input,output);
2: var
3: kosu,koutei,i,j:integer;
4: t:array[1..50] of integer;
5: start,finish:array[1..50,1..50] of integer;
6: begin
7: writeln(`製品の個数を入力して下さい`);readln(kosu);
8: writeln(`工程の数を入力して下さい`);readln(koutei);
9: writeln(`各工程の所要時間を入力して下さい`);
10: for i:=1 to koutei do readln(t[i]);
11: start[1,1]:=0;
12: for i:=1 to kosu do
13: finish[1,i]:=start[1,i]+t[1];start[1,i+1]:=finish[1,i];
14: for i:=1 to koutei do
15: finish[i,1]:=start[i,1]+t[i];start[i+1,1]:=finish[i,1];
16: for i:=2 to kosu do
17: begin
18: for j:=2 to koutei do
19: begin
20: if finish[i-1,j]<finish[i,j-1] then
21: start[i,j]:=finish[i-1,j]
22: else start[i,j]:=finish[i,j-1];
23: finish[i,j]:=start[i,j]+t[i];
24: end;
25: end;
26: writeln(`時間 →`,finish[koutei,kosu]);
27:end.
ここに載せた文章は、中央大学管理工学研究部が発行する機関誌RANDOMで連載したものを修正・加筆したものです。
ちょっと手抜きなところもありますが、当時の限られた時間の中で作られた文章やプログラムです。修正している今もレポートに追われている毎日で、満足なものに仕上げることが出来なかったのが残念です。特にガントチャートのプログラムはあまり深く考えずに作ったもので、違った計算結果が出るかも知れません。お恥ずかしい限りです。
以上、申し訳ありませんが、見苦しい弁解で終わらさせていただきます。
担当:佐藤