WO2002091093A1

WO2002091093A1 - Multi-item multi-process lot size scheduling method

Info

Publication number: WO2002091093A1
Application number: PCT/JP2002/004352
Authority: WO
Inventors: Kenji Muramatsu; Aditya Warman; Minoru Kobayashi; Takuya Yamaguchi
Original assignee: INFORMATION AND MATHEMATICAL SCIENCE LABORATORY Inc; Tokai University Educational System
Current assignee: INFORMATION AND MATHEMATICAL SCIENCE LABORATORY Inc; Tokai University Educational System
Priority date: 2001-05-01
Filing date: 2002-05-01
Publication date: 2002-11-14
Anticipated expiration: 2003-11-01
Also published as: JP2002328977A; US20030105543A1; EP1403748B1; EP1403748A4; US7072732B2; DE60223143T2; EP1403748A1; JP4737735B2; DE60223143D1

Description

明細書

多品目多工程口ットサイズスケジユーリング方法

技術分野

本発明は、複数の機械により複数の工程で当該各工程に対応した品目をそれぞれ処理し、かつ少なくとも 1 つの機械または工程では段取を伴う品目の切り換えが可能な多品目多ェ程生産システムに適用される生産スケジュールを生成するのに好適な多品目多工程ロットサイズスケジユーリング方法に関する。

背景技術

一般に、多工程、多機械から構成される生産システムでは、多様な注文を複数の品目に分類して切り換え生産をするのが一般的である。この種の生産システム、つまり多品目多工程生産システムでは、どの工程及びどの機械設備においても、処理する品目が切り替わる度に段取が伴う。この段取には、段取時間（セットアップタイム）と段取り費がかかる。但し、段取時間が 0 の場合もあり得る。この段取時間と段取り費は、いずれも処理する品目に依存する。一方、品目の在庫には、期間に比例して保管費がかかる。保管費は、品目に依存する。そこで、品切れあるいは納期遅れを起こさないで、且つ計画対象期間に亙る総費用ができるだけ少なくて済む、多品目多工程生産システム全体の最適スケジュールを求めることが要求される。この多品目多工程生産システムにおけるスケジューリングを、多品目多工程ロットサイズスケジユーリングと呼ぶ。このスケジユーリングで扱うべき問題（スケジユーリング問題）は、時間最適化問題、換言するならば、最適制御過程の問題である。各品目は、生産すれば、その在庫が増え、使えば減る。したがって、どの品目についても、在庫の時間的推移を計画対象期間に亙って陽に追う必要がある。

また、多品目多工程ロットサイズスケジューリングでは、 1 つの問題の中に多様な異質の決定の局面が混在する。特に、離散的な決定の局面と連続的な決定の局面とが混在する。これらの異質な諸局面は互いに分かち難く結びついている。この点に、上記スケジューリング問題の解法上の難しさがある。この問題に含まれる決定の諸局面として、各品目のロットサィズ、ロットの順序、ロットの分割、差し立て、及び仕掛品在庫量の各々の決定がある。また、同一機械での繰り返し処理についての決定などもある。これらの決定の諸局面はすべて時間と共に変化する。

ところが従来技術では、上記諸局面のうち、例えば、ロットのサイズ決定は時間的に不変であるとの前提を置いて連続数学の範疇で扱われている。一方、ロットの順序決定は離散数学の範疇で扱われている。

多品目多工程ロットサイズスケジューリングの問題は、高次元の問題でもある。それは 1 つの品目が少なくとも 1 つの次元を構成するからである。したがって、スケジューリング問題は高次元の時間最適化問題となる。この場合、スケジュ一リング問題を分解して解かない限り、計算に必要な時間とメモリ容量とが爆発的に増加する。よって従来技術においては、スケジューリング問題の解を、合理的な時間とメモリ容量の範囲内で得ることは期待できない。これは、文献 1 「 Bellman, R. ： Adaptive し ontrol Processes: A Guided Tour, Princeton University Press 、丄 961 J に己載れているように、ベルマンの次元の呪いとして広く知られている。

そこで、スケジユーリング問題の中に含まれている多様な異質の決定の局面を分解することが考えられる。しかし、これら異質の決定の局面は互いに分かち難く結びいているため、分解することは容易でない。このため従来技術においては、異質な決定の局面を 1 つずつ順に取り上げて、その取り上げられた局面を他と切り離して処理する手法が適用されている。

しカゝしながら、着目する 1 つの局面を他と切り離すためには、つまり着目する 1 つの局面を陽に取り扱うためには、他の各局面に人為的制約を置く必要がある。例えばロットの順序を決定するためには、それぞれのロットのサイズを予め与えておく必要がある。このように、従来技術では、多様な異質な決定の諸局面を含む高次元の時間最適化問題を解くために、 1 つの局面を他と切り離す度に人為的制約を置くことを余儀なくされ、各局面を同時に最適化することを困難にしている。

発明の開示

本発明は上記事情を考慮してなされたものでその目的は、多品目多工程のスケジユーリングの問題に含まれる多様な決定の諸局面を一つ一つ列挙することも意識することもなく、また人為的な制約を必要とすることなく、当該諸局面を全体最適化の視点から解決して経済的かつ合理的な実行可能スケジュールを生成できるようにすることにある。

本発明の 1 つの観点によれば、多品目多工程生産システムに適用される生産スケジュールをコンピュータにより生成する多品目多工程ロットサイズスケジユーリング方法が提供される。上記システムにおける少なくとも 1 つの機械またはェ程では、段取を伴う品目の切り換えが可能である。上記方法は、解くステップと、調整ステップと、再実行させるステツプと、生成ステップとから構成される。上記解くステップは、多品目多工程のスケジユーリングの問題に対応し、上記各ェ程で処理される品目別にスケジュールを求めるための、品目間の機械干渉に関する第 1 の制約及び仕掛品在庫量を非負とする第 2 の制約の付いた品目別の 1 次元部分最適化問題を、他の品目とは独立に解く。上記調整ステップは、上記解くステツプで求められた品目別の解をもとに上記第 1 及び第 2 の制約を充足させるための調整を行う。上記再実行させるステップは、上記調整ステップの都度、上記解くステップを再実行させる。上記生成ステップは、上記第 1 及び第 2 の制約が充足した際に上記解くステップで求められている品目別の解に基づいて生産スケジュールを生成する。

図面の簡単な説明

図 1 は本発明の一実施形態に係る多品目多工程口ットサイズスケジユーリング装置の機能構成を示すプロック図。

図 2 は図 1 のスケジユーリング装置を実現する計算機の構成を示すブロック図。図 3 は図 1 のスケジユーリング装置の動作を説明するためのフローチヤ一ト。

図 4 は図 3 中のステップ 3 0 5 の詳細手順を説明するためのフローチヤ一ト。

図 5 は（ S _it一， s _it から（ δ _it ^k, s _itk)への状態推移の関係を説明するための図。

図 6 は（ δ _itk, s _itk)の状態推移図。

図 7 Aは通常の在庫保管費を説明するための図。

図 7 B はェシエロン在庫保管費を説明するための図。

図 8 は図 1 のスケジユーリング装置で生成されるスケジュールが適用される多品目多工程の生産システムの概略構成を示す図。

発明を実施するための最良の形態

図 1 は本発明の一実施形態に係る多品目多工程口ットサイズスケジューリング装置の機能ブロック構成を示す。この図 1 のスケジユーリング装置は、多工程から構成される生産システムにおけるスケジユーリングの有する問題を解く機能を有する。この問題は、多様な注文を複数の品目に分類して切り換え生産をするためのスケジユーリング（多品目多工程口ットサイズスケジューリング）の有する高次元時間最適化問題である。図 1 のスケジューリング装置はまた、高次元時間最適化問題の解から上記生産システムで適用される最適スケジュール（最適生産スケジュール）を決定する機能をも有する。

図 1 のスケジユーリング装置は、例えば図 2 に示すブロック構成のパーソナルコンピュータ等の計算機によって実現される。図 2 の計算機は、 C P U 2 1 と、主メモリ 2 2 と、磁気ディスク装置（以下、 H D D と称する） 2 3 と、 C D — R O M装置 2 4 と、キーボード 2 5 と、ディスプレイ 2 6 とを備えている。これら、 C P U 2 1 、主メモリ 2 2 、 H D D 2 3 、 C D — R O M装置 2 4 、キーボード 2 5 及びディスプレィ 2 6 は、システムバス 2 7 により相互接続されている。

C P U 2 1 は、計算機の主制御装置である。主メモリ 2 2 は、 C P U 2 1 によって実行される各種プログラム、及びデ一タ等を格納する。 H D D 2 3 は上記計算機の外部記憶装置である。 C D— R O M装置 2 4 は、記録媒体としての例えば C D — R O M 2 4 2 に予め格納されている情報を計算機内に読み込む機能を有する。 C D — R O M 2 4 2 には、複数のェ程（多工程）、多機械（多設備）で複数の品目を生産する生産システムで適用される多品目多工程口ットサイズスケジューリングを行うための最適化スケジユーリングプログラム 2 4 1 が予め格納されてレヽる。このプログラム 2 4 1 は、 C D — R O M装置 2 4 により C D — R O M 2 4 2 から計算機内に読み込まれて、 H D D 2 3 に格納（インストール）されているものとする。なお、プログラム 2 4 1 を、図示せぬ通信回線を介して H D D 2 3 にダウンロードすることも可能である。キーボード 2 5 は最適スケジュールの生成に必要な生産データ等を入力するための入力装置であり、ディスプレイ 2 6 は表示用の出力装置である。本実施形態において、図 1 のスケジユーリング装置の機能構成は、 H D D 2 3 にインストールされた最適化スケジユーリングプログラム 2 4 1 を C P U 2 1 が主メモリ 2 2 上に読み込んで当該プログラム 2 4 1 を実行することにより実現される。

《最適化スケジユーリングの基本原理》

