HUGE

(Version 3.01)

  1. 概要
  2. 使用条件
  3. インストール
  4. 実行例（単独で使用する場合）
  5. 実行例（複数で使用する場合）
  6. データファイル
  7. 制限事項
  8. 最新版の入手
  9. 謝辞

概要

HUGEは，フローショップやジョブショップのスケジューリングを対話的に行うツールです。Java アプリケーションのため，Java の実行環境を導入すれば，幅広いオペレーティングシステムで実行できます。

主な機能は以下の通りです。

使用条件

作者への連絡（バグ報告，改善要望，質問など）は以下のアドレスまでお願いします。

mkatsumi@hiroshima-u.ac.jp

インストール

  1. 複数のファイルが複雑に関係していることより，実行形式をそのまま利用されることを前提に説明します。ソースファイルからコンパイルを行いたい方は，後半に述べるファイルを入手のうえ，コンパイルして下さい。ただし，コンパイル方法等の説明は割愛いたします。

  2. 自分のコンピュータ環境に対応した Java の実行環境もしくは開発環境を入手して下さい．HUGE は Java 2 SDK, version 1.3 によって開発しているため，古いバージョンのJVM(Java Virtual Machine)では正常に動かないと思われます。Java の実行環境等は Sun Microsystems, Inc. の Javaサイトや，IBM など，OS を開発している会社のサイトなどから入手できます。

  3. 次に，HUGEをダウンロードしてください。単独で使用される場合と，複数スケジューラで使用される場合でファイルが若干異なります．

    すべてのファイルをそのままハードディスク上に保存してください。なお，ソースファイル一式はこれです．必要のある方はダウンロードしてください．

