スケジューリング装置
【課題】「一部の試験装置については、同一の試験装置、同一の治具、同一の試験条件で、異なる種類の部品をセットにして一緒に試験を行うことが可能」といった制約条件を考慮して、最適なスケジュールを作成する。
【解決手段】入力装置１によりスケジュールを作成するための各種の制約条件を入力し、スケジュール演算部２によりスケジュールを作成し、出力装置３からスケジュールを出力する。スケジュール演算部２では、割り付けできる可能性があるとして選択した「電子部品に対する試験」が、作業者及びバッチ処理が可能な試験装置が必要で且つ作業者及びバッチ処理が可能な試験装置が空いていると判定したときには、複数の「電子部品に対する試験」を同一の試験装置で同一の試験条件となるものどうしでグループにし、予め決めたグループ選択基準に基づき選択した一つのグループの「電子部品に対する試験」の開始・終了時刻をスケジュールに割り付けする。
【解決手段】入力装置１によりスケジュールを作成するための各種の制約条件を入力し、スケジュール演算部２によりスケジュールを作成し、出力装置３からスケジュールを出力する。スケジュール演算部２では、割り付けできる可能性があるとして選択した「電子部品に対する試験」が、作業者及びバッチ処理が可能な試験装置が必要で且つ作業者及びバッチ処理が可能な試験装置が空いていると判定したときには、複数の「電子部品に対する試験」を同一の試験装置で同一の試験条件となるものどうしでグループにし、予め決めたグループ選択基準に基づき選択した一つのグループの「電子部品に対する試験」の開始・終了時刻をスケジュールに割り付けする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、フローショップ型工程のスケジューリング装置に関し、バッチ処理が可能か否か等の設備能力を考慮することにより、総処理時間が短い最適なスケジュールを作成することができるように工夫したものである。
【背景技術】
【０００２】
ロケットや航空機などの製品には、多数・多種類の電子部品が組み込まれている。これら多数・多種類の電子部品は、製品に組み込む前に、環境ストレス試験が実施される。
環境ストレス試験を短時間で効率的に行うには、電子部品の試験順序を規定するスケジュールを最適に決める必要がある。
【０００３】
各電子部品は、作業者により又は試験装置により複数の試験を行う必要がある。いずれの電子部品も、試験は必ず決まった順番で行うが、電子部品によっては一部の試験を行わない（スキップする）ことが決まっている。
【０００４】
このように、全ての電子部品を、必ず決まった一定の順番で試験（ジョブ：処理）を行う（但し、一部の電子部品は所定のジョブをスキップすることも含む）工程のことを、フローショップ工程と呼んでいる。
【０００５】
例えば、
電子部品Ｐ１は、作業者による試験ｔ１，作業者による試験ｔ２，試験装置Ｔ３及び作業者による試験ｔ３，作業者による試験ｔ４，試験装置Ｔ５及び作業者による試験ｔ５を、この順番（ｔ１→ｔ２→ｔ３→ｔ４→ｔ５の順）に行い、
電子部品Ｐ２は、作業者による試験ｔ１，作業者による試験ｔ２，試験装置Ｔ３及び作業者による試験ｔ３，作業者による試験ｔ４，試験装置Ｔ５及び作業者による試験ｔ５を、この順番（ｔ１→ｔ２→ｔ３→ｔ４→ｔ５の順）に行い、
電子部品Ｐ３は、試験ｔ２，試験ｔ３，試験ｔ４は行わない（スキップする）が、作業者による試験ｔ１，試験装置Ｔ５及び作業者による試験ｔ５を、この順番（ｔ１→ｔ５の順）に行う。
このようなフローショップ型工程において、作業時間や納期遅れが最小になるように、各ジョブを各ショップでどのような順番で処理（試験）すべきかを決めることを、フローショップ型問題と呼んでいる。
【０００６】
各試験内容に応じて、使用する試験装置、治具、試験条件が決まっており、一部の試験装置については、同一の試験装置、同一の治具、同一の試験条件で、異なる種類の部品をセットにして一緒に試験を行うこと、即ち「バッチ処理」が可能である。
例えば、上記例では、試験装置Ｔ３はバッチ処理が可能であるが、試験装置Ｔ５はバッチ処理ができないようになっていることがある。
【０００７】
従来技術では、いわゆる一般的なフローショップ工程に対して、スケジューリングを行い、結果を表示する装置や方法が提案されてきた（例えば、特許文献１，２，３参照）。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開平１１−１８４９２３
【特許文献２】特開平０７−０７３２４４
【特許文献３】特開平０２−０４２５０３
【発明の概要】
【発明が解決しようとする課題】
【０００９】
「一部の試験装置については、同一の試験装置、同一の治具、同一の試験条件で、異なる種類の部品をセットにして一緒に試験を行うことが可能」といった「制約条件」を考慮してスケジュールを作成するには、従来では、上記の制約条件を人手で考慮し、試験スケジュールを作成していた。
このため、以下の問題が発生していた。
・設備能力を十分に活かした数量になっておらず、作業ロットが分かれる場合があり、効率が悪い。
・多くの情報を紙ベースで手作業により確認するため、手間がかかる。
・作業遅れが発生する。
・作業があふれる場合には、外注に流れてしまうことになり、追加費用が発生する。
【００１０】
また、特許文献１〜３に示す従来技術では、１つの装置（設備）に対し、１つの部品を扱う古典的なフローショップ問題を解くのに留まっており、本件で扱う問題のように、１つの装置（設備）に対して同時に複数種類の電子部品を扱えるケースには対応していない。
即ち、一般的なフローショップ工程に対するスケジューリングでは、１装置に対して１部品が原則であり、本件で扱うような、「一部の試験装置については、同一の試験装置、同一の治具、同一の試験条件で、異なる種類の部品をセットにして一緒に試験を行うことが可能」といった制約条件を考慮することができなかった。
【００１１】
本発明は、上記従来技術に鑑み、「一部の試験装置については、同一の試験装置、同一の治具、同一の試験条件で、異なる種類の部品をセットにして一緒に試験を行うことが可能」といった制約条件を考慮して、総処理時間の短い最適なスケジュールを作成することができる、スケジューリング装置を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記課題を解決する本発明の構成は、
複数の電子部品を、予め決めた試験順序にしたがって複数の試験をするフローショップ型工程のスケジュールを作成するスケジューリング装置であって、
各試験における「バッチ処理の可否」，「作業者の要否」，「試験装置の要否」に関する制約条件と、各電子部品の「個数」，「納期」に関する制約条件と、各電子部品について各試験を行うときの「試験条件及び試験時間」に関する制約条件と、作業者の人数と、各試験装置の台数を入力する入力部と、
前記入力部により入力された条件を基に、スケジュールを作成するスケジュール演算部とを有し、
前記スケジュール演算部は、
各電子部品に対する各試験のうち、開始・終了時刻の割り付けをしていないもので、開始・終了時刻の割り付けができる可能性がある「電子部品に対する試験」を選択し、
選択した「電子部品に対する試験」が、作業者のみが必要で且つ作業者が空いていると判定したときには、作業者のみが必要な「電子部品に対する試験」の開始・終了時刻をスケジュールに割り付け、
選択した「電子部品に対する試験」が、作業者及びバッチ処理ができない試験装置が必要で且つ作業者及びバッチ処理ができない試験装置が空いていると判定したときには、作業者及びバッチ処理ができない試験装置が必要な「電子部品に対する試験」の開始・終了時刻をスケジュールに割り付け、
選択した「電子部品に対する試験」が、作業者及びバッチ処理が可能な試験装置が必要で且つ作業者及びバッチ処理が可能な試験装置が空いていると判定したときには、複数の「電子部品に対する試験」を同一の試験装置で同一の試験条件となるものどうしでグループにし、予め決めたグループ選択基準に基づき選択した一つのグループの「電子部品に対する試験」の開始・終了時刻をスケジュールに割り付ける、という演算を次々と行うことによりスケジュールを作成する、ことを特徴とする。
【００１３】
また本発明の構成は、
前記スケジュール演算部は、
前記グループ選択基準として複数のグループ選択基準を有しており、
それぞれのグループ選択基準を用いて複数のスケジュールを作成し、
作成した複数のスケジュールのうち、総処理時間が最も短いスケジュールを最終的なスケジュールとすることを特徴とする。
【００１４】
また本発明の構成は、
前記グループ選択基準は、納期が最も早い電子部品が含まれているグループを選択する基準、または、一度に試験することができる量が最も多いグループを選択する基準、を含むことを特徴とする。
【発明の効果】
【００１５】
本発明によれば、「一部の試験装置については、同一の試験装置、同一の治具、同一の試験条件で、異なる種類の部品をセットにして一緒に試験を行うことが可能」といった制約条件を考慮することにより、総処理時間の短い最適なスケジュールを作成することができる。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施例に係るスケジューリング装置を示す構成図。
【図２】電子部品ごとの試験工程と試験条件に関する制約条件を示す表。
【図３】試験条件と試験時間に関する制約条件を示す表。
【図４】本発明の実施例の演算処理を示すフローチャート。
【図５】本発明の実施例で求めたスケジュールを示すガントチャート。
【図６】本発明の実施例の演算処理手順を示すタイムチャート。
【発明を実施するための形態】
【００１７】
以下、本発明の実施の形態について、実施例に基づき詳細に説明する。
【実施例１】
【００１８】
実施例１は、複数の電子部品を、予め決められた試験順序にしたがって、複数の試験をするフローショップ型工程のスケジュールを作成するスケジューリング装置１０である。
実施例１は、発明の理解を容易にするため、電子部品の種類を６種類（Ｐ１〜Ｐ６）、試験の数を５種類（ｔ１〜ｔ５）とした例である。
【００１９】
図１に示すように、スケジューリング装置１０は、入力装置１と、スケジュール演算部２と、出力装置３により構成されている。
スケジュール演算部２は、後述するスケジュール演算をするためのソフトウエア（プログラム）とハードウエア資源（コンピュータ）とが協働した具体的手段であり、フローショップ型工程のスケジュールを作成する特有の情報処理装置を構築している。
【００２０】
入力装置１は、例えば、図２に示す「電子部品ごとの試験（ジョブ：処理）工程と試験条件」に関する制約条件と、図３に示す「試験条件と試験時間」に関する制約条件と、作業者人数（本例では４人）に関する制約条件を、スケジュール演算部２に入力する。
【００２１】
図２に示す「電子部品ごとの試験工程と試験条件」に関する制約条件と、図３に示す「試験条件と試験時間」に関する制約条件について、更に説明すると、次の通りである。
【００２２】
各試験ｔ１〜ｔ５における、「バッチ処理の可否」、「作業者の要否」、「試験装置の要否」に関する制約条件がある。
具体的には、図２に示すように、
・試験ｔ１では、バッチ処理は不可（×）、作業者は必要（○）、試験装置は不要（×）であり、
・試験ｔ２では、バッチ処理は不可（×）、作業者は必要（○）、試験装置は不要（×）であり、
・試験ｔ３では、バッチ処理は可能（○）、作業者は必要（○）、試験装置（試験装置Ｔ３）は必要（○）であり、
・試験ｔ４では、バッチ処理は不可（×）、作業者は必要（○）、試験装置は不要（×）であり、
・試験ｔ５では、バッチ処理は不可（×）、作業者は必要（○）、試験装置（試験装置Ｔ５）は必要（○）である。
この例においては、試験ｔ５で用いる試験装置Ｔ５ではバッチ処理は不可（×）であるのに対して、試験ｔ３で用いる試験装置Ｔ３ではバッチ処理は可能（○）であることに着目して、後述するスケジュール演算をしていることが、特徴の一つである。
なお、本例では、試験装置Ｔ３は１台であり、試験装置Ｔ５も１台である。このような各試験装置の台数も、入力装置１によりスケジュール演算部２に入力される。
【００２３】
各電子部品Ｐ１〜Ｐ６の「個数」、「納期」に関する制約条件がある。
具体的には、図２に示すように、
・電子部品Ｐ１では、「個数」は１０個、「納期」は2011年4月30日であり、
・電子部品Ｐ２では、「個数」は１０個、「納期」は2011年4月30日であり、
・電子部品Ｐ３では、「個数」は１０個、「納期」は2011年7月31日であり、
・電子部品Ｐ４では、「個数」は１０個、「納期」は2011年5月31日であり、
・電子部品Ｐ５では、「個数」は１０個、「納期」は2011年5月31日であり、
・電子部品Ｐ６では、「個数」は１０個、「納期」は2011年7月31日である。
【００２４】
各電子部品Ｐ１〜Ｐ６について各試験ｔ１〜ｔ５を行うときの「試験条件及び試験時間」に関する制約条件がある。
具体的には、図２、図３に示すように、
・電子部品Ｐ１に関しては、試験ｔ１では試験条件ｃ１で１個当たりの試験時間は0.02時間、試験ｔ２では試験条件ｃ２で１個当たりの試験時間は0.01時間、試験ｔ３では試験条件ｃ３−１で試験時間は２１分、試験ｔ４では試験条件ｃ４で１個当たりの試験時間は0.01時間、試験ｔ５では試験条件ｃ５で試験時間は６分であり、
・電子部品Ｐ２に関しては、試験ｔ１では試験条件ｃ１で１個当たりの試験時間は0.02時間、試験ｔ２では試験条件ｃ２で１個当たりの試験時間は0.01時間、試験ｔ３では試験条件ｃ３−１で試験時間は２１分、試験ｔ４では試験条件ｃ４で１個当たりの試験時間は0.01時間、試験ｔ５では試験条件ｃ５で試験時間は６分であり、
・電子部品Ｐ３に関しては、試験ｔ１では試験条件ｃ１で１個当たりの試験時間は0.02時間、試験ｔ５では試験条件ｃ５で試験時間は6分であり、試験ｔ２，ｔ３，ｔ４はスキップし、
・電子部品Ｐ４に関しては、試験ｔ１では試験条件ｃ１で１個当たりの試験時間は0.02時間、試験ｔ２では試験条件ｃ２で１個当たりの試験時間は0.01時間、試験ｔ３では試験条件ｃ３−２で試験時間は３６分、試験ｔ４では試験条件ｃ４で１個当たりの試験時間は0.01時間、試験ｔ５では試験条件ｃ５で試験時間は６分であり、
・電子部品Ｐ５に関しては、試験ｔ１では試験条件ｃ１で１個当たりの試験時間は0.02時間、試験ｔ２では試験条件ｃ２で１個当たりの試験時間は0.01時間、試験ｔ３では試験条件ｃ３−２で試験時間は３６分、試験ｔ４では試験条件ｃ４で１個当たりの試験時間は0.01時間、試験ｔ５では試験条件ｃ５で試験時間は６分であり、
・電子部品Ｐ６に関しては、試験ｔ１では試験条件ｃ１で１個当たりの試験時間は0.02時間、試験ｔ５では試験条件ｃ５で試験時間は６分であり、試験ｔ２，ｔ３，ｔ４はスキップしている。
この例においては、バッチ処理が可能な試験ｔ３において、電子部品Ｐ１，Ｐ２に関しては試験条件ｃ３−１で試験時間は２１分であるのに対して、電子部品Ｐ４，Ｐ５に関しては試験条件ｃ３−２で試験時間は３６分であることに着目して、後述するスケジュール演算をしていることが、特徴の一つである。
【００２５】
スケジュール演算部２は、入力装置１から上記の各制約条件（図２、図３参照）が入力されると、図４のフローチャートに示すスケジュール演算（詳細は後述する）をして、図５のガントチャートに示すスケジュールを作成する。
作成されたスケジュール（図５参照）は、出力装置３から出力されて、画面表示されたりプリントアウトされたりする。
【００２６】
ここでスケジュール演算部２によるスケジュール演算手法を、図４のフローチャートに基づき説明する。
【００２７】
まず、各電子部品に対する各試験の開始・終了時刻のスケジュールへの割り付けが全て終了したか否かを判定する（ステップＳ１）。
【００２８】
各電子部品に対する各試験の開始・終了時刻のスケジュールへの割り付けが全て終了していないと判定したときには、各電子部品に対する各試験のうち、開始・終了時刻の割り付けをしていないもので、開始・終了時刻の割り付けができる可能性がある「電子部品に対する試験」を選択する（ステップＳ２）。
ステップ２でいう、『開始・終了時刻の割り付けができる可能性がある「電子部品に対する試験」』とは、各電子部品に対して順番に行う試験のうち、まだ試験が行われていない最も順番の早い試験のことを意味している。
【００２９】
選択した「電子部品に対する試験」が、作業者のみが必要か、または、作業者と試験装置が必要かを判定する（ステップ３）。
【００３０】
選択した「電子部品に対する試験」が、作業者のみが必要と判定したときには、作業者が空いているか否かを判定する（ステップ４）。
【００３１】
作業者が空いていないと判定したときには、作業者が空く時間まで待ち（ステップ５）、ステップＳ２に戻る。
作業者が空いていると判定したときには、作業者のみが必要な「電子部品に対する試験」の開始・終了時刻をスケジュールに割り付ける（ステップＳ６）。その後、ステップＳ１に戻る。
【００３２】
ステップＳ３において、選択した「電子部品に対する試験」が、作業者と試験装置が必要と判定したときには、作業者と試験装置が空いているか否かを判定する（ステップＳ７）。
【００３３】
作業者と試験装置が空いていないと判定したときには、作業者と試験装置が空く時間まで待ち（ステップＳ８）、ステップＳ２に戻る。
作業者と試験装置が空いていると判定したときには、空いている試験装置はバッチ処理が可能か否かを判定する（ステップＳ９）。
【００３４】
空いている試験装置はバッチ処理が可能でないと判定したときには、作業者と試験装置が必要な「電子部品に対する試験」の開始・終了時刻をスケジュールに割り付ける（ステップＳ１０）。
【００３５】
空いている試験装置はバッチ処理が可能であると判定したときには、複数の「電子部品に対する試験」を、同一の試験装置で同一の試験条件となるものどうしでグループにする（ステップＳ１１）。
【００３６】
ステップＳ１１でグループ化した後、納期が最も早い電子部品が含まれているグループの「電子部品に対する試験」の開始・終了時刻をスケジュールに割り付ける（ステップＳ１２）。その後、ステップＳ１に戻る。
【００３７】
ステップＳ１で、各電子部品に対する各試験の開始・終了時刻のスケジュールへの割り付けが全て終了したと判定したら、スケジュール作成を完了する（ステップＳ１３）。
【００３８】
次に、図５に示すガントチャート及び図６に示すタイムチャートに基づき、スケジュール演算部２によるスケジュール演算の具体例を説明する。
【００３９】
時刻が０時００分においては、電子部品Ｐ１に対する試験ｔ１、電子部品Ｐ２に対する試験ｔ１、電子部品Ｐ４に対する試験ｔ１、電子部品Ｐ５に対する試験ｔ１を開始する割り付けを行う。この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ４→ステップＳ６の演算処理をして決定したものである。
これら電子部品Ｐ１，Ｐ２，Ｐ４，Ｐ５に対する試験ｔ１は、０時１２分の時刻に終了する。終了時刻は、試験開始時刻に、試験する電子部品の数に1個当たりの試験時間をかけた時間を加えることによって決定することができる。
【００４０】
時刻が０時１２分においては、電子部品Ｐ１に対する試験ｔ２、電子部品Ｐ２に対する試験ｔ２を開始する割り付けを行う。この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ４→ステップＳ６の演算処理をして決定したものである。
これら電子部品Ｐ１，Ｐ２に対する試験ｔ２は、０時１８分の時刻に終了する。終了時刻は、試験開始時刻に、試験する電子部品の数に1個当たりの試験時間をかけた時間を加えることによって決定することができる。
【００４１】
時刻が０時１２分においては、電子部品Ｐ３に対する試験ｔ１、電子部品Ｐ６に対する試験ｔ１を開始する割り付けを行う。この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ４→ステップＳ６の演算処理をして決定したものである。
これら電子部品Ｐ３，Ｐ６に対する試験ｔ１は、０時２４分の時刻に終了する。終了時刻は、試験開始時刻に、試験する電子部品の数に1個当たりの試験時間をかけた時間を加えることによって決定することができる。
【００４２】
時刻が０時１８分においては、電子部品Ｐ４に対する試験ｔ２、電子部品Ｐ５に対する試験ｔ２を開始する割り付けを行う。この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ４→ステップＳ６の演算処理をして決定したものである。
これら電子部品Ｐ４，Ｐ５に対する試験ｔ２は、０時２４分の時刻に終了する。終了時刻は、試験開始時刻に、試験する電子部品の数に1個当たりの試験時間をかけた時間を加えることによって決定することができる。
【００４３】
時刻が０時２４分においては、電子部品Ｐ１，Ｐ２に対する試験ｔ３（試験条件ｃ３−１、試験時間２１分）のグループと、電子部品Ｐ４，Ｐ５に対する試験ｔ３（試験条件ｃ３−２、試験時間３６分）のグループとが、バッチ処理ができるグループとして割り付けができる可能性がある。
両グループの電子部品の納期を比べると、電子部品Ｐ１，Ｐ２の納期（2011年4月30日）が、電子部品Ｐ４，Ｐ５の納期（2011年５月31日）よりも厳しいので、電子部品Ｐ１，Ｐ２のグループを選択し、電子部品Ｐ１，Ｐ２に対する試験ｔ３（試験装置Ｔ３によりバッチ処理で行う試験ｔ３）を開始する割り付けを行う。
この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ７→ステップＳ９→ステップＳ１１→ステップＳ１２の演算処理をして決定したものである。
これら電子部品Ｐ１，Ｐ２に対する試験ｔ３は、０時４５分の時刻に終了する。終了時刻は、試験開始時刻に、試験条件ｃ３−１における試験時間２１分を加えることによって決定することができる。
【００４４】
時刻が０時２４分においては、電子部品Ｐ３に対する試験ｔ５（試験装置Ｔ５によりバッチ処理でなく行う試験ｔ５）を開始する割り付けを行う。
この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ７→ステップＳ９→ステップＳ１０の演算処理をして決定したものである。
電子部品Ｐ３に対する試験ｔ５は、０時３０分の時刻に終了する。終了時刻は、試験開始時刻に、試験条件ｃ５における試験時間６分を加えることによって決定することができる。
【００４５】
時刻が０時３０分においては、電子部品Ｐ６に対する試験ｔ５（試験装置Ｔ５によりバッチ処理でなく行う試験ｔ５）を開始する割り付けを行う。
この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ７→ステップＳ９→ステップＳ１０の演算処理をして決定したものである。
電子部品Ｐ６に対する試験ｔ５は、０時３６分の時刻に終了する。終了時刻は、試験開始時刻に、試験条件ｃ５における試験時間６分を加えることによって決定することができる。
【００４６】
時刻が０時４５分においては、電子部品Ｐ１に対する試験ｔ４、電子部品Ｐ２に対する試験ｔ４を開始する割り付けを行う。この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ４→ステップＳ６の演算処理をして決定したものである。
これら電子部品Ｐ１，Ｐ２に対する試験ｔ４は、０時５１分の時刻に終了する。終了時刻は、試験開始時刻に、試験する電子部品の数に1個当たりの試験時間をかけた時間を加えることによって決定することができる。
【００４７】
時刻が０時４５分においては、電子部品Ｐ４，Ｐ５に対する試験ｔ３（試験条件ｃ３−２、試験時間３６分）のグループが、バッチ処理ができるグループとして割り付けができる。このため、電子部品Ｐ４，Ｐ５に対する試験ｔ３（試験装置Ｔ３によりバッチ処理で行う試験ｔ３）を開始する割り付けを行う。
この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ７→ステップＳ９→ステップＳ１１→ステップＳ１２の演算処理をして決定したものである。
これら電子部品Ｐ４，Ｐ５に対する試験ｔ３は、１時２１分の時刻に終了する。終了時刻は、試験開始時刻に、試験条件ｃ３−２における試験時間３６分を加えることによって決定することができる。
【００４８】
時刻が０時５１分においては、電子部品Ｐ１に対する試験ｔ５（試験装置Ｔ５によりバッチ処理でなく行う試験ｔ５）を開始する割り付けを行う。
この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ７→ステップＳ９→ステップＳ１０の演算処理をして決定したものである。
電子部品Ｐ１に対する試験ｔ５は、０時５７分の時刻に終了する。終了時刻は、試験開始時刻に、試験条件ｃ５における試験時間６分を加えることによって決定することができる。
【００４９】
時刻が０時５７分においては、電子部品Ｐ２に対する試験ｔ５（試験装置Ｔ５によりバッチ処理でなく行う試験ｔ５）を開始する割り付けを行う。
この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ７→ステップＳ９→ステップＳ１０の演算処理をして決定したものである。
電子部品Ｐ２に対する試験ｔ５は、１時０３分の時刻に終了する。終了時刻は、試験開始時刻に、試験条件ｃ５における試験時間６分を加えることによって決定することができる。
【００５０】
時刻が１時２１分においては、電子部品Ｐ４に対する試験ｔ４、電子部品Ｐ５に対する試験ｔ４を開始する割り付けを行う。この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ４→ステップＳ６の演算処理をして決定したものである。
これら電子部品Ｐ４，Ｐ５に対する試験ｔ４は、１時２７分の時刻に終了する。終了時刻は、試験開始時刻に、試験する電子部品の数に1個当たりの試験時間をかけた時間を加えることによって決定することができる。
【００５１】
時刻が１時２７分においては、電子部品Ｐ４に対する試験ｔ５（試験装置Ｔ５によりバッチ処理でなく行う試験ｔ５）を開始する割り付けを行う。
この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ７→ステップＳ９→ステップＳ１０の演算処理をして決定したものである。
電子部品Ｐ４に対する試験ｔ５は、１時３３分の時刻に終了する。終了時刻は、試験開始時刻に、試験条件ｃ５における試験時間６分を加えることによって決定することができる。
【００５２】
時刻が１時３３分においては、電子部品Ｐ５に対する試験ｔ５（試験装置Ｔ５によりバッチ処理でなく行う試験ｔ５）を開始する割り付けを行う。
この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ７→ステップＳ９→ステップＳ１０の演算処理をして決定したものである。
電子部品Ｐ５に対する試験ｔ５は、１時３９分の時刻に終了する。終了時刻は、試験開始時刻に、試験条件ｃ５における試験時間６分を加えることによって決定することができる。
【００５３】
このようにして、図５に示すスケジュールが作成される。このスケジュールの総処理時間は、処理（試験）開始時刻から、最終ジョブ（電子部品Ｐ５の試験ｔ５）が終了する時刻までの時間である、１時間３９分である。
【実施例２】
【００５４】
上記の実施例１では、試験装置がバッチ処理可能であるときには、複数の「電子部品に対する試験」を、同一の試験装置で同一の試験条件となるものどうしでグループにし、納期が最も早い電子部品が含まれているグループの「電子部品に対する試験」の開始・終了時刻をスケジュールに割り付けている。
しかし、最も納期が厳しい電子部品を含むグループを選択するルール（グループ選択基準）が必ずしも最適とは限らない。
【００５５】
そこで、最も納期が厳しい電子部品を含むグループを選択するルール（グループ選択基準）に固定するだけではなく、グループ選択基準を最適化変数（値の例：最も納期が厳しい電子部品を選択、一度に処理できる量が最も多いものを選択など）と考え、下記の「局所探索法」に実装することにより、最適なグループ選択基準を求めることもできる。
【００５６】
例えば、スケジュール演算部２に、グループ選択基準として複数のグループ選択基準を備えておき、それぞれのグループ選択基準を用いて複数のスケジュールをそれぞれ作成し、作成した複数のスケジュールのうち、総処理時間が最も短いスケジュールを最終的なスケジュールとすることもできる。
【００５７】
また、各試験装置ごとに最大待ち時間を変数（値の例：待ちなし、３０分、１時間、４時間など）として設定し、当該試験装置が使用可能な状態になってから、本変数時間内に当該試験装置を使用する電子部品が到着すると予想される場合は、待ちを発生させ、現在試験可能な電子部品と合わせて試験を行うようなスケジュールを作成することもできる。
【００５８】
また、各電子部品のロットサイズについても、試験すべき部品数の分割手段を変数として考える（試験すべき部品数が５０個である部品に関する変数の値の例：１０個+４０個、２０個+３０個、５０個、１０個×５など）ことで、上記と同様に扱うことが可能である。
【００５９】
探索手法は「局所探索法」と呼ばれる手法である。これはあるスケジュールに対して、一部の変数の値を変えた場合（例えば、ある装置を使う際の待ち時間を変更する）について、スケジュールを作成しなおし、そのスケジュールの評価関数の値が、元のスケジュールの評価関数の値よりも小さいものであれば、そのスケジュールを元のスケジュールと置き換えるという操作を繰り返すものである。
このように、局所探索法を用いて、評価関数の値の最も小さいスケジュール、即ち、スケジュールの総処理時間が最も短いスケジュールを探し出して、最終的なスケジュールとして採用する。
【実施例３】
【００６０】
現実のスケジューリングにおいては、電子部品の数や種類は極めて多く、試験種類も極めて多い。
そこで、より精度のよいスケジュールを作成するためには、
（１）入力データとして、
・各電子部品の納期
・各試験工程において使用する試験装置、使用する治具、試験条件、作業時間
・作業者の人数
・試験装置の台数
・各試験装置、各作業員の稼働シフト
を入力し、
（２）スケジュール作成の制約条件として、
・試験装置の取り合い
・治具の取り合い
・試験条件
・納期
・試験装置の体積（部品の体積を考慮して、一度に処理できる個数を計算）
・各試験装置、各作業者の稼働シフト
・特定の工程に対して固定された日程
を考慮し、局所探索法を用いて、スケジュールの総処理時間が最も短いものを最終的なスケジュールとして採用することが望ましい。
【符号の説明】
【００６１】
１ 入力装置
２ スケジュール演算部
３ 出力装置
１０ スケジューリング装置
【技術分野】
【０００１】
本発明は、フローショップ型工程のスケジューリング装置に関し、バッチ処理が可能か否か等の設備能力を考慮することにより、総処理時間が短い最適なスケジュールを作成することができるように工夫したものである。
【背景技術】
【０００２】
ロケットや航空機などの製品には、多数・多種類の電子部品が組み込まれている。これら多数・多種類の電子部品は、製品に組み込む前に、環境ストレス試験が実施される。
環境ストレス試験を短時間で効率的に行うには、電子部品の試験順序を規定するスケジュールを最適に決める必要がある。
【０００３】
各電子部品は、作業者により又は試験装置により複数の試験を行う必要がある。いずれの電子部品も、試験は必ず決まった順番で行うが、電子部品によっては一部の試験を行わない（スキップする）ことが決まっている。
【０００４】
このように、全ての電子部品を、必ず決まった一定の順番で試験（ジョブ：処理）を行う（但し、一部の電子部品は所定のジョブをスキップすることも含む）工程のことを、フローショップ工程と呼んでいる。
【０００５】
例えば、
電子部品Ｐ１は、作業者による試験ｔ１，作業者による試験ｔ２，試験装置Ｔ３及び作業者による試験ｔ３，作業者による試験ｔ４，試験装置Ｔ５及び作業者による試験ｔ５を、この順番（ｔ１→ｔ２→ｔ３→ｔ４→ｔ５の順）に行い、
電子部品Ｐ２は、作業者による試験ｔ１，作業者による試験ｔ２，試験装置Ｔ３及び作業者による試験ｔ３，作業者による試験ｔ４，試験装置Ｔ５及び作業者による試験ｔ５を、この順番（ｔ１→ｔ２→ｔ３→ｔ４→ｔ５の順）に行い、
電子部品Ｐ３は、試験ｔ２，試験ｔ３，試験ｔ４は行わない（スキップする）が、作業者による試験ｔ１，試験装置Ｔ５及び作業者による試験ｔ５を、この順番（ｔ１→ｔ５の順）に行う。
このようなフローショップ型工程において、作業時間や納期遅れが最小になるように、各ジョブを各ショップでどのような順番で処理（試験）すべきかを決めることを、フローショップ型問題と呼んでいる。
【０００６】
各試験内容に応じて、使用する試験装置、治具、試験条件が決まっており、一部の試験装置については、同一の試験装置、同一の治具、同一の試験条件で、異なる種類の部品をセットにして一緒に試験を行うこと、即ち「バッチ処理」が可能である。
例えば、上記例では、試験装置Ｔ３はバッチ処理が可能であるが、試験装置Ｔ５はバッチ処理ができないようになっていることがある。
【０００７】
従来技術では、いわゆる一般的なフローショップ工程に対して、スケジューリングを行い、結果を表示する装置や方法が提案されてきた（例えば、特許文献１，２，３参照）。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開平１１−１８４９２３
【特許文献２】特開平０７−０７３２４４
【特許文献３】特開平０２−０４２５０３
【発明の概要】
【発明が解決しようとする課題】
【０００９】
「一部の試験装置については、同一の試験装置、同一の治具、同一の試験条件で、異なる種類の部品をセットにして一緒に試験を行うことが可能」といった「制約条件」を考慮してスケジュールを作成するには、従来では、上記の制約条件を人手で考慮し、試験スケジュールを作成していた。
このため、以下の問題が発生していた。
・設備能力を十分に活かした数量になっておらず、作業ロットが分かれる場合があり、効率が悪い。
・多くの情報を紙ベースで手作業により確認するため、手間がかかる。
・作業遅れが発生する。
・作業があふれる場合には、外注に流れてしまうことになり、追加費用が発生する。
【００１０】
また、特許文献１〜３に示す従来技術では、１つの装置（設備）に対し、１つの部品を扱う古典的なフローショップ問題を解くのに留まっており、本件で扱う問題のように、１つの装置（設備）に対して同時に複数種類の電子部品を扱えるケースには対応していない。
即ち、一般的なフローショップ工程に対するスケジューリングでは、１装置に対して１部品が原則であり、本件で扱うような、「一部の試験装置については、同一の試験装置、同一の治具、同一の試験条件で、異なる種類の部品をセットにして一緒に試験を行うことが可能」といった制約条件を考慮することができなかった。
【００１１】
本発明は、上記従来技術に鑑み、「一部の試験装置については、同一の試験装置、同一の治具、同一の試験条件で、異なる種類の部品をセットにして一緒に試験を行うことが可能」といった制約条件を考慮して、総処理時間の短い最適なスケジュールを作成することができる、スケジューリング装置を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記課題を解決する本発明の構成は、
複数の電子部品を、予め決めた試験順序にしたがって複数の試験をするフローショップ型工程のスケジュールを作成するスケジューリング装置であって、
各試験における「バッチ処理の可否」，「作業者の要否」，「試験装置の要否」に関する制約条件と、各電子部品の「個数」，「納期」に関する制約条件と、各電子部品について各試験を行うときの「試験条件及び試験時間」に関する制約条件と、作業者の人数と、各試験装置の台数を入力する入力部と、
前記入力部により入力された条件を基に、スケジュールを作成するスケジュール演算部とを有し、
前記スケジュール演算部は、
各電子部品に対する各試験のうち、開始・終了時刻の割り付けをしていないもので、開始・終了時刻の割り付けができる可能性がある「電子部品に対する試験」を選択し、
選択した「電子部品に対する試験」が、作業者のみが必要で且つ作業者が空いていると判定したときには、作業者のみが必要な「電子部品に対する試験」の開始・終了時刻をスケジュールに割り付け、
選択した「電子部品に対する試験」が、作業者及びバッチ処理ができない試験装置が必要で且つ作業者及びバッチ処理ができない試験装置が空いていると判定したときには、作業者及びバッチ処理ができない試験装置が必要な「電子部品に対する試験」の開始・終了時刻をスケジュールに割り付け、
選択した「電子部品に対する試験」が、作業者及びバッチ処理が可能な試験装置が必要で且つ作業者及びバッチ処理が可能な試験装置が空いていると判定したときには、複数の「電子部品に対する試験」を同一の試験装置で同一の試験条件となるものどうしでグループにし、予め決めたグループ選択基準に基づき選択した一つのグループの「電子部品に対する試験」の開始・終了時刻をスケジュールに割り付ける、という演算を次々と行うことによりスケジュールを作成する、ことを特徴とする。
【００１３】
また本発明の構成は、
前記スケジュール演算部は、
前記グループ選択基準として複数のグループ選択基準を有しており、
それぞれのグループ選択基準を用いて複数のスケジュールを作成し、
作成した複数のスケジュールのうち、総処理時間が最も短いスケジュールを最終的なスケジュールとすることを特徴とする。
【００１４】
また本発明の構成は、
前記グループ選択基準は、納期が最も早い電子部品が含まれているグループを選択する基準、または、一度に試験することができる量が最も多いグループを選択する基準、を含むことを特徴とする。
【発明の効果】
【００１５】
本発明によれば、「一部の試験装置については、同一の試験装置、同一の治具、同一の試験条件で、異なる種類の部品をセットにして一緒に試験を行うことが可能」といった制約条件を考慮することにより、総処理時間の短い最適なスケジュールを作成することができる。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施例に係るスケジューリング装置を示す構成図。
【図２】電子部品ごとの試験工程と試験条件に関する制約条件を示す表。
【図３】試験条件と試験時間に関する制約条件を示す表。
【図４】本発明の実施例の演算処理を示すフローチャート。
【図５】本発明の実施例で求めたスケジュールを示すガントチャート。
【図６】本発明の実施例の演算処理手順を示すタイムチャート。
【発明を実施するための形態】
【００１７】
以下、本発明の実施の形態について、実施例に基づき詳細に説明する。
【実施例１】
【００１８】
実施例１は、複数の電子部品を、予め決められた試験順序にしたがって、複数の試験をするフローショップ型工程のスケジュールを作成するスケジューリング装置１０である。
実施例１は、発明の理解を容易にするため、電子部品の種類を６種類（Ｐ１〜Ｐ６）、試験の数を５種類（ｔ１〜ｔ５）とした例である。
【００１９】
図１に示すように、スケジューリング装置１０は、入力装置１と、スケジュール演算部２と、出力装置３により構成されている。
スケジュール演算部２は、後述するスケジュール演算をするためのソフトウエア（プログラム）とハードウエア資源（コンピュータ）とが協働した具体的手段であり、フローショップ型工程のスケジュールを作成する特有の情報処理装置を構築している。
【００２０】
入力装置１は、例えば、図２に示す「電子部品ごとの試験（ジョブ：処理）工程と試験条件」に関する制約条件と、図３に示す「試験条件と試験時間」に関する制約条件と、作業者人数（本例では４人）に関する制約条件を、スケジュール演算部２に入力する。
【００２１】
図２に示す「電子部品ごとの試験工程と試験条件」に関する制約条件と、図３に示す「試験条件と試験時間」に関する制約条件について、更に説明すると、次の通りである。
【００２２】
各試験ｔ１〜ｔ５における、「バッチ処理の可否」、「作業者の要否」、「試験装置の要否」に関する制約条件がある。
具体的には、図２に示すように、
・試験ｔ１では、バッチ処理は不可（×）、作業者は必要（○）、試験装置は不要（×）であり、
・試験ｔ２では、バッチ処理は不可（×）、作業者は必要（○）、試験装置は不要（×）であり、
・試験ｔ３では、バッチ処理は可能（○）、作業者は必要（○）、試験装置（試験装置Ｔ３）は必要（○）であり、
・試験ｔ４では、バッチ処理は不可（×）、作業者は必要（○）、試験装置は不要（×）であり、
・試験ｔ５では、バッチ処理は不可（×）、作業者は必要（○）、試験装置（試験装置Ｔ５）は必要（○）である。
この例においては、試験ｔ５で用いる試験装置Ｔ５ではバッチ処理は不可（×）であるのに対して、試験ｔ３で用いる試験装置Ｔ３ではバッチ処理は可能（○）であることに着目して、後述するスケジュール演算をしていることが、特徴の一つである。
なお、本例では、試験装置Ｔ３は１台であり、試験装置Ｔ５も１台である。このような各試験装置の台数も、入力装置１によりスケジュール演算部２に入力される。
【００２３】
各電子部品Ｐ１〜Ｐ６の「個数」、「納期」に関する制約条件がある。
具体的には、図２に示すように、
・電子部品Ｐ１では、「個数」は１０個、「納期」は2011年4月30日であり、
・電子部品Ｐ２では、「個数」は１０個、「納期」は2011年4月30日であり、
・電子部品Ｐ３では、「個数」は１０個、「納期」は2011年7月31日であり、
・電子部品Ｐ４では、「個数」は１０個、「納期」は2011年5月31日であり、
・電子部品Ｐ５では、「個数」は１０個、「納期」は2011年5月31日であり、
・電子部品Ｐ６では、「個数」は１０個、「納期」は2011年7月31日である。
【００２４】
各電子部品Ｐ１〜Ｐ６について各試験ｔ１〜ｔ５を行うときの「試験条件及び試験時間」に関する制約条件がある。
具体的には、図２、図３に示すように、
・電子部品Ｐ１に関しては、試験ｔ１では試験条件ｃ１で１個当たりの試験時間は0.02時間、試験ｔ２では試験条件ｃ２で１個当たりの試験時間は0.01時間、試験ｔ３では試験条件ｃ３−１で試験時間は２１分、試験ｔ４では試験条件ｃ４で１個当たりの試験時間は0.01時間、試験ｔ５では試験条件ｃ５で試験時間は６分であり、
・電子部品Ｐ２に関しては、試験ｔ１では試験条件ｃ１で１個当たりの試験時間は0.02時間、試験ｔ２では試験条件ｃ２で１個当たりの試験時間は0.01時間、試験ｔ３では試験条件ｃ３−１で試験時間は２１分、試験ｔ４では試験条件ｃ４で１個当たりの試験時間は0.01時間、試験ｔ５では試験条件ｃ５で試験時間は６分であり、
・電子部品Ｐ３に関しては、試験ｔ１では試験条件ｃ１で１個当たりの試験時間は0.02時間、試験ｔ５では試験条件ｃ５で試験時間は6分であり、試験ｔ２，ｔ３，ｔ４はスキップし、
・電子部品Ｐ４に関しては、試験ｔ１では試験条件ｃ１で１個当たりの試験時間は0.02時間、試験ｔ２では試験条件ｃ２で１個当たりの試験時間は0.01時間、試験ｔ３では試験条件ｃ３−２で試験時間は３６分、試験ｔ４では試験条件ｃ４で１個当たりの試験時間は0.01時間、試験ｔ５では試験条件ｃ５で試験時間は６分であり、
・電子部品Ｐ５に関しては、試験ｔ１では試験条件ｃ１で１個当たりの試験時間は0.02時間、試験ｔ２では試験条件ｃ２で１個当たりの試験時間は0.01時間、試験ｔ３では試験条件ｃ３−２で試験時間は３６分、試験ｔ４では試験条件ｃ４で１個当たりの試験時間は0.01時間、試験ｔ５では試験条件ｃ５で試験時間は６分であり、
・電子部品Ｐ６に関しては、試験ｔ１では試験条件ｃ１で１個当たりの試験時間は0.02時間、試験ｔ５では試験条件ｃ５で試験時間は６分であり、試験ｔ２，ｔ３，ｔ４はスキップしている。
この例においては、バッチ処理が可能な試験ｔ３において、電子部品Ｐ１，Ｐ２に関しては試験条件ｃ３−１で試験時間は２１分であるのに対して、電子部品Ｐ４，Ｐ５に関しては試験条件ｃ３−２で試験時間は３６分であることに着目して、後述するスケジュール演算をしていることが、特徴の一つである。
【００２５】
スケジュール演算部２は、入力装置１から上記の各制約条件（図２、図３参照）が入力されると、図４のフローチャートに示すスケジュール演算（詳細は後述する）をして、図５のガントチャートに示すスケジュールを作成する。
作成されたスケジュール（図５参照）は、出力装置３から出力されて、画面表示されたりプリントアウトされたりする。
【００２６】
ここでスケジュール演算部２によるスケジュール演算手法を、図４のフローチャートに基づき説明する。
【００２７】
まず、各電子部品に対する各試験の開始・終了時刻のスケジュールへの割り付けが全て終了したか否かを判定する（ステップＳ１）。
【００２８】
各電子部品に対する各試験の開始・終了時刻のスケジュールへの割り付けが全て終了していないと判定したときには、各電子部品に対する各試験のうち、開始・終了時刻の割り付けをしていないもので、開始・終了時刻の割り付けができる可能性がある「電子部品に対する試験」を選択する（ステップＳ２）。
ステップ２でいう、『開始・終了時刻の割り付けができる可能性がある「電子部品に対する試験」』とは、各電子部品に対して順番に行う試験のうち、まだ試験が行われていない最も順番の早い試験のことを意味している。
【００２９】
選択した「電子部品に対する試験」が、作業者のみが必要か、または、作業者と試験装置が必要かを判定する（ステップ３）。
【００３０】
選択した「電子部品に対する試験」が、作業者のみが必要と判定したときには、作業者が空いているか否かを判定する（ステップ４）。
【００３１】
作業者が空いていないと判定したときには、作業者が空く時間まで待ち（ステップ５）、ステップＳ２に戻る。
作業者が空いていると判定したときには、作業者のみが必要な「電子部品に対する試験」の開始・終了時刻をスケジュールに割り付ける（ステップＳ６）。その後、ステップＳ１に戻る。
【００３２】
ステップＳ３において、選択した「電子部品に対する試験」が、作業者と試験装置が必要と判定したときには、作業者と試験装置が空いているか否かを判定する（ステップＳ７）。
【００３３】
作業者と試験装置が空いていないと判定したときには、作業者と試験装置が空く時間まで待ち（ステップＳ８）、ステップＳ２に戻る。
作業者と試験装置が空いていると判定したときには、空いている試験装置はバッチ処理が可能か否かを判定する（ステップＳ９）。
【００３４】
空いている試験装置はバッチ処理が可能でないと判定したときには、作業者と試験装置が必要な「電子部品に対する試験」の開始・終了時刻をスケジュールに割り付ける（ステップＳ１０）。
【００３５】
空いている試験装置はバッチ処理が可能であると判定したときには、複数の「電子部品に対する試験」を、同一の試験装置で同一の試験条件となるものどうしでグループにする（ステップＳ１１）。
【００３６】
ステップＳ１１でグループ化した後、納期が最も早い電子部品が含まれているグループの「電子部品に対する試験」の開始・終了時刻をスケジュールに割り付ける（ステップＳ１２）。その後、ステップＳ１に戻る。
【００３７】
ステップＳ１で、各電子部品に対する各試験の開始・終了時刻のスケジュールへの割り付けが全て終了したと判定したら、スケジュール作成を完了する（ステップＳ１３）。
【００３８】
次に、図５に示すガントチャート及び図６に示すタイムチャートに基づき、スケジュール演算部２によるスケジュール演算の具体例を説明する。
【００３９】
時刻が０時００分においては、電子部品Ｐ１に対する試験ｔ１、電子部品Ｐ２に対する試験ｔ１、電子部品Ｐ４に対する試験ｔ１、電子部品Ｐ５に対する試験ｔ１を開始する割り付けを行う。この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ４→ステップＳ６の演算処理をして決定したものである。
これら電子部品Ｐ１，Ｐ２，Ｐ４，Ｐ５に対する試験ｔ１は、０時１２分の時刻に終了する。終了時刻は、試験開始時刻に、試験する電子部品の数に1個当たりの試験時間をかけた時間を加えることによって決定することができる。
【００４０】
時刻が０時１２分においては、電子部品Ｐ１に対する試験ｔ２、電子部品Ｐ２に対する試験ｔ２を開始する割り付けを行う。この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ４→ステップＳ６の演算処理をして決定したものである。
これら電子部品Ｐ１，Ｐ２に対する試験ｔ２は、０時１８分の時刻に終了する。終了時刻は、試験開始時刻に、試験する電子部品の数に1個当たりの試験時間をかけた時間を加えることによって決定することができる。
【００４１】
時刻が０時１２分においては、電子部品Ｐ３に対する試験ｔ１、電子部品Ｐ６に対する試験ｔ１を開始する割り付けを行う。この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ４→ステップＳ６の演算処理をして決定したものである。
これら電子部品Ｐ３，Ｐ６に対する試験ｔ１は、０時２４分の時刻に終了する。終了時刻は、試験開始時刻に、試験する電子部品の数に1個当たりの試験時間をかけた時間を加えることによって決定することができる。
【００４２】
時刻が０時１８分においては、電子部品Ｐ４に対する試験ｔ２、電子部品Ｐ５に対する試験ｔ２を開始する割り付けを行う。この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ４→ステップＳ６の演算処理をして決定したものである。
これら電子部品Ｐ４，Ｐ５に対する試験ｔ２は、０時２４分の時刻に終了する。終了時刻は、試験開始時刻に、試験する電子部品の数に1個当たりの試験時間をかけた時間を加えることによって決定することができる。
【００４３】
時刻が０時２４分においては、電子部品Ｐ１，Ｐ２に対する試験ｔ３（試験条件ｃ３−１、試験時間２１分）のグループと、電子部品Ｐ４，Ｐ５に対する試験ｔ３（試験条件ｃ３−２、試験時間３６分）のグループとが、バッチ処理ができるグループとして割り付けができる可能性がある。
両グループの電子部品の納期を比べると、電子部品Ｐ１，Ｐ２の納期（2011年4月30日）が、電子部品Ｐ４，Ｐ５の納期（2011年５月31日）よりも厳しいので、電子部品Ｐ１，Ｐ２のグループを選択し、電子部品Ｐ１，Ｐ２に対する試験ｔ３（試験装置Ｔ３によりバッチ処理で行う試験ｔ３）を開始する割り付けを行う。
この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ７→ステップＳ９→ステップＳ１１→ステップＳ１２の演算処理をして決定したものである。
これら電子部品Ｐ１，Ｐ２に対する試験ｔ３は、０時４５分の時刻に終了する。終了時刻は、試験開始時刻に、試験条件ｃ３−１における試験時間２１分を加えることによって決定することができる。
【００４４】
時刻が０時２４分においては、電子部品Ｐ３に対する試験ｔ５（試験装置Ｔ５によりバッチ処理でなく行う試験ｔ５）を開始する割り付けを行う。
この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ７→ステップＳ９→ステップＳ１０の演算処理をして決定したものである。
電子部品Ｐ３に対する試験ｔ５は、０時３０分の時刻に終了する。終了時刻は、試験開始時刻に、試験条件ｃ５における試験時間６分を加えることによって決定することができる。
【００４５】
時刻が０時３０分においては、電子部品Ｐ６に対する試験ｔ５（試験装置Ｔ５によりバッチ処理でなく行う試験ｔ５）を開始する割り付けを行う。
この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ７→ステップＳ９→ステップＳ１０の演算処理をして決定したものである。
電子部品Ｐ６に対する試験ｔ５は、０時３６分の時刻に終了する。終了時刻は、試験開始時刻に、試験条件ｃ５における試験時間６分を加えることによって決定することができる。
【００４６】
時刻が０時４５分においては、電子部品Ｐ１に対する試験ｔ４、電子部品Ｐ２に対する試験ｔ４を開始する割り付けを行う。この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ４→ステップＳ６の演算処理をして決定したものである。
これら電子部品Ｐ１，Ｐ２に対する試験ｔ４は、０時５１分の時刻に終了する。終了時刻は、試験開始時刻に、試験する電子部品の数に1個当たりの試験時間をかけた時間を加えることによって決定することができる。
【００４７】
時刻が０時４５分においては、電子部品Ｐ４，Ｐ５に対する試験ｔ３（試験条件ｃ３−２、試験時間３６分）のグループが、バッチ処理ができるグループとして割り付けができる。このため、電子部品Ｐ４，Ｐ５に対する試験ｔ３（試験装置Ｔ３によりバッチ処理で行う試験ｔ３）を開始する割り付けを行う。
この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ７→ステップＳ９→ステップＳ１１→ステップＳ１２の演算処理をして決定したものである。
これら電子部品Ｐ４，Ｐ５に対する試験ｔ３は、１時２１分の時刻に終了する。終了時刻は、試験開始時刻に、試験条件ｃ３−２における試験時間３６分を加えることによって決定することができる。
【００４８】
時刻が０時５１分においては、電子部品Ｐ１に対する試験ｔ５（試験装置Ｔ５によりバッチ処理でなく行う試験ｔ５）を開始する割り付けを行う。
この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ７→ステップＳ９→ステップＳ１０の演算処理をして決定したものである。
電子部品Ｐ１に対する試験ｔ５は、０時５７分の時刻に終了する。終了時刻は、試験開始時刻に、試験条件ｃ５における試験時間６分を加えることによって決定することができる。
【００４９】
時刻が０時５７分においては、電子部品Ｐ２に対する試験ｔ５（試験装置Ｔ５によりバッチ処理でなく行う試験ｔ５）を開始する割り付けを行う。
この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ７→ステップＳ９→ステップＳ１０の演算処理をして決定したものである。
電子部品Ｐ２に対する試験ｔ５は、１時０３分の時刻に終了する。終了時刻は、試験開始時刻に、試験条件ｃ５における試験時間６分を加えることによって決定することができる。
【００５０】
時刻が１時２１分においては、電子部品Ｐ４に対する試験ｔ４、電子部品Ｐ５に対する試験ｔ４を開始する割り付けを行う。この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ４→ステップＳ６の演算処理をして決定したものである。
これら電子部品Ｐ４，Ｐ５に対する試験ｔ４は、１時２７分の時刻に終了する。終了時刻は、試験開始時刻に、試験する電子部品の数に1個当たりの試験時間をかけた時間を加えることによって決定することができる。
【００５１】
時刻が１時２７分においては、電子部品Ｐ４に対する試験ｔ５（試験装置Ｔ５によりバッチ処理でなく行う試験ｔ５）を開始する割り付けを行う。
この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ７→ステップＳ９→ステップＳ１０の演算処理をして決定したものである。
電子部品Ｐ４に対する試験ｔ５は、１時３３分の時刻に終了する。終了時刻は、試験開始時刻に、試験条件ｃ５における試験時間６分を加えることによって決定することができる。
【００５２】
時刻が１時３３分においては、電子部品Ｐ５に対する試験ｔ５（試験装置Ｔ５によりバッチ処理でなく行う試験ｔ５）を開始する割り付けを行う。
この割り付けは、図４のステップＳ１→ステップＳ２→ステップＳ３→ステップＳ７→ステップＳ９→ステップＳ１０の演算処理をして決定したものである。
電子部品Ｐ５に対する試験ｔ５は、１時３９分の時刻に終了する。終了時刻は、試験開始時刻に、試験条件ｃ５における試験時間６分を加えることによって決定することができる。
【００５３】
このようにして、図５に示すスケジュールが作成される。このスケジュールの総処理時間は、処理（試験）開始時刻から、最終ジョブ（電子部品Ｐ５の試験ｔ５）が終了する時刻までの時間である、１時間３９分である。
【実施例２】
【００５４】
上記の実施例１では、試験装置がバッチ処理可能であるときには、複数の「電子部品に対する試験」を、同一の試験装置で同一の試験条件となるものどうしでグループにし、納期が最も早い電子部品が含まれているグループの「電子部品に対する試験」の開始・終了時刻をスケジュールに割り付けている。
しかし、最も納期が厳しい電子部品を含むグループを選択するルール（グループ選択基準）が必ずしも最適とは限らない。
【００５５】
そこで、最も納期が厳しい電子部品を含むグループを選択するルール（グループ選択基準）に固定するだけではなく、グループ選択基準を最適化変数（値の例：最も納期が厳しい電子部品を選択、一度に処理できる量が最も多いものを選択など）と考え、下記の「局所探索法」に実装することにより、最適なグループ選択基準を求めることもできる。
【００５６】
例えば、スケジュール演算部２に、グループ選択基準として複数のグループ選択基準を備えておき、それぞれのグループ選択基準を用いて複数のスケジュールをそれぞれ作成し、作成した複数のスケジュールのうち、総処理時間が最も短いスケジュールを最終的なスケジュールとすることもできる。
【００５７】
また、各試験装置ごとに最大待ち時間を変数（値の例：待ちなし、３０分、１時間、４時間など）として設定し、当該試験装置が使用可能な状態になってから、本変数時間内に当該試験装置を使用する電子部品が到着すると予想される場合は、待ちを発生させ、現在試験可能な電子部品と合わせて試験を行うようなスケジュールを作成することもできる。
【００５８】
また、各電子部品のロットサイズについても、試験すべき部品数の分割手段を変数として考える（試験すべき部品数が５０個である部品に関する変数の値の例：１０個+４０個、２０個+３０個、５０個、１０個×５など）ことで、上記と同様に扱うことが可能である。
【００５９】
探索手法は「局所探索法」と呼ばれる手法である。これはあるスケジュールに対して、一部の変数の値を変えた場合（例えば、ある装置を使う際の待ち時間を変更する）について、スケジュールを作成しなおし、そのスケジュールの評価関数の値が、元のスケジュールの評価関数の値よりも小さいものであれば、そのスケジュールを元のスケジュールと置き換えるという操作を繰り返すものである。
このように、局所探索法を用いて、評価関数の値の最も小さいスケジュール、即ち、スケジュールの総処理時間が最も短いスケジュールを探し出して、最終的なスケジュールとして採用する。
【実施例３】
【００６０】
現実のスケジューリングにおいては、電子部品の数や種類は極めて多く、試験種類も極めて多い。
そこで、より精度のよいスケジュールを作成するためには、
（１）入力データとして、
・各電子部品の納期
・各試験工程において使用する試験装置、使用する治具、試験条件、作業時間
・作業者の人数
・試験装置の台数
・各試験装置、各作業員の稼働シフト
を入力し、
（２）スケジュール作成の制約条件として、
・試験装置の取り合い
・治具の取り合い
・試験条件
・納期
・試験装置の体積（部品の体積を考慮して、一度に処理できる個数を計算）
・各試験装置、各作業者の稼働シフト
・特定の工程に対して固定された日程
を考慮し、局所探索法を用いて、スケジュールの総処理時間が最も短いものを最終的なスケジュールとして採用することが望ましい。
【符号の説明】
【００６１】
１ 入力装置
２ スケジュール演算部
３ 出力装置
１０ スケジューリング装置
【特許請求の範囲】
【請求項１】
複数の電子部品を、予め決めた試験順序にしたがって複数の試験をするフローショップ型工程のスケジュールを作成するスケジューリング装置であって、
各試験における「バッチ処理の可否」，「作業者の要否」，「試験装置の要否」に関する制約条件と、各電子部品の「個数」，「納期」に関する制約条件と、各電子部品について各試験を行うときの「試験条件及び試験時間」に関する制約条件と、作業者の人数と、各試験装置の台数を入力する入力部と、
前記入力部により入力された条件を基に、スケジュールを作成するスケジュール演算部とを有し、
前記スケジュール演算部は、
各電子部品に対する各試験のうち、開始・終了時刻の割り付けをしていないもので、開始・終了時刻の割り付けができる可能性がある「電子部品に対する試験」を選択し、
選択した「電子部品に対する試験」が、作業者のみが必要で且つ作業者が空いていると判定したときには、作業者のみが必要な「電子部品に対する試験」の開始・終了時刻をスケジュールに割り付け、
選択した「電子部品に対する試験」が、作業者及びバッチ処理ができない試験装置が必要で且つ作業者及びバッチ処理ができない試験装置が空いていると判定したときには、作業者及びバッチ処理ができない試験装置が必要な「電子部品に対する試験」の開始・終了時刻をスケジュールに割り付け、
選択した「電子部品に対する試験」が、作業者及びバッチ処理が可能な試験装置が必要で且つ作業者及びバッチ処理が可能な試験装置が空いていると判定したときには、複数の「電子部品に対する試験」を同一の試験装置で同一の試験条件となるものどうしでグループにし、予め決めたグループ選択基準に基づき選択した一つのグループの「電子部品に対する試験」の開始・終了時刻をスケジュールに割り付ける、という演算を次々と行うことによりスケジュールを作成する、
ことを特徴とするスケジューリング装置。
【請求項２】
請求項１において、
前記スケジュール演算部は、
前記グループ選択基準として複数のグループ選択基準を有しており、
それぞれのグループ選択基準を用いて複数のスケジュールをそれぞれ作成し、
作成した複数のスケジュールのうち、総処理時間が最も短いスケジュールを最終的なスケジュールとすることを特徴とするスケジューリング装置。
【請求項３】
請求項１または請求項２において、
前記グループ選択基準は、納期が最も早い電子部品が含まれているグループを選択する基準、または、一度に試験することができる量が最も多いグループを選択する基準、を含むことを特徴とするスケジューリング装置。
【請求項１】
複数の電子部品を、予め決めた試験順序にしたがって複数の試験をするフローショップ型工程のスケジュールを作成するスケジューリング装置であって、
各試験における「バッチ処理の可否」，「作業者の要否」，「試験装置の要否」に関する制約条件と、各電子部品の「個数」，「納期」に関する制約条件と、各電子部品について各試験を行うときの「試験条件及び試験時間」に関する制約条件と、作業者の人数と、各試験装置の台数を入力する入力部と、
前記入力部により入力された条件を基に、スケジュールを作成するスケジュール演算部とを有し、
前記スケジュール演算部は、
各電子部品に対する各試験のうち、開始・終了時刻の割り付けをしていないもので、開始・終了時刻の割り付けができる可能性がある「電子部品に対する試験」を選択し、
選択した「電子部品に対する試験」が、作業者のみが必要で且つ作業者が空いていると判定したときには、作業者のみが必要な「電子部品に対する試験」の開始・終了時刻をスケジュールに割り付け、
選択した「電子部品に対する試験」が、作業者及びバッチ処理ができない試験装置が必要で且つ作業者及びバッチ処理ができない試験装置が空いていると判定したときには、作業者及びバッチ処理ができない試験装置が必要な「電子部品に対する試験」の開始・終了時刻をスケジュールに割り付け、
選択した「電子部品に対する試験」が、作業者及びバッチ処理が可能な試験装置が必要で且つ作業者及びバッチ処理が可能な試験装置が空いていると判定したときには、複数の「電子部品に対する試験」を同一の試験装置で同一の試験条件となるものどうしでグループにし、予め決めたグループ選択基準に基づき選択した一つのグループの「電子部品に対する試験」の開始・終了時刻をスケジュールに割り付ける、という演算を次々と行うことによりスケジュールを作成する、
ことを特徴とするスケジューリング装置。
【請求項２】
請求項１において、
前記スケジュール演算部は、
前記グループ選択基準として複数のグループ選択基準を有しており、
それぞれのグループ選択基準を用いて複数のスケジュールをそれぞれ作成し、
作成した複数のスケジュールのうち、総処理時間が最も短いスケジュールを最終的なスケジュールとすることを特徴とするスケジューリング装置。
【請求項３】
請求項１または請求項２において、
前記グループ選択基準は、納期が最も早い電子部品が含まれているグループを選択する基準、または、一度に試験することができる量が最も多いグループを選択する基準、を含むことを特徴とするスケジューリング装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１２−１１８８４３（Ｐ２０１２−１１８８４３Ａ）
【公開日】平成２４年６月２１日（２０１２．６．２１）
【国際特許分類】
【出願番号】特願２０１０−２６９１１６（Ｐ２０１０−２６９１１６）
【出願日】平成２２年１２月２日（２０１０．１２．２）
【出願人】（０００００６２０８）三菱重工業株式会社 (10,378)
【Ｆターム（参考）】
【公開日】平成２４年６月２１日（２０１２．６．２１）
【国際特許分類】
【出願日】平成２２年１２月２日（２０１０．１２．２）
【出願人】（０００００６２０８）三菱重工業株式会社 (10,378)
【Ｆターム（参考）】
[ Back to top ]