次に、本実施形態で適用される、各品目のロットサイズ、ロット順序、仕掛品在庫量等の決定の局面をすベて同時に最適化するための最適化スケジユーリングの基本原理について説明する。

〈時間最適化問題の高分解能モデルへの定式化〉

本実施形態では、スケジューリング問題、つまり高次元の時間最適化問題が、高い分解能のモデルに定式化される。そのため本実施形態では、計画対象期間がタイムスロットと呼ばれる細かな時間に刻まれる。さらに、時間最適化問題が、品目別に分解される。

タイムスロットは、問題を離散化して解くための最小時間単位である。タイムスロットの幅は、丸めの誤差、特に段取時間、あるいはタイムスロット当たりの処理量（生産量）における丸め誤差が許容できる範囲に納まるように決定される。例えば、計画対象期間を 1 0分単位に刻めば、段取時間の丸め誤差は 5 分であり、処理量の丸め誤差は 5 分間に処理できる量になる。これらの丸め誤差が許容できるならば、タイムスロット幅（刻み幅）は 1 0 分に定められる。

このように時間を細かく刻むことは、問題に含まれているすべての決定の局面を一つ一つ取り上げることを意識することもなく、問題に含まれるすべての決定の局面を一挙に解決するために必要不可欠である。次に、問題を品目別に取り扱う理由は、実際の処理あるいは注文が品目ベースで成されることによる。

ここで、モデルにおけるきめ細かさの概念を明らかにするために、上記「モデルの分解能」を次のように定義する。スケジユーリングあるいはビジネスのプロセスを数式モデルに定式化して扱うためには、初めに、時間軸と空間を規定する幾つかの軸とを設定することが必要である。ビジネスプロセスはこの座標空間上に展開される。そこで、これらの各軸を刻む最小の単位をすベて列挙して、これを「モデルの分解能」と呼ぶことにする。本実施形態におけるモデルの分解能は、タイムスロット、品目、機械設備である。したがって、得られるスケジュールの分解能も上記 3 点の何れが違っても識別できるものである。

〈問題の品目別への分解〉

多品目多工程口ットサイズスケジユーリングの高次元最適化問題では、分離可能性が成り立つ。また、この高次元最適化問題には、制約式が存在する。この点で、多品目多工程口ットサイズスケジューリング問題は、文献 2 「村松健児：

"拡張ラグランジュ分解調整法による同時最適スケジユーリング " ，オペレーションズ，リサーチ vol. 45, no. 6, pp.270-275. (2000)」に記載されている多品目単一機械ロットサイズスケジューリング問題と同様である。そこで本実施形態では、多品目多工程ロットサイズスケジューリング問題を品目別に分解する。この分解が可能であれば、対象とする生産システムの構造は特に多工程であるために極めて複雑であるにもかかわらず、問題の解法は次の解法と調整とに帰着する。即ち、問題の解法は、品目別の部分最適化問題の解法と部分問題間の相互関係制約を充足するための調整とに帰着する。

し力、しながら、このままでは多品目多工程ロットサイズスケジユーリングの部分最適化問題を他と独立に解くことができない。それは次の理由による。多工程のスケジューリング問題においては仕掛かり品目が関係する。実際の仕掛品については、処理が前工程において成されれば在庫が増え、後ェ程において成されれば在庫が減る。このため、 1 つの品目に 2 つの系列の処理が関係する。言い換えると、 1 つの系列の処理によって増減する品目が、処理の前後に少なくとも 2 つ存在する。したがって、一方の部分問題の最適化を図ると、他方の部分問題の最適化が崩れることになる。このように、 1 つの品目に 2 つの処理の系列が関係することが、後述するラグランジュ分解調整法における分解と調整にとつて最大の障害になる。

〈見かけの在庫〉

まず、上記した 1 つの品目に 2 つの処理の系列が関係することに起因する問題の所在を明確にするために、「処理の独立性」という概念を導入する。この「処理の独立性」を次のように定義する。即ち、スケジューリング問題を部分最適化問題に分解したとき、同一の処理あるいは処理の系列が複数の部分最適化問題に亙って現れないことを、「処理の独立性」と呼ぶ。

この処理の独立性を確保するためには、問題の本質を変えないで、 1 つの品目からいずれか一方の処理の系列を消去する必要がある。そのための手段が以下に定義する「見かけの在庫」という概念である。一般に仕掛品在庫とは、工程間に発生する実際の在庫である。したがって、仕掛品在庫は、初期在庫と累積生産量の和から、次工程への実際の累積出荷量あるいは累積処理量を引いたものと定義できる。ところが本実施形態では、ある品目について、次工程へ実際に渡される累積出荷量の代わりに、累積量を用いて上記仕掛品在庫に相当する量が計算される。この累積量は、後述する式（ 1 ) に示されるように、外（生産システム外）力、らの各タイムス口ットにおける出荷要求（外部需要）をその品目に展開することで算出される。この仕掛品在庫に相当する量は、実際の仕掛品在庫ではなく、架空の在庫あるいは見かけ上の在庫である。以後、これを「見かけの在庫」と呼ぶ。

このように、仕掛品在庫の代わりに見かけの在庫という概念を新たに導入することにより、 1 つの品目に 1 つの系列の処理を対応させることが可能になる。ところが、見かけの在庫に基づいて処理を計画した結果、実際の仕掛品在庫が品切れを起こす危険がある。そこで、この危険を回避する手段が必要となる。そのために本実施形態では、以下に定義する「処理の整合性」という概念を導入する。

仕掛品の実際の在庫は、仕掛品及びその仕掛品に後続する直結点の品目の処理によって増減する。処理の独立性のもとに、見かけの在庫に基づいてなされるこれらの処理が、実際の仕掛品在庫の品切れを起こさないという意味で、実行可能であるとき、「処理の整合性」が成立していると呼ぶことにする。このことは逆に、「処理の整合性」が成立している限りは処理の独立性が認められるが、「処理の整合性」が成立しなくなったなら処理の独立性が認められなくなるため、実際の仕掛品在庫が品切れとならないように（つまり充足するように）調整が必要となることを示す。なお、後続直結点の品目とは、ある品目 X を生産する直後の工程（後続直結点）で当該品目 X を組み込んで生産される品目 y のことである。この品目 y は、後述する図 8 の例における、品目 1 に対する品目 i 及び品目 i 一 1 などである。一方、品目 X は品目 y の直前の工程で生産される品目、つまり先行直結点の品目である。

〈処理の整合性を達成するために〉

本実施形態では、上記のように定義した処理の整合性を達成するために、実際の仕掛品在庫が品切れとならない条件、つまり実際の仕掛品在庫に対する非負条件を次のように相互関係制約に追加する。まず見かけの在庫を用いて、後述する式（ 7 ) に示されるように、実際の仕掛かり品在庫に対する量を定式化する。続いて、見かけの在庫により定式化された仕掛品在庫に対して、その非負条件を、後述する式（ 8 ) に示されるように、部分問題間の制約、即ち相互関係制約に追加して、これを陽に取り扱う。

〈エシロン在庫保管費〉ところが、実際の仕掛品在庫でなく見かけの在庫に注目して部分問題を解くことから、通常の在庫保管費を適用すると計算に矛盾が生じる。そこで在庫保管費についても見かけの在庫に合わせて把握をする必要が生じる。そのようにすることによって、実態を反映した在庫保管費の計算ができる。これには既に知られている方法が利用できる。それが「ェシェロン在庫保管費」という考え方である。

以下、ェシェロン在庫保管費について述べる。まず、どの品目に対しても、処理がなされて新たに価値が付加されたとき、新たに付加された部分の価値に対して在庫保管費を見積もることができる。ここで、処理により生まれた、品目の全体の価値に対して、在庫保管費を見積もるのではない点に注意されたい。さらにその価値は、品目がシステム内に存続する限り、その品目が別の品目に組み込まれた場合にも不変であると考えることができる。その場合には同様の考え方に基づいて、新たに生産される品目の価値のうち、新たに付加された価値に対してのみ在庫保管費を見積もることにする。このようにして定義される在庫保管費を「ェシェロン在庫保管費」と呼ぶ。

このェシェロン在庫保管費の詳細を、品目 1 と品目 2 と力 S 組み込まれた品目 3 を生産して、当該品目 3 を出荷した場合を例に、図 7 A及び B を参照して説明する。まず、品目 1 は時刻て 1 で、品目 2 は時刻 τ 2 で、それぞれ生産されたものとする。品目 3 は時刻て 3 で生産され、時刻 τ 4 で出荷されたものとする。また、品目 1 , 2 の価値に対して見積もられる在庫保管費が h 1 , h 2 であり、品目 3 の生産により新たに付加された価値に対して見積もられる在庫保管費が h 3 であるものとする。

この場合、一般には図 7 Aに示すように、品目 1 の在庫保管費 h 1 は時刻 τ 1〜 τ 3 の期間、品目 2 の在庫保管費 h 2 は時刻 τ 2〜て 3 の期間、それぞれ発生する。また、品目 3 の在庫保管費は、在庫保管費 h 3 に、品目 1 及び 2 の在庫保管費 h l， h 2 の和 h l+ h 2 をカ卩えたもの h l + h 2+ h 3 となる。この品目 3 の在庫保管費 h 1 + h 2 + h 3 は、時刻 τ 3〜 τ 4 の期間発生する。

これに対し、ェシェロン在庫保管費では、図 7 Β に示すように、品目 1 及び 2 が品目 3 に組み込まれた時刻 τ 3 以後も、その品目 1 及び 2 の在庫保管費 h i, h 2 は不変であるとして扱われる。品目 1 及び 2 の在庫保管費 h 1， h 2 は、品目 3 の出荷時刻 τ 4 まで継続する。また、品目 3 の在庫保管費は、新たに付加された価値に対して見積もられる h 3 のみとなり、時刻 τ 3〜て 4 の期間発生するものとして扱われる。これにより、在庫保管費を各品目 1 , 2 , 3 毎に独立して扱うことができ、在庫保管費を見かけの在庫に合わせることが可能となる。