実行例（単独で使用する場合）

  1. ダウンロードしたファイルをマウスでダブルクリックすれば実行できます(Windows系の場合）。ただし，ファイアウォールがある場合は，コマンドプロンプトから
    >java -Dhttp.proxyHost=proxyhost -Dhttp.proxyPort=portNumber -jar HUGE.jar [RETURN]
    と入力する必要があります．なお，この場合，Open URL による外部との交信スピードは非常に遅くなります．

  2. まずサンプルデータを入力してみましょう。先にダウンロードしたファイルにはデータ が含まれていません。そこでFile のメニューの２番目の Open URL...のダイアログを開くと，
    http://home.hiroshima-u.ac.jp/mkatsumi/open/HUGE/data/index.html
    のページが開きます．ここから，Three problems by Fisher and Thompson を選び，さらに 6-job, 6-machine problem を選ぶとこの問題が読み込まれます． その後，左下のInitial Schedule という枠の付いたボタン群の左側をクリックすると，ディスパッチング規則を選ぶことができます．その右側のGenerateというボタンをクリックすると，当該規則によって作られる初期スケジュールのガントチャートが中央に表示されます。

    （データをあらかじめ Netscape などのブラウザによってローカルディスクにダウンロードしておけば，Open File ダイアログから読み込むことも可能です。）

  3. HUGEのウインドウが小さい場合，使用環境に応じて広げてください。ただしガントチャートの表示はウインドウのサイズの変更と同期しません。そこで右下の４つの三角マークの付いたボタンをクリックしてみてください．縦軸や横軸が少しずつ伸び縮みします。

  4. ディスパッチング規則としてSPTを用いた場合，画面右下のCmaxが88となるはずです。この値は最後のオペレーションが完了した時刻であり，この問題では黄色に設定されたジョブJ_Bの第４オペレーションの完了時刻となっています。

    最大完了時刻最小化を目的としたスケジューリングでは，この値が小さくなるように，言葉を換えればチャートができるだけ左側につまった形になるように各機械でのオペレーションの順序と開始時刻を決定する必要があります。現在のスケジュールにはかなり“空き”がありますので，対話的にこのスケジュールの修正を試みます。

  5. まず黄色のボックスのいずれかでマウスをクリックして下さい。ジョブJ_Bの第１オペレーションから第６オペレーションまでの流れが黄色の線で表示されます。これを見ると，第２オペレーションと第３オペレーションの間がかなり空いています。そこで，第３オペレーションをもう少し前に移動させてみます。

  6. まず画面左上のStartというボタンをクリックすると，Select a boxという表示が下部に出ます。そこで，機械M_4で６番目に処理するジョブJ_Bの黄色のオペレーションをクリックします。すると，当該オペレーションが強調表示されるとともに，時間軸上に移動できる範囲が太い線で表示されます。ここでは赤いオペレーションの直後に移動させることにします。マウスを赤いボックスと水色のボックスの境目に移動させてクリックすると，時刻の確認が下部に表示され，左上のAcceptとCancelのボタンが選べる状態になります。Acceptをクリックすると，更新された新しいガントチャートが表示されます。（なお，Start，Accept，Cancel，そして Undoは，それぞれキーボードの s, a, c, u を押すことでも選択できます．）

    先の開始時刻の指示において，マウスの位置が少し前側にずれていると，赤いボックスが黄色のボックスの後ろに移動したガントチャートになっているかもしれません。その場合は左上のUndoをクリックして直前のガントチャートに戻し，改めて移動から指示しなおしてください。なお，開始時刻のポイントを指示するときに，SHIFTキーを押しながらクリックすると，直前のボックスのオペレーションの終了直後に当該オペレーションを位置づけるように開始時刻を計算します。時間軸が詰まっていて，正確な開始時刻をマウスで指示することが難しい場合に利用してください。

    また，CTRLキーを押しながら開始時刻を設定すると，そのオペレーションの最早開始時刻（時間軸上で太く表示された区間の先頭）に開始時刻を設定します。

  7. さて，黄色のジョブを機械M_4で２番目に処理するように変更するとCmaxの値は79へと改善されました。しかしながら，改めてガントチャートを見ると，機械M_5では黄色のオペレーションを時刻42から処理できるにも関わらず，実際には時刻55から開始するスケジュールとなっています。そこで，このオペレーションを最早開始時刻まで移動させると，Cmaxが73へと改善されます。

    いかがでしょうか。まだCmaxは小さくできそうです。さらに試行錯誤を重ねてみてください。ちなみにCmaxが55となるスケジュールが存在し，それがCmax最小化に対する最適スケジュールとなります。

  8. よいスケジュールが得られたら保存しましょう。FileのメニューからSave...のダイアログを選ぶと，保存用のダイアログが開きます。保存用の名前を指示すれば，そのファイルに問題のデータと，現在のスケジュールが保存されます。 このファイルをFileのメニューのOpen File...で読み込むと，スケジュールが再現されます。

  9. 一般にガントチャートは縦軸に機械を選びますが，ジョブがどの程度スムーズに流れているかを見るときには，縦軸をジョブにした方が分かりやすいでしょう。右上にあるV-AxisをクリックしてJobの方を選ぶと，縦軸をジョブとしたガントチャートに切り替わります。

  10. ガントチャート上に表示されたジョブ（あるいは機械）の色が気に入らない場合， 当該ジョブ（あるいは機械）のボックス上でマウスの「右ボタン」をクリックすると， 色を選ぶ画面が表示されます。

  11. ジョブに納期情報がある場合，個々のジョブの納期が時間軸の下に対応する線色で示されます。（縦軸をジョブにしている場合，各ジョブごとに納期のところに縦線が表示されます。）

  12. FileメニューのPrintを選ぶと現在の画面が印刷されます。HUGE はFileメニューの一番下のExitを選ぶことで終了します。

実行例（複数で使用する場合）


  1. ダウンロードしたファイル (HUGE301.jar と HUGE_Policy）のあるディレクトリにおいて以下のコマンドを入力してください． 

    >jar -xf HUGE301.jar [RETURN]

  2. さて，複数のスケジューラでシステムを使用する場合，１人がホスト，その他の全員がゲストという位置付けとなります．ホストは問題やスケジュールを全員に配付する役割を担い，スケジュール情報については配付するか否かを個別に指定できます（配付先は個別指定できません）．まず，ホスト側で，以下の手順を実行してください． 
    >start rmiregistry [RETRURN]
    なお，CLASSPATH を設定している場合は，あらかじめその設定をはずしておく方がよいはずです．

    次に，

    >java -Djava.security.policy=HUGE_Policy HUGE [RETURN]
    と入力すれば，ホスト側の初期画面が表示されます（Windows用にこのコマンドを記述したバッチファイルも用意しております）．後は名前とＩＤ（任意）を入力すれば，HUGEのメイン画面とコントロール用の補助画面が表示されます．HUGEのFileメニューから問題を読み込めば準備が整ったことになります．

    一方，ゲスト側は， 

    >java -Djava.security.policy=HUGE_Policy HUGE [RETURN]
    だけを入力すれば実行されます．ただし，ホスト側と異なり，途中でホストプログラムが走っているコンピュータのIPアドレスもしくは名前を入力する必要があります．

  3. 両者の準備がそろった時点で，ホスト側の補助画面の Start ボタンを押すと，ゲスト側のコンピュータの補助画面のDataというボタンが選択可能となります．これを押すと，スケジュールを入手できます．スケジュールのCmaxの値は全員で共有情報として参照できますが，対応するスケジュールそのものは，ホスト側の補助画面において Share と名付けたチェックボックにチェックが入っているもののみ，ゲスト側で参照可能となります．

  4. スケジュールを共有するという性格上，ホストならびにゲストともに，１種類の問題しか読み込めません．また，ゲストは問題をホストから受け取ることしかできません．さらに，ホスト，ゲストともに，自分のスケジュールは画面から消すことはできません（アイコン化することは可能です）．他の人のスケジュールは，View のチェックボックスを使って表示・消去できます．

データファイル

以下のファイルは簡単な３ジョブ３機械のジョブショップスケジューリング問題を あらわしています。 
<SCD1>
<DATANAME>
Sample 3-job, 3-machine problem.
</DATANAME>
<JOB>
JOB_A blue
JOB_B 0 255 255
JOB_C
</JOB>
<MACHINE>
MAC_1 yellow
MAC_2 pink
MAC_3 255 0 255
</MACHINE>
<OPERATION>
JOB_A MAC_1 4
JOB_A MAC_2 3
JOB_A MAC_3 2
JOB_B MAC_2 1
JOB_B MAC_1 4
JOB_B MAC_3 4
JOB_C MAC_3 3
JOB_C MAC_2 2
JOB_C MAC_1 3
</OPERATION>
<DUEDATE>
JOB_A 13
JOB_B 11
JOB_C 12
</DUEDATE>
</SCD1>
ファイルはまず<SCD1>と</SCD1>というブロック宣言文で囲まれている必要があります。その中で， <DATANAME> <JOB> <MACHINE> <OPERATION> <DUEDATE> そして <SCHEDULE> というサブブロックが“この順で”出現する必要があります。それぞれのサブブロックは対応する</...>で終わりを宣言します。なお<DUEDATE>のサブブロックは納期情報の無い問題では不要です。また<SCHEDULE>のサブブロックは完成したスケジュールの情報を格納する部分であり，作成したスケジュールを保存するときにシステムが自動的に書き込みます。よって通常は作成する必要がありません。

個々のサブブロックについて説明する前に，全体的な留意点をまとめます。

<DATANAME>サブブロック（必須）

データの名前や説明文を記入します。

<JOB>サブブロック（必須）

各ジョブの名前と色を指定します。ジョブ名は任意の文字列で指定でき，文字数に制限はありません。ジョブの色は，Java 標準の13色については文字列で指定できます。
Java 標準の13色：white, lightGray, gray, darkGray, black, red, pink, orange, yellow, green, magenta, cyan, blue.
上述のデータ例ではJOB_Aを青色に指定しています。ここに挙げた以外の色を指定したい場合には，Red, Green, Blue の３要素の強さを0から255の間の整数値で， この順に指定してください。上述の例ではJOB_Bがこのパターンによる指定となっており，Red:0, Green:255,Blue:255は cyan になります。色を指定しなかった場合は，システムがランダムに色を割り当てます。なお，ジョブ名と色指定の間には空白もしくはタブ記号を入れて下さい。また色をR, G, Bで指定する場合にはそれらの値の間にも空白もしくはタブ記号を入れてください。

<MACHINE>サブブロック（必須）

上述のジョブに対するサブブロックの説明と同様です。

<OPERATION>サブブロック（必須）

各ジョブごとに，“その処理順に”，加工機械名と加工時間を，空白もしくはタブ記号で区切ってならべてください。なお，加工時間には整数値しか使えません。たとえば上述のデータでは，ジョブJOB_AはMAC_1, MAC_2, MAC_3の順に加工を受ける必要があり，それらの加工時間は順に４, ３, ２単位時間となります。

<DUEDATE>サブブロック（任意）

ジョブに納期がある場合，ジョブ名と納期を空白もしくはタブ記号で区切ってならべてください。納期には整数値しか指定できません。納期が一部のジョブにしか設定されていない場合，システムは納期情報を考慮した取り扱い（評価値の計算や納期表示など）を行いません。

<SCHEDULE>サブブロック（任意）

スケジュール情報がある場合，このサブブロックにおいて，機械名，ジョブ名，オペレーション番号，開始時刻を，この順に，それぞれを空白もしくはタブ記号で区切ってならべます。オペレーション番号とは，各ジョブごとに処理順序にそって１から順に割り当てた番号です。 以下は上述の問題に対する一つの例です。データファイルにこのサブブロックが含まれている場合，システムはファイルを読み込んだ後に，そのスケジュールを直ちに表示します。 
<SCHEDULE>
MAC_3 JOB_B 3 9
MAC_3 JOB_A 3 7
MAC_1 JOB_C 3 9
MAC_2 JOB_A 2 4
MAC_1 JOB_B 2 4
MAC_2 JOB_C 2 7
MAC_3 JOB_C 1 0
MAC_2 JOB_B 1 0
MAC_1 JOB_A 1 0
</SCHEDULE>

制限事項

  1. 加工時間と納期はすべて整数値に限定されます。またすべてのジョブは時刻ゼロにショップに到着するものとします。

  2. データファイルにSCHEDULEサブセクションでスケジュールが与えられているとき，システムはそのスケジュールの実行可能性をチェックしません。

  3. データファイルの整合性チェックはかなり手を抜いていますので，表示されたガントチャートがおかしい場合，データファイルに間違いがないか再度確認してください。

  4. スケジュールをファイルに保存したとき，ジョブや機械の色指定情報はすべてR, G, Bに分解された整数値で保存されます。

  5. ジョブ名や機械名は任意の長さに設定できますが，ガントチャート上の縦軸では最初の（半角）６文字までしか表示されません。

  6. スケジュールの評価基準は メイクスパンのみとなっております．納期に関する評価基準も内部では計算しておりますが，表示の問題等から外部からは参照できません．必要な方はソースファイルを変更して下さい．

最新版の入手

最新版は作者のホームページから入手できます。 また代表的な問題についてのデータファイルならびに 最適解も上記サイトから入手できます。

謝辞

Apr. 21, 2001
mkatsumi@hiroshima-u.ac.jp