〈ラグランジュ分解調整法の反復演算による解法〉

本実施形態では、すべての相互関係制約式をラグランジュ緩和してラグランジュ関数を導く処理が行われる。このラグランジュ関数は分解ができる。これにより、問題の最適化は、以下に述べる 2 つの処理を交互に反復することに帰着する。この 2 つの処理の一方は、所与のラグランジュ乗数値に対して各品目の部分最適化問題を他と独立に解くことである。この 2 つの処理の他方は、各制約条件に対応するラグランジュ乗数値を更新することである。部分問題の解法には動的計画法が用いられる。ここでは、制約式の极いは、部分問題の中で陽に取り扱うものと相互関係制約として扱うものとに別れる。

〈本実施形態で適用する解法の特徴〉

スケジューリングの問題を解くのに、当該問題を、上述のように高い分解能のモデルに定式化して、ラグランジュ分解調整法により解くことが考えられる。ここでは、例えば多品目単一機械ロットサイズスケジューリング問題であれば、ラグランジュ分解調整法を、各品目について他と独立に生産在庫問題を最適化するためと、機械干渉の生じているタイムスロットの使用料（即ちラグランジュ乗数の値）を調整して干渉を解消するためとに用いることが考えられる。

ところが本実施形態では、上記の品目（出荷の対象となる品目）の他に、工程間において発生する品目、即ち仕掛品を分解して取り扱わなくてはならない。したがって、品目間の分解のみならず工程間の分解を可能にする機構が必要になる。そのために本実施形態では、仕掛品在庫、特に仕掛品在庫に相当する見かけの在庫とェシエロン在庫保管費との概念を導入して処理の独立性を導いている。また本実施形態では、処理の整合性を保証するために、見かけの在庫を用いて実際の仕掛品在庫量を定式化して、その仕掛品在庫量の非負条件を相互関係制約に加えている。このように本実施形態では、見かけの在庫及びエシロン在庫保管費の概念の導入と、上記定式化とにより、多品目多工程の問題を品目別に分解する新規な方法を適用している。ここでは、機械干渉の生じているタイムスロットの他に、ラグランジュ乗数（即ち双対変数）を調整することによって全体最適化を図っている点に注目されたい。ラグランジュ乗数は、仕掛品在庫が充足していないタイムスロットの使用料（ペナルティコスト）に相当する。

《定式化》

次に、上記最適化スケジユーリングの基本原理における定式化の詳細について説明する。

〈前提条件〉

まず、本実施形態で取り上げる最適化スケジューリング問題の前提条件を明らかにしておく。

( 1 ) 対象あるいは適用分野

どの工程どの機械設備におけるどの品目もロットを構成して処理される。ロットのサイズは、この問題が解かれたときに決まる。注文が確定するまでは処理に着手できない品目、あるいは予め初期在庫を持つことが許される標準品のいずれであっても、最適化スケジユーリングの対象とすることができる。前者の場合には初期在庫はすべて 0 として扱われる。具体的には、プリント配線基板、半導体、キッチン家具、ォ一ディォ · ビジュアル機器（ A V機器）、光学器機などの生産工程の全体あるいは部分に、最適化スケジユーリングの適用の可能性が高い。図 8 は、図 1 のスケジユーリング装置で生成されるスケジユールに従って、多様な注文を複数の品目に分解して切り換え生産する、多品目多工程生産システムの構成例を示す。図 8 のシステムにおいて、例えば品目 p — 1 と品目 p とは、同一機械 4 において処理が繰り返される。本実施形態では、この機械 4 における品目 p — 1 と品目 p との関係のように、同 —機械設備において処理が操り返される状況を含むシステムに対して、そうでない場合と同様に、最適化スケジユーリングを適用することが可能である。このような例として、プリント基板の表面のプリント配線処理と当該プリント基板の裏面のプリント配線処理とを同一機械設備で行う場合が挙げられる。このとき、プリント基板自体は同一でありながら、表面のプリント配線処理が行われるプリント基板と裏面のプリント配線処理が行われるプリント基板とが区別される。つまり、表面のプリント配線処理が行われるプリント基板と裏面のプリント配線処理が行われるプリント基板とが、それぞれ異なる品目（の処理番号）として扱われる。図 8 中の機械 4 における品目 P — 1 及び品目 P が、これに当たる。

( 2 ) データに関する必要条件

2 a )各品目の出荷要求データは、計画対象期間に亙ってタィムスロット別に所与である。

2 b ) どのタイムスロットにおいても、処理時間で把握されるネットの累積出荷要求量が工程能力を超えてはならない。実際には切り換えの際の段取時間も関係するが、本実施形態では実行可能解の存在条件は満たされているものとして取り扱う。

( 3 ) 工程間移動時間

工程間移動時間あるいは（工程間移動に伴う）処理のリードタイム（処理を先行させる時間）を無視できないときは、所要量を展開するためのモデルにおいてそれらを考慮する。

( 4 ) 離散化と丸め誤差

本実施形態では、スケジューリング問題を予め離散化問題に定式化して取り扱う。タイムスロットの刻み幅は、許容できる丸め誤差に基づいて定める。例えば、段取時間の長さがそれぞれ 2 〜 3 時間、計画対象期間が 2 週間（ 2 4 時間 X 1 4 日）の問題に対して、刻みを 3 0 分に定めれば、丸め誤差は 1 5 分となる。この場合、問題は 2 X 2 4 X 1 4 = 6 7 2 タイムス口ットの最適制御過程になる。

( 5 ) モデルの分解能を高めるための処置

通常のスケジユーリングにおいては、オペレーションをぁたかも所与の単位あるいは既存のオブジェクトであるかのようにして取り扱うことが多い。ところが、本実施形態においては、それに対応するものを認めない。本実施形態における決定の最小単位は、品目を各タイムスロットにおいて "処理するか、しないか" を表す、 1 — 0 の決定変数である。この決定変数自体は、ディジタル画像処理におけるピクセルのようなものであって、 1 か 0 の数にすぎないが、これらが集まつて決定の局面を表すことになる。例えば、ある品目と機械設備に対して連続するタイムスロットが値 1 を取れば、それはロットのサイズを表すことになる。〈用いる記号〉

( 1 ) 添字とその集合

まず、本実施形態で適用される添字とその集合を、次のように定義する。

i ：品目またはその処理番号， i E I ( 1 , 2 ,…， n i ) 但し i = 0 は巿場（システムの外）を表す

k ：機械番号， k E K ( 1 , 2 ,…， n _k)を表す

t : タイムスロット番号， t E T ( l , 2 , '" , n _t)を表す A ：仕掛品目の集合

S (i) ：品目 i の後続直結点の集合

K ( i ) ：品目 i の処理に利用できる機械の集合

M (i) ：機械 k が処理できる品目の集合

P (i) ：品目 i の先行直結点の集合

( 2 ) 入力データ

次に、本実施形態で適用される、予め設定される入力データ（生産データ及び出荷要求量データ）を、次のように定義する。

_{P i} ^k : 機械 k におけるタイムスロット当りの品目 i の処理量

s _imax ^k ：機械 k の品目 i に対する段取時間

s _i0 ^k ：機械 k , 品目 i のタイムスロット t = 0 における段取りの残り時間、即ち初期値

X io ：品目 i のタイムスロット t = 0 における実際の在庫量，在庫を持たない問題に対しては 0 とする

δ _i0 ^k ：機械 k における品目 i のタイムスロット t = 0 における処理の状態、即ち初期値

r _i0t ：タイムスロット t における品目 i の外部需要を示す出荷要求量データであり、システムの外へ例えば補修部品などとして引かれる分

P ij ：品目 j に組み込まれる品目 i の、品目 j 1 単位あたりの所要量

c ：機械 k における品目 i の段取費用

h _{i :} 品目 i の処理によって新たに付加される価値に対する、タイムスロット当たりの在庫保管費（ェシヱロン在庫保管費）

r i i t ：タイムスロット t において品目 j を生産するために使用される品目 i の所要量

r i . _t ：品目 i のタイムスロット t における所要量

τ ij ：品目 j に組み込まれるまでの品目 i のリードタイム ( 3 ) 決定変数と状態変数

次に決定変数と状態変数を次のように定義する。

6 _{i t}k ：タイムスロット t における機械 k の品目 i の処理を表す決定変数

6 _it ^k は品目 i カタイムスロット t において機械 k により処理されるとき 1 、それ以外のとき 0

ここに、 5 _{i t} は S _{i t}l, l G K (i)を要素とするベクトノレ，

δ i = 、 δ i 1,…， δ it,… δ i_nt)

δ = ( δ …， δ … δ _ni)

s _it ^k ：品目 i のタイムスロット t における機械 k の段取りの残り時間

0 max s it は s ti¹, l e K (i)を要素とするベクトル s i = ( s iい … ， s i_t，… s int)

s = ( s … ， s … s _ni)

X _{i t} ：品目 i のタイムスロット t 末における見かけ上の在庫量

x _{i t} の定義式は次の通り

^Xit ―ズ ίθ—'- (1)

に

s" = 0のとき

その他

しかし、品目 i が最終品目の場合には、見かけの在庫は実在庫と一致する

ここに

^Xi一 V |'1，···，·½,'··， ^Xin_t )

X ~

上記式（ 1 ) では、 x _{i t} が、右辺の第 1 項で示される初期在庫 x _{i 0} と右辺の第 2 項で示される累積量との和から、右辺の第 3 項で示される累積量を差し引いたものとして定義されている。右辺第 2 項は、タイムスロット t ' における品目 i の処理量の t ' = l 力ら t ' = t までの総和、つまりタイムスロット t 末までの品目 i の処理量の累積量（累積生産量）を表す。右辺第 3 項は、タイムスロット t ' における品目 i の所要量の t ， = 1 から t ' == t までの総和、つまり外からのタイムスロット t 末までの各タイムスロットにおける出荷要求をその品目 i に展開してこれの累積量を取ったものを表す。なお、 X i ₀ は仕掛品 i G Aに対しては、見かけの在庫量 X i _t のタイムスロット t = 0 における値、即ち初期値である。しかし、式（ 1 ) では、 X i 0 は実際の初期在庫を表す点に注意されたい。

〈制約条件〉

( 1 ) 各種所要量の関係

品目 j の所要量は、当該品目 j に品目 i が組み込まれるまでの品目 i のリードタイム τ i j を考慮して品目 i に展開される。ここに品目 i は仕掛品である。したがって、 r i j _t は p ij とリードタイム τ i j が反映された r j . ( _t— _τ i j)とを用いて下記式（ 2 ) のように表される。また、 r j.t は r ijt と r _i()t を用いて下記式（ 3 ) のように表される。 /£ ，ゾ eS ')のとき

その他 rijt = iit- ,) ） ri t = Ζ ·, + (3) 上記式（ 3 ) では、 r j.t は、右辺第 1 項で示される累積量と、右辺第 2 項で示される、タイムスロット t においてシステムの外へ引かれる量との和により表されている。右辺第 1 項は、 S (i)に含まれる全品目：）についての、タイムス口ット t において品目 j を生産するために使用される品目 i の所要量 r i i _t の総和、つまり後工程（後続直結点）の品目 j に組み込まれる量を表す。

( 2 ) 状態推移

機械の段取時間の残り時間（残り段取時間）の推移方程式：

s i _t ^k は、上述のように、タイムスロット t における各品目 i の段取時間の残り時間（残り段取時間）を表す。 s _{i t} ^k は、機械（生産ライン）の遊休中は s _{i t}k= 0 で、品目を切り換えたとき、即ち処理状態が S _{i t}一 = 0 から δ _{i t} ^k= 1 へ変わったときに s _imaxk となる。以後 s _{i t}k は、時間が 1 タィムスロット経過する毎に 1 づっ 0 になるまで減少し、それ以後は再び切り換えが起こるまでその状態を維持する。したがって s _it ^k は次式に従う。

ここに 0)+ = max(0, y)を表す

上記式（ 4 ) の右辺第 1 項は、 δ _{i t}— = 0 力ら δ _{i t} ^k= 1 へ変わったときに s _imax ^k となる残り段取時間の状態遷移を示す。右辺第 2 項中の（ S it— — 1 )は 1 タイムスロット経過する毎に _{S i t}k が 1 ずつ減少する状態を示す。

在庫の推移方程式：

タイムスロット t における各品目 i の実処理は、 S _{i t}k = 1 かつ s _{i t} ^k= 0 の状態のときに限られる。したがって、在庫推移は以下の式に従う。

上記式（ 5 ) 中の x _{i t} は、品目 i のタイムスロット t —

1 末における見かけの在庫量（右辺第 1 項）とタイムスロット t における処理量（右辺第 2 項）との和から所要量 r i._t (右辺第 3項）を引いたものとして表されている。 _{r i} . t は、外部需要を展開して得られるタイムスロット t の所要量である。

繰り返すが、右辺第 3項は、後続直結点からの要求量でなく、外部需要を展開して得られる所要量 r i . t を表す。したがって、 X i _t は仕掛品 i e Aに対しては、タイムスロット t 末における見かけの在庫量を表す。し力、し X i _t は、 t = 0 に対しては実在庫を表す。また X i _t は、最終品に対しても実在庫を表す。

機械干渉に関する制約：

どのタイムスロット t においても、機械 k は高々 1 品目しか処理できない。ある品目の段取り中または処理中に、別の品目の段取りを行うこともできない。この制約を機械干渉に関する制約と呼び、次式が成立する必要がある。

∑°it ^{≤ 1} (6) 品切れを生じないための条件（品切れ禁止制約）：

どのタイムスロット t におけるどの品目 i に対しても品切れは許されない。これを在庫の非負条件と呼ぶ。最終品目については、見かけの在庫が同時に実在庫を表す。このため、在庫の非負条件は、部分最適化問題の中で陽に取り扱われるところが、仕掛品については実際の仕掛品を定式化して、これの非負条件を設定しなくてはならない。

タイムスロット t における品目 i の仕掛品在庫量は、初期在庫量 x _{i 0} と累積生産量との和から累積払い出し量を除いた量である。但し、直接外部へ出荷された量 r _{i 0t} は予め差し引いておかなくてはならない。したがって、タイムスロット t における品目 i の仕掛品在庫量の非負条件は次式のように表される。

-

上記式（ 7 ) の左辺第 2 項は、各タイムスロットにおいて品目 i の処理量から直接外部へ出荷された量を予め差し引いた処理量のタイムスロット t 末までの累積量、つまり累積生産量を表す。左辺第 3 項はタイムスロット t 末までの累積払い出し量を表す。

ところが品目が最終品の場合には、式（ 7 ) 左辺の第 1 項及び第 2 項の部分のみとなる。上記式（ 7 ) の制約式に見かけの在庫量の定義式（ 1 ) を代入して整理すると、次式を得る。

ここに、左辺第 2 項は、リードタイム _{T i}j = 0 の場合には式（ 2 ) , ( 3 ) 力、ら値 0 となって消える。

使用できる機械台数の制約：

同時に使用できる機械は高々 c 台に限られるしたがって次式が成立する必要がある。

(9)

〈コスト〉

スケジユーリング問題で関連する費用には 2種ある。 1 つは、機械 k が品目 i への切り換え時に発生する段取費 _{C i}k である。もう 1 つは、各タイムスロット t 末毎に見かけの在庫量 x _{i t} に比例して発生するェシエロン在庫保管費 h i である。これらは、それぞれ _{C i} ^k ( l 一 S _{i t}— i^ S itk, h i x _{i t} により表される。したがって品目 i のタイムスロット t におけるコストを f i ( δ j, Sj , x i) で表すと、このコスト f i

( δ i , Si , x i ) 、即ち品目 i におけるコスト関数は次式

( 1 0 ) で表される。

/^ ,_Χί) =∑ί∑ς (卜 +/½ (10)

teT keK(i) ノ

ここで、タイムスロット t におけるコストは、タイムス口ット t 一 1 における決定変数 δ i _t- にも依存する点に注意されたい。

〈問題〉

以上により、結局、取り扱うべき最適化問題は、式（ 1 0 ) のコスト f i ( S i , si, x i) の全品目についての総和を表す関数の値、つまり目的関数の値を、一定の制約のもとで最小とすることである。よって、最適化問題は次式に定式化される。 mn ( ， ')

s-t. (4), (5), (6), (8), (9) なお、式（ 1 1 ) 中の s . t . ( 4 ) , ( 5 ) , ( 6 ) ， ( 8 ) , ( 9 ) は、取り扱うべき問題が式（ 4 ) , ( 5 ) , ( 6 ) , ( 8 ) , ( 9 ) の制約を受けることを示す。式 ( 4 ) の制約とは、機械の残り段取時間の推移方程式による制約である。式（ 5 ) の制約とは、見かけの在庫に対して定義された在庫の推移方程式による制約である。式（ 6 ) の制約とは、機械干渉に関する制約である。式（ 8 ) の制約とは実際の仕掛品在庫に対する品切れ禁止制約、つまり実際の仕掛品在庫に対する非負制約式による制約である。式（ 9 ) の制約とは、使用できる機械台数の制約を受けることを示す。

《ラグランジュ分解調整法に基づく解法》

〈制約条件の取り扱い〉

この問題には、制約条件として、式（ 2 ) , ( 3 ) ， ( 4 ) , ( 5 ) ，（ 6 ) , ( 8 ) , ( 9 ) が関係している。ここに提案する解法ではこれらの制約条件の取り扱い方が大きく 2通りに分かれることに注意されたい。第 1 は部分問題の中に取り込まれて、個々の問題を解く際に陽に取り扱われるものである。第 2 は相互関係制約として複数の部分問題に亙って関係するものである。

式（ 2 ) , ( 3 ) は入力データ間の関係を表すもので決定変数を含まないから、上記のいずれにも入らない。式（ 4 ) 及び（ 5 ) は推移方程式であり、品目に固有である。このため、式（ 4 ) 及び（ 5 ) は、品目別の部分問題を動的計画法で解くときに欠かすことができない。したがってこれらは第 1 の種類に属する。同時（一度）に使用できる機械の制約式 ( 9 ) についても品目に固有である。よって、式（ 9 ) も第 1 の種類に属し、やはり部分問題の中で取り扱うことにする。ところが、機械干渉に関する式（ 6 ) は複数の品目に関係している。このため式（ 6 ) は、第 2 の種類である相互関係制約に属する。次に、品切れを避けるための制約式（ 8 ) については注意が必要である。即ち、品目が最終品目の場合には、式（ 7 ) において左辺第 3項が関係しないから、初め力、ら処理の独立性が成り立つている。この場合、在庫の非負制約は、部分問題の中で陽に取り扱うことができる。これに反して品目が仕掛品の場合には、上記第 3項が関係して、処理の独立性が犯される。この場合、在庫の非負制約は、最適化スケジューリングの基本原理において既に説明した理由により、部分問題の中で取り扱うことはできない。そこで本実施形態では、処理の整合性を保証するために、式（ 8 ) を第 2 の種類である相互関係制約として取り扱う。〈ラグランジュ関数〉

相互関係制約、即ち、機械干渉の制約（ 6 ) と仕掛品在庫に対する非負制約（ 8 ) とを緩和して、次式に示すラグランジュ関数を導く。 O, ） = J /； {δ₍ , Si , x_t )

ここに、 _tk と； _it とは、それぞれ、機械干渉制約条件 ( 6 ) と仕掛品在庫の非負条件（ 8 ) に対するペナルティコスト（ラインの使用料）を表すラグランジュ乗数である。但し、！；は， l e K (i)を要素とするベクトノレであり、 μ - ί μ ^ /ΐ ΐ, .'- , μ ηΐ) とする。同様に、ぇ丄もベクトルであり、え i= ( λ , ·■■ , λ _it, ··· , λ _int) , λ = ( λ ι, - , λ ι, ···, λ _nt) とする。

〈ラグランジュ問題〉

結局、制約条件として式（ 2 ) , ( 3 ) , ( 4 ) ，（ 5 ) ( 6 ) , ( 8 ) ，（ 9 ) が関係している上記式（ 1 1 ) の問題は、次式（ 1 3 ) に示すラグランジュ問題と同値になる。この式（ 1 3 ) は、式（ 1 1 ) と関係している制約式（ 2 ) ( 3 ) , ( 4 ) , ( 5 ) ，（ 6 ) , ( 8 ) , ( 9 ) 中の式 ( 4 ) , ( 5 ) , ( 9 ) を制約条件とする

max min ∑(μ, λ, S, s, χ)

(13) t. ⁵ (4), (5), (9)

ここで、問題を品目別に分解するために、式（ 1 2 ) をまず品目 i について整理して、以下のラグランジュ関数を導く ,) = ( ,) +∑ ∑A

teT keK(i)

ここで、 a (i)を、品目 i が後続直結点を持つとき（つまり仕掛品となり得るとき） 1 、それ以外のとき 0 と表現すれば、上記式（ 1 4 ) は次式のように表すことができる。

L( ,X,S,S,X) =

iら I ί€Γ keK

〈部分最適化問題〉

上記式（ 1 5 ) 力ゝら、式（ 1 1 ) で示される問題は、所与の μ , λ に対して、以下の部分問題（部分最適化問題）に分解することができる。

mm

(16) s. (4)ズ5),(9)

品目 i に対する、式（ 1 6 ) で示される部分最適化問題は所与の，えに対して、他と独立に解くことができる。この解法については後述する。〈ラグランジュ乗数の調整〉

本実施形態では、ラグランジュ乗数として、 _t ^k と； I i _t との 2 種が用いられる。このため、繰返し計算の第 V 回目でのラグランジュ乗数の更新には、機械干渉に用いるラグランジュ乗数の更新ルールと、仕掛品の在庫充足に用いるラグランジュ乗数の更新ルールとの 2 つが必要となる。

機械干渉に用いるラグランジュ乗数の更新ルール：まず、機械干渉に用いるラグランジュ乗数の更新ルールは次式に示される通りである。 Γ - 1 ( 1 7 )

eM (り

仕掛品の在庫充足に用いるラグランジュ乗数の更新ルーノレ：

次に、仕掛品の在庫充足に用いるラグランジュ乗数の更新ルールは次式に示される通りである。 υ-Ι

八" =

t'=\

なお、上記式（ 1 8 ) において α , ]3 はスカラーステップサイズである。この α ， 0 の値は数値計算で試行錯誤的に決められる。ここで、 ct , i3 をそれぞれ k (機械）， i (品目）に依存させることも可能である。《部分最適化問題の動的計画法》

次に、式（ 1 6 ) で示される部分最適化問題を動的計画法に再定式化して解く方法について説明する。

〈取り得る状態〉

タイムスロット t において取り得る決定 S it^k は、先行するタイムスロット t — 1 における在庫状態 X に依存するばかりでない。即ち決定 S itk は、先行するタイムスロット t — 1 における利用可能なすべての機械の状態、及び同じタイムスロッ卜 t における残り段取時間 s i _t—丄 ^k にも依存する。 ( δ _{i t}-l^k. s _{i t}— ）から（ δ _{i t} ^k, s _{i t} ^k)への状態推移の関係を整理すれば、図 5 に示すようになる。図中の〇印はタイムスロット t 一 1 の状態に対して許される決定が存在することを、 X印はそうでないことを、それぞれ表している。

図 6 は、この（ S _{i t} ^k, s _it ^k)の状態遷移を示す。図 6 において、（0 ， 0 )の状態 6 1 が次のタイムスロットで取り得る状態は、同じ状態 6 1 または（ 1 ， s _imax ^k)の状態 6 2 のいずれかである。状態 6 1 は、機械 k の遊休中を示す。また、状態 6 2 は、品目を切り換えたとき、つまりセットアップの開始時を示す。この状態 6 2 、即ち（ 1 , s i_max ^k)の状態 6 2 が次のタイムスロットに取り得る状態は、（ 1 , s i _maxk— 1 )の状態 6 3 のみである。

状態 6 3 は、セットアップ開始時から時間が 1 タイムス口ットだけ経過し、残り段取時間が s _imax ^k一 1 となったことを示す。以下、同様にして、時間が 1 タイムスロット経過する毎に、（ S i十 ^k, s _{i t} ^k) のうちの S i ₊ ^k が 1 のままの状態で、 s _itk だけが 1 ずつ減少していく。や力 Sて（ S _itk， s _itk) は、 ( 1 , 1 ) の状態 6 4 に遷移する。状態 6 4 は残り段取時間が 1 ( 1 タイムスロット分）であり、セットアップ終了直前の状態となったことを示す。状態 6 2 から状態 6 4 までの期間がセットアップ中の期間 6 5 となる。状態 6 4 、即ち（ 1 , 1 ) の状態 6 4 が、次のタイムスロットに取り得る状態は、 ( 1 ， 0 ) の状態 6 6 のみである。状態（期間） 6 5 は生産中を示す。状態 6 6 、即ち（ 1 ， 0 ) の状態 6 6 が、次のタィムスロッ卜に取り得る状態は、同じ状態 6 6 または（ 0 ， 0 ) の状態 6 1 のいずれかである。

〈最適コスト関数とその計算〉

次に、最適コスト関数とその計算について説明する。本実施形態では、所与のラグランジュ乗数 /X , λ i に対して、最適コスト関数を

V _t ^ ^δ it. ^s it. ^x it' ' ^λ

で表す。この最適コスト関数 V _t を、タイムスロット 0 力、らタイムスロット t までの各タイムスロットにおいて採られた最適決定に伴って発生するコストの和であると定義する。伹し、タイムスロット t において、品目 i の決定変数（機械のセッティングの状態）、残り段取時間、在庫状態（タイムスロット末の在庫量）を、それぞれ S iい s _it, x _it であるとする。

ここで重要なことは、上記最適コスト関数に、状態変数のベタトルとして、べクトノレ s _it と変数 x _it の他に、決定変数のベクトノレ S _it が入っている点である。つまり、決定変数 δ i _t が状態変数の役割も担っている点である。これはタィムス口ット t において発生する段取りコストが、タイムスロット t — 1 の決定にも依存することに起因している。言い換えるならば、タイムスロット t において発生するコストを計算するために、先行タイムスロット t 一 1 におけるの情報が必要になるからである。この場合、最適コスト関数は動的計画法による次の再帰関係式で表すことができる。

₀ (所与の ¾) ,。，¾

V_Q{S_iQ,s_iQ,x_iQ^, _i) = ' のとき）（19)

+ 00, (その他）

V e に対して、 0≤ ½_! < x_imaxのとき

mm (20) " keK(i) jeP(i)

+ 1( - 1,ぶ" -い ,卜い

ここで x _{i t}— i が許容範囲にないときは、任意の δ

s _{i t}-i^k に対して、 V _t ( δ _{i t}, s _{i t}, x _{i t}, μ , λ ι) は常に +∞である。このとき、 S _{i t}— い s _{i t}, x _{i t}, μ λ i) は上記式（ 2 0 ) の最適決定を表すものとする。 s _{i t}l = 0 ( 1 e K (i) ) の場合には、所与の S it¹, s it¹ ( 1 e K (i) ) , χ _{i t}, μ , λ i と選択された決定 S _it—

( l E K (i) ) に対して、前記式（ 4 ) ，（ 5 ) から s it— i k x _{i t}-i を求めれば、タイムスロット t — 1 における最適コスト関数の値が決まる。ところが、 s _{i t}l = 0 の場合、その s _{i t} ¹ = 0 の状態に推移するタイムスロット t 一 1 における s it- I¹ の状態は、 s it— = 0 と s it-^ = 1 のいずれをとるか、特定できない。そこで、これに対処するために、上記式（ 2 0 ) で示される最小値（ m i n ) が、 δ i _t—丄の他に、 s it- 1 に対してもとられている。一方、タイムスロット t において発生するすべてのコストは確定している。したがつて上記式（ 2 0 ) が計算できる。

〈最適解の決定〉

今、品目 i について、上記式（ 2 0 ) の最適コスト関数値 V _t ( δ _{i t}, s _{i t}, x _{i t}, μ , λ i) と、最適決定即ち S _{i t}-

!* ( 6 _{i t )} s _{i t}, x _{i t}, μ , λ i) とが、各タイムスロット t ( t = 1 , ·'· , n _t) に対してすべて求められているものとする。また、品目 i の各タイムスロット毎の V _t ( 5 _{i t}, s if x if ' i) 及ひ ⁵ it - l* ( ⁵ it' ^s it' ^x it- ' λ i) とが、例えば表の形でメモリ（ここではコスト記憶ェリア 2 2 3 ) 内に格納されてレ、るものとする。さらに、 s it¹ = 0 ( 1 e K (i) ) に対しては、最適な残り段取時間 s it-1* ( 5 _{i t}, s _{i t}, x _{i t >} μ , λ i) についても、メモリに同様に格納されているものとする。このときの、品目の最適解、即ちスケジュールと状態推移とを確定するための手続きについて、図 4 のフローチャートを参照して説明する。

まず、 t = n _t のタイムスロットに対して取り得るすべての S j_い s _{i t >} X _it の組み合わせ（ 5 _{i t}， s iい x _{i t}) の中力、ら V _t ( 6 _{i t}, s it, x _{i t}, μ , λ i) が最小となる S _{i t}, s _{i t}, x it を求めて、最適な解として確定する（ステップ 4 0 5 , 4 0 6 ) 。この最適な解 S i s _{i t}, x _it を、 δ it*, s _{i t}*, x _it*とする。次に、 δ _{i t}*， s _{i t}*. x _it*に対し最適な決定 δ _{i t}— （ δ _{i t}*， s _{i t}*, x _it*) を特定する (ステップ 4 0 7 ) 。この S _{i t}*， s _{i t}*， x _{i t}*を前記式 ( 4 ) ，（ 5 ) に代入して s _{i t}— ， x it- を求める（ステップ 4 0 8 ) 。なお、 δ _{i t}*, s _{i t}*, x _it*と、コスト記憶エリア 2 2 3 に表形式で格納されている、品目 i の各タイムスロット毎の S i_t一丄* ( S i s _{i t} , X _{i t} , μ , λ i) と力ら、 s it-i*, x it- を求めることも可能である。

次に、 t を 1 だけデクリメントする（ステップ 4 0 9 ) 。このデクリメント後の t 力 S 1 より小さくならなければ（ステップ 4 1 0 ) 、そのデクリメント後の t に対して上記ステツプ 4 0 6 以降の処理を行う。これを t = l まで繰り返す（ステツプ 4 1 0 ) 。

以上、本実施形態で適用する最適化スケジユーリングの基本原理と、当該基本原理における定式化の詳細と、ラグランジュ分解調整法に基づく解法と、部分最適化問題の動的計画法とについて説明した。

<最適化スケジユーリングの実現例〉

次に、上記した最適化スケジユーリングの実現例について説明する。図 1 のスケジューリング装置は、上記した最適化スケジユーリングの基本原理を適用して最適化スケジユーリングを行う。そのため、スケジューリング装置は、最適化部 1 1 と、在庫量抽出部 1 2 と、残り段取時間抽出部 1 3 と、機械干渉判定部 1 4 と、機械干渉制御部 1 5 と、スケジユール生成部 1 6 と、主制御部 1 7 と、充足判定部 1 8 と、在庫制御部 1 9 とを備えている。これら各部 1 1 〜 1 9 は、図 2 の計算機内の C P U 2 1 が最適化スケジユーリングプロダラム 2 4 1 を実行することにより実現される機能要素である。

最適化部 1 1 は、各品目 i について、式（ 1 6 ) の部分最適化問題を、他の品目とは独立に解き、その解を求める動作を実行する。この際、最適化部 1 1 は、上記部分最適化問題を、在庫推移と残り段取時間推移の制約のもとで、式（ 2 0 ) の最適コスト関数を用いて解く。在庫量抽出部 1 2 は、最適化部 1 1 での動作に必要な在庫量を抽出する。残り段取時間抽出部 1 3 は、最適化部 1 1 での動作に必要な残り段取時間を抽出する。

機械干渉判定部 1 4 は、最適化部 1 1 により求められた品目 i 毎の解から、機械干渉が解消されていると見なせるか否かを判定する。機械干渉制御部 1 5 は、機械干渉が解消されていない場合に、機械干渉が減少するように最適化部 1 1 を制御する。具体的には、最適化部 1 1 により用いられる最適コスト関数中の、機械干渉の制御（調整）に必要なラグランジュ乗数（ _tk) を更新する。

充足判定部 1 8 は、最適化部 1 1 により求められた品目 i 毎の解から、仕掛品在庫が充足しているか否かを判定する。在庫制御部 1 9 は、仕掛品在庫が充足していない場合、つまり仕掛品在庫の品切れを起こしている場合に、仕掛品在庫が充足するように最適化部 1 1 を制御する。具体的には、最適化部 1 1 により用いられる最適コスト関数中の、仕掛品の充足の制御（調整）に必要なラグランジュ乗数（え it) を更新する。

スケジュール生成部 1 6 は機械干渉及び仕掛品在庫の品切れが解消されたものと判定された場合、その際に求められている解を用いて生産スケジュールを生成する。主制御部 1 7 はスケジユーリング装置全体を制御する。

主メモリ 2 2 には、生産データ記憶エリア 2 2 1 と、出荷要求量記憶エリア 2 2 2 と、コスト記憶エリア 2 2 3 とが確保されている。エリア 2 2 1 は、生産データを格納するのに用いられる。この生産データは、品目 i 及び機械 k別の p i ^k , s _imax ^k, s _{i 0} ^k, δ _io ^k, c ik の各データと、品目 i 別の x i 0，， P ij , h i , て i j の各データと、品目 i 毎の各タイムスロット t における r _{i i t}， r i . _t の各データとを含む。ェリア 2 2 2 は、出荷要求量データを格納するのに用いられる。出荷要求量データは、品目 i 毎の各タイムスロット t における r _{i 0t} を含む。エリア 2 2 3 は、最適化部 1 1 で算出されたタイムスロット t までのコストの和 V _t ( S iい s _{i t} , x it , , λ ί ) 及び当該和 V _t ( S iい s _{i t} , x _{i t} , β , λ i) に対応する 5 _{i t}*， s _{i t}*, x _{i t}*を表形式で格納するのに用いられる。ここで、 δ _{i t}*， s _{i t}*, x _{i t}*を格納するエリァを別に確保することも可能である。

主メモリ 2 2 には更に、中間結果記憶エリア 2 2 4 と、最終結果記憶エリ了 2 2 5 と、スケジュール記憶エリア 2 2 6 とが確保されている。エリア 2 2 4 は、最適化部 1 1 で最適部分問題を解くことにより求められた解の中間結果を格納するのに用レ、られる。エリア 2 2 5 は、最適化部 1 1 で最適部分問題を解くことにより求められた解の最終結果を格納するのに用レヽられる。エリア 2 2 6 は、スケジュール生成部 1 6 により生成された生産スケジュールを格納するのに用いられる。

次に図 1 の構成の動作を、図 3 のフローチャートを参照して説明する。まず、図 1 のスケジューリング装置を用いて最適生産スケジュールを作成するには、 P i^k, s _imax^k. s _i0 ^k, δ _i0 ^k, c i^k の各データと、品目 i 別の x _i0, , ρ i j , h i, τ i j の各データと、品目 i 毎の各タイムスロット t における _{r i}j_t, r i . _t の各データとを含む生産データを予め入力しておく必要がある。ここでは、この生産データを、ォペレータがキーボード 2 5 を操作することにより、例えば表形式で入力するものとする。この生産データを、通信回線を介して外部から入力することも可能である。

入力された生産データは、主制御部 1 7 の制御により、主メモリ 2 2 内の生産データ記憶エリア 2 2 1 に格納される。また、このエリア 2 2 1 に格納された生産データを H D D 2 3 に保存して、再利用することができる。また、生産スケジユールの生成が必要となる都度、品目 i 毎の、指定タイムス口ット t における r iOt を含む出荷要求量データが入力されて、主メモリ 2 2 内の出荷要求量記憶エリア 2 2 2 に格納される。

ここでは、計画対象期間が 2 週間であり、 1 日 7 時間の 3 シフトで生産が行われるものとする。また、タイムスロット幅が 3 0 分に設定されるものとする。この場合、計画対象期間全体のタイムスロット数 Tは 5 8 8 である。つまり本実施形態では、出荷要求量データを入力することで、計画対象期間には、 3 0 分刻みで 5 8 8 個のタイムス口ットが設定される。この刻み幅、つまり 1 タイムスロット期間は小さレ、ほど、最適化問題（数理モデル）の解像度を上げることができる。計算量は刻みの数（タイムスロット数）の 1 次のオーダーにしかならないから、刻み幅を小さくすることをそれほど恐れる必要はない。即ち、刻み幅を半分にしても計算時間は倍にしかならない。勿論、必ずしも刻み幅を著しく小さくする必要はなく、丸め誤差が無視し得る程度であれば、実用上問題ない。

この状態で、キーボード 2 5 からスケジユーリングの開始指示が入力されると、主制御部 1 7 により初期化処理が行われる。この初期化処理では、繰り返し数（繰り返し番号） V が初期値 0 に設定される（ステップ 3 0 1 ) 。また、中間結果記憶エリア 2 2 4 上の品目 i ( i G I ( 1 , 2 , ··· , n i) ) 別、タイムスロット t ( t G T ( 1 , 2 , ··· , n _t) ) 別及び機械 k ( k e K ( 1 , 2 , … ， n _k) ) Sリの、それぞれ決定変数 δ itk v 及び s itk v が初期値 o に設定される（ステップ 3 0 2 ) 。また、タイムスロット t ( t e T ( 1 , 2 , ··· , n _t) ) 別及び機械 k ( k e K ( 1 , 2 , ··· , n _k) ) 別のラグランジュ乗数 _t ^{k ν} が、初期値 0 に設定される（ステップ 3 0 3 ) 。このステツプ 3 0 3 では、タイムスロット t ( t e T ( 1 , 2 , ··· , n _t) ) 別のラグランジュ乗数； L _t ^v も初期値 0 に設定される。主制御部 1 7 はステップ 3 0 1 〜 3 0 3 を実行すると、最適化部 1 1 を起動する。最適化部 1 1 はまず、品目 i を 1 に初期設定する（ステップ 3 0 4 ) 。次に最適化部 1 1 は、品目 i の式（ 1 6 ) に示す部分最適化問題を、残り段取時間推移方程式（ 4 ) 及び在庫推移方程式（ 5 ) の制約のもとで解く（ステップ 3 0 5 ) 。ここでは、上記部分最適化問題を解くのに、式（ 2 0 ) の最適コスト関数が用いられる。また、部分最適化問題を解いた結果、品目 i について、当該品目 i の処理に利用可能な各機械 k別に、各タイムスロット毎の解 δ _{i t} ^{k v} ( V t e τ , k e K (i) ) が求められる。

図 4 は、このステップ 3 0 5 の詳細な手順を示したものである。ここでは最適化部 1 1 は、品目 i の部分最適化問題を解くために、以下に述べる最適コスト関数値 V _t ( S _{i t}， s it , x it. β , え i) と最適決定 S _{i t}— i^ i S iい s _{i t}, x _it) とを求める。そのため最適化部 1 1 は、まずタイムス口ット t を 1 に設定する（ステップ 4 0 1 ) 。そして最適化部 1 1 は、品目 i について、取り得る（実行し得る）すべての組み合わせの ( δ iい s it, x _it) に対し、最適コスト関数値 V _t ( δ _{i t}, s _{i t}, x _{i t}, μ , X i) を算出する（ステップ 4 0 2 ) 。この最適コスト関数値の算出は、品目 i の処理 (生産）に使用可能な機械 k の範囲（ k G K (i) ) で前記式 ( 2 0 ) の最適コスト関数を用いて実行される。上記ステツプ 4 0 2 では、上記算出された最適コスト関数値 V _t ( 6 it, s _{i t}, x _{i t}, u , λ j) が、そのときの最適決定 S _{i t}一 ^ ( δ it, s _{i t}, x _it) と共に、コスト記憶エリア 2 2 3 に表形式で格納される。

次に最適化部 1 1 は、 t を 1 だけインクリメントする（ステツプ 4 0 3 ) 。もし、インクリメント後の t が n _t より大きくなければ（ステップ 4 0 4 ) 、最適化部 1 1 は、そのィンクリメント後の t に対して上記ステップ 4 0 2， 4 0 3 の処理を行う。このステップ 4 0 2， 4 0 3 の処理は、 t = n _t まで繰り返される（ステップ 4 0 4 ) 。

やがて、インクリメント後の t 力 S n _t より大きくなると、最適化部 1 1 は t を n _t に設定する（ステップ 4 0 5 ) 。そして最適化部 1 1 は、コスト記憶エリア 2 2 3 上の最適コスト V _t ( 6 _{i t}, x _{i t}, s _it) を t = n _t 力ら逆に迪る。即ち最適化部 1 1 は、先に説明したように、まず、 t = n _t のタィムスロットに対して取り得るすべての S iい s _{i t} , X _{i t} の組み合わせ（ S _{i 1:}， s _{i t}, x _it) の中力ら V _t ( δ _{i t}, s _{i t}, x _{i t )} μ , λ i) の最小値（最適コスト）を探し、その際の S _{i t}, s _{i t}, x _{i t} を最適解 S _{i t}*， s _{i t}*, x _{i t}*とする (ステップ 4 0 6 ) 。

次に最適化部 1 1 は、 δ _{i t}*， s _{i t}*, x _it*に対し最適な決定 δ it- ( δ _{i t}*， s _{i t}*, x _{i t}*) を特定する（ステップ 4 0 7 ) 。最適化部 1 1 は、この 5 _{i t}*, s _{i t}*₍ x _{i t}*を用いて、最適コスト V t に至った直前のタイムスロット t— 1 での s _{i t}- 1*， x _{i t}- を求める（ステップ 4 0 8 ) 。ここでは、 δ _{i t}*， s _{i t}*, x _{i t}*を前記式（ 4 ) , ( 5 ) に代入することで、 s _{i t} X _{i t} を求めるものとする。し力し、先に述べたように、コスト記憶エリア 2 2 3 に表形式で格納されてレ、る、品目 i の各タイムスロット毎の 5 _{i t}— ^ ( S it, s _{i t >} x _{i t}, μ ， λ i) をもとに S it-i*, x it— i*を求めることも可能である。最適化部 1 1 は、上記ステップ 4 0 6 〜 4 0 8 を、 t を 1 ずつデクリメントしな力 S ら（ステップ 4 0 9 ) 、 t = l まで繰り返す（ステップ 4 1 0 ) 。

以上のようにして、品目 i について最適コストを与える δ _{i t} ^{k v} ( t = 1 , …， n _{t )} k G K (i) ) が最適化部 1 1 により求められる（ステップ 3 0 5 ) 。すると最適化部 1 1 は、中間結果記憶エリア 2 2 4 上の S it^{k v} を、求めた最新の δ itk v に更新する（ステップ 3 0 6 ) 。

次に最適化部 1 1 は i を 1 だけインクリメントする（ステップ 3 0 7 ) 。このインクリメント後の i 力 S _{n i} より大きくないならば（ステップ 3 0 8 ) 、最適化部 1 1 は未処理の品目が存在するものと判定する。この場合、最適化部 1 1 は、インクリメント後の i で示される品目 i について、上記ステップ 3 0 5 〜 3 0 7 を実行する。

やがて、インクリメント後の i 力 S _{n i} より大きくなると、最適化部 1 1 は、 i = 1 ， …， n i のすベての品目について 8 _{i t} ^{k v} ( V i e I , t e T , k e K (i) ) が求められれたと判断する。この場合、最適化部 1 1 は、機械干渉判定部 1 4 及び充足判定部 1 8 を起動する。

機械干渉判定部 1 4 は、機械 k 毎に、その機械 k で処理 (生産）されるすべての品目 i ( i e M (i) ) の解 S _{i t} ^k v 力ら、各品目 i 間の S _{i t} ^k= l のタイムスロットの重なりの回数を表す機械干渉数を算出する。ここでは、平均機械干渉数が算出される。この平均機械干渉数は、全機械についての繰り返し数 V における全品目、全期間（全計画対象期間）に亙る機械干渉数の総和を、 n _t X n _k (全タイムスロット数 X全機械数）で除することで算出される。判定部 1 4 は、算出した機械干渉数（平均機械干渉数）が予め定められた閾値より小さいかにより、機械干渉が解消されていると見なせるかを判定する（ステップ 3 0 9 ) 。

—方、充足判定部 1 8 は、全品目 i ( i E I ( 1 , 2 ,…， n i) ) について、仕掛品在庫量がマイナスとなる（つまり非負条件を満たさなかった）タイムスロットの総数を求める。判定部 1 8 は、求めたタイムスロットの総数から、仕掛品在庫が充足しているか否かを、上記ステップ 3 0 9 において判定する。具体的には、全品目について、仕掛品在庫量がマイナスとなるタイムスロットの総数が求められる。このタイムスロッ卜の総数を n i X n t (全品目数 X全タイムスロット数）で除することで、平均的な仕掛品在庫の不足の割合が求められる。そこで、この割合が予め定められた閾値より小さいかにより、仕掛品在庫が充足しているかが判定される。ここで、各仕掛品在庫量は、ステップ 3 0 5 で求められた対応する解 δ _it ^{k v} と組をなす X _{i t} を用いて、前記式（ 8 ) に従って算出される。

もし、機械干渉が解消されているという条件及び仕掛品在庫量が充足しているととう条件の少なくとも一方の条件を満たさない場合、繰り返し数（反復回数） V が 1 だけインクリメントされる（ステップ 3 1 0 ) 。すると、機械干渉制御部 1 5 及び在庫制御部 1 9 の少なくとも一方が起動される。ここでは、機械干渉が解消されていないときは機械干渉制御部 1 5 が、仕掛品在庫量が充足していないときは充足判定部 1 8 が、それぞれ起動される。上記両条件が成立していないときは、機械干渉制御部 1 5 及び充足判定部 1 8 の両方が起動される。

機械干渉制御部 1 5 は、自身が起動された場合、機械干渉に用いるラグランジュ乗数 _t ^{k v} を前記式（ 1 7 ) により更新（調整）して、最適化部 1 1 に通知する（ステップ 3 1 1 ) 。一方、充足判定部 1 8 は、自身が起動された場合、上記ステップ 3 1 1 において、仕掛品の在庫充足に用いるラグランジュ乗数え t ^v を前記式（ 1 8 ) により更新（調整）して、最適化部 1 1 に通知する。

すると最適化部 1 1 は、更新後のラグランジュ乗数 /i _t ^{k v} 及び/または _t ^v を用いて、ステップ 3 0 5 〜 3 0 7 を品目数分繰り返し実行する（ステップ 3 0 8 ) 。これにより、品目別、機械別の解 δ it^{k v} がタイムスロット毎に求められる。やがて、上記ステップ 3 0 9 において、機械干渉判定部 1 4 により、機械干渉が解消されていると見なせると判定されたものとする。また、ステップ 3 0 9 において、充足判定部 1 8 により、仕掛品在庫量が充足していると判定されたものとする。すると、そのときの品目別、機械別の解 δ i _tk V が最終結果記憶エリア 2 2 5 に格納され、スケジュール生成部 1 6 が起動される（ステップ 3 1 2 ) 。

スケジュール生成部 1 6 は、最終結果記憶エリァ 2 2 5 に格納されている品目別、機械別の解 δ _{i t} k V をもとに、生産スケジュールを生成して、スケジュール記憶エリア 2 2 6 に格納する（ステップ 3 1 3 ) 。前記したように品目別、機械別の解 S _{i t} ^{k v} は 0 — 1 変数により表される。そこで解 δ _{i t} ^k ^v は、生産スケジュール上では、時間軸上に刻まれたタイムスロット t 毎に、品目 i 別、機械 k 別に、当該スロットで機械 k により品目 i を処理（セットアップまたは生産）すれば

1 で、そうでなければ 0 で表される。したがって、解 δ i _t ^k v における 1 の並びとその時間的位置により品目別及び機械別にロットサイズとそれらのロットの時間的位置を生成することができる。ロットの時間的位置は実行可能なスケジユールにおいてロットの順序を決定するための情報を与える。つまり本実施形態においては、品目間の解（スケジュール）の機械干渉が解消されていると見なせ、かつ仕掛品在庫量が充足していると判定される解 δ _{i t} ^{k v} が求まった時点で、口ットサイズとロット順序を同時に生成することができる。

スケジュール記憶エリア 2 2 6 に格納された生産スケジュールは、図 2 中のディスプレイ 2 6 に表示されると共に、キ一ボード 2 5 からの印刷指示入力に応じて、または自動的に、プリンタ装置（図示せず）から印刷出力される。また、この生産スケジュールをそのままの形で、または所定のデータ変換により、生産ラインでの制御情報として用いることができる。

なお、本発明は、上記実施形態に限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で種々に変形することが可能である。更に、上記実施形態には種々の段階の発明が含まれており、開示される複数の構成要件における適宜な組み合わせにより種々の発明が抽出され得る。例えば、実施形態に示される全構成要件から幾つかの構成要件が削除されても、発明が解決しょうとする課題の欄で述べた課題が解決でき、発明の効果の欄で述べられている効果が得られる場合には、この構成要件が削除された構成が発明として抽出され得る。

産業上の利用可能性

本発明によれば、多品目多工程のスケジユーリングの問題に含まれる多様な決定の諸局面を一つ一つ列挙することも意識することもなく、また人為的な制約を必要とすることなく、当該諸局面を全体最適化の視点から解決して経済的かつ合理的な実行可能スケジュールを生成することができる。

Claims

請求の範囲

1 . 複数の機械により複数の工程で当該各工程に対応した品目をそれぞれ処理し、かつ少なくとも 1 つの機械または工程では段取を伴う品目の切り換えが可能な多品目多工程生産システムに適用される生産スケジュールをコンピュータにより生成する多品目多工程口ットサイズスケジユーリング方法であって、

多品目多工程のスケジユーリングの問題に対応し、前記各工程で処理される品目別にスケジュールを求めるための、品目間の機械干渉に関する第 1 の制約及び仕掛品在庫量を非負とする第 2 の制約の付いた品目別の 1 次元部分最適化問題を、他の品目とは独立に解くステップと、

前記解くステップで求められた品目別の解をもとに前記第 1 及び第 2 の制約を充足させるための調整を行うステップと、前記調整ステップの都度、前記解くステップを再実行させるステップと、

前記第 1 及び第 2 の制約が充足した際に前記解くステップで求められている品目別の解に基づいて生産スケジュールを生成するステップと

を具備することを特徴とする多品目多工程ロットサイズスケジユーリング方法。

2 . 請求項 1 記載の多品目多工程口ットサイズスケジュ一リング方法において、

前記品目別の 1 次元の最適化問題は、前記第 1 の制約に対応する第 1 のペナルティコスト及び前記第 2 の制約に対応する第 2 のペナルティコストを含む総コストを最適化する問題である。

3 . 請求項 2記載の多品目多工程ロットサイズスケジューリング方法において、

前記解くステップで求められた品目別の解に対する各品目間の同一機械における前記機械干渉の程度から前記第 1 の制約の充足を判定するステップと、

前記解くステップで求められた品目別の解に対する仕掛品在庫から前記第 2 の制約の充足を判定するステップと

を更に具備し、

前記調整ステップでは、前記第 1 の制約の充足を判定するステップにより前記第 1 の制約が充足していないと判定された場合には、前記機械干渉の程度を小さくするように前記第 1 のペナルティコストを更新し、前記第 2 の制約の充足を判定するステップにより前記第 2 の制約が充足していないと判定された場合には、前記仕掛品在庫を充足させるように前記第 2 のペナルティコストを更新する。

4 . 請求項 1 記載の多品目多工程ロットサイズスケジュ一リング方法において、前記 1 次元の部分最適化問題は、前記第 1 の制約が第 1 のラグランジュ乗数による重み付けにより緩和されると共に前記第 2 の制約が第 2 のラグランジュ乗数による重み付けにより緩和された問題である。

5 . 請求項 4 記載の多品目多工程ロットサイズスケジューリング方法において、

を更に具備し、

前記調整ステップでは、前記第 1 の制約の充足を判定するステップにより前記第 1 の制約が充足していないと判定された場合には、前記機械干渉の程度を小さくするように前記第 1 のラグランジュ乗数を更新し、前記第 2 の制約の充足を判定するステップにより前記第 2 の制約が充足していないと判定された場合には、前記仕掛品在庫を充足させるように前記第 2 のラグランジュ乗数を更新する。

6 . 請求項 5記載の多品目多工程ロットサイズスケジュ一リング方法において、前記解くステップでは、各品目及び各機械別に、かつ計画対象期間が予め設定された時間間隔で分割された各タイムスロット毎に、そのタイムスロットが当該品目の生産のために当該機械により使用されているか否かを示す決定変数を解として取得する。

7 . 請求項 6 記載の多品目多工程ロットサイズスケジュ一リング方法において、前記第 1 の制約は、任意のタイムスロットにおける品目別及び機械別の決定変数のうち、同一機械について高々 1 品目の決定変数のみが生産のために使用されていることを示すことができるという相互関係制約である。

8 . 請求項 7 記載の多品目多工程ロットサイズスケジュ一リング方法において、前記解法ステップでは、任意のタイムスロット t における品目 i の前記決定変数を S _it、前記第

1 のラグランジュ乗数を、前記第 2 のラグランジュ乗数を λ i とすると共に、当該タイムスロット t の終了時の、次ェ程へ実際に渡される累積出荷量に代えて用いられる見かけの在庫の状態であって、当該タイムスロット t までの各タイムスロットにおける外部需要を当該タイムスロット t における品目 i に展開した累積量を用いて算出される見かけの在庫の状態、及び品目 i へのセットアップに必要な段取時間の残り時間を、それぞれ状態変数 X _{i t}， s _it として、前記 1 次元の部分最適化問題を、当該タイムスロット t までの各タイムスロットにおいて採られた最適決定に伴って発生するコストの和を表す最適コスト関数 V i ( S _it, X _it, s _it, μ , λ により解く。

9 . 請求項 8記載の多品目多工程ロットサイズスケジュ一リング方法において、前記最適コスト関数で算出されるコストは、前記第 1 のラグランジュ乗数 / i に基づいて算出される機械の使用料に相当する第 1 のペナルティコストと、前記第 2 のラグランジュ乗数に基づいて算出される機械の使用料に相当する第 2 のペナルティコストと、品目 i の処理によって新たに付加される価値に対するタイムス口ット当たりのェシェロン在庫保管費 h i 及び前記状態変数 x _{i t} で決まるコストとを含むことを特徴とする。

1 0. 複数の機械により複数の工程で当該各工程に対応した品目をそれぞれ処理し、かつ少なくとも 1 つの機械または工程では段取を伴う品目の切り換えが可能な多品目多工程生産システムにおける多品目多工程口ットサイズスケジユーリングのためのプログラムであって、

コンピュータに、

前記第 1 及び第 2 の制約を充足した際に前記解くステップで求められている品目別の解に基づいて生産スケジュールを生成するステップと

を実行させるためのプログラム。

1 1 . 複数の機械により複数の工程で当該各工程に対応した品目をそれぞれ処理し、かつ少なくとも 1 つの機械または工程では段取を伴う品目の切り換えが可能な多品目多工程生産システムにおける多品目多工程口ットサイズスケジユーリングのためのプログラムを記憶したコンピュータ読み取り可能な記憶媒体であって、

コンピュータに、

を実行させるためのプログラムを記憶したコンピュータ読み取り可能な記憶媒体。

1 2 . 複数の機械により複数の工程で当該各工程に対応した品目をそれぞれ処理し、かつ少なくとも 1 つの機械または工程では段取を伴う品目の切り換えが可能な多品目多工程生産システムに適用される生産スケジュールを生成する多品目多工程ロットサイズスケジューリング装置であって、

多品目多工程のスケジユーリングの問題に対応し、前記各工程で処理される品目別にスケジュールを求めるための、品目間の機械干渉に関する第 1 の制約及び仕掛品在庫量を非負とする第 2 の制約の付いた品目別の 1 次元部分最適化問題を、他の品目とは独立に解く最適化手段と、

前記最適化手段により求められた品目別の解をもとに前記第 1 の制約を充足させるための調整を行う機械干渉制御手段と、前記最適化手段により求められた品目別の解をもとに前記第 2 の制約を充足させるための調整を行う在庫制御手段と、前記第 1 及び第 2 の制約が充足した際に前記最適化手段により求められている品目別の解に基づいて生産スケジュールを生成するスケジュール生成手段と

を具備することを特徴とする多品目多工程ロットサイズスケジユーリング装置。

1 3 . 請求項 1 2 記載の多品目多工程ロットサイズスケジユーリング装置において、

1 4 . 請求項 1 3 記載の多品目多工程ロットサイズスケジユーリング装置において、

前記最適化手段により求められた品目別の解に対する各品目間の同一機械における前記機械干渉の程度から前記第 1 の制約の充足を判定する機械干渉判定手段と、

前記最適化手段により求められた品目別の解に対する仕掛品在庫から前記第 2 の制約の充足を判定する在庫充足判定手段と

を更に具備し、

前記機械干渉制御手段は、前記機械干渉判定手段により前記第 1 の制約が充足していないと判定された場合には、前記機械干渉の程度を小さくするように前記第 1 のペナルティコストを更新し、

前記在庫制御手段は、前記在庫充足判定手段により前記第 2 の制約が充足していないと判定された場合には、前記仕掛品在庫を充足させるように前記第 2 のペナルティコストを更新する。

1 5 . 請求項 1 2 記載の多品目多工程ロットサイズスケジユーリング装置において、

前記品目別の 1 次元の最適化問題は、前記第 1 の制約が第 1 のラグランジュ乗数による重み付けにより緩和されると共に前記第 2 の制約が第 2 のラグランジュ乗数による重み付けにより緩和された問題である。

1 6 . 請求項 1 5 記載の多品目多工程ロットサイズスケジユーリング装置において、

を更に具備し、

前記機械干渉制御手段は、前記機械干渉判定手段により前記第 1 の制約が充足していないと判定された場合には、前記機械千渉の程度を小さくするように前記第 1 のラグランジュ乗数を更新し、

前記在庫制御手段は、前記在庫充足判定手段により前記第 2 の制約が充足していないと判定された場合には、前記仕掛品在庫を充足させるように前記第 2 のラグランジュ乗数を更新する。