(57)【特許請求の範囲】
【請求項１】
入力部と演算処理部とを備えるコンピュータにより、マージンのある引当材料の重量を算出する方法であって、
前記入力部から与えられる材料の重量の入力を受け、かつ、二つ以上の注文について各々の注文に対する単重、単重上限、単重下限、マージン上限値、マージン下限値の入力を受けるステップと、
前記演算処理部が入力された前記注文に対して、所定の算出式に基づいて、前記材料を余剰なく引当てることが可能であるかを判断するステップと、
前記材料を余剰なく引当てることが可能であると判断したことに応じて、前記演算処理部が引当材料の重量を算出するステップと、
を含み、
前記判断するステップでは、
入力された前記注文に対して、引当可能な引当量の組み合わせを、ユークリッド空間内の多面体の格子点で表し、前記与えられる材料の重量、前記注文の各々の 前記単重上限、および、前記単重下限とで形成される領域の前記格子点の有無を検出することにより、前記材料を余剰なく引当てることが可能であるかを判断する方法。
【請求項２】
前記判断するステップでの領域とは、前記注文の数が二つであることに応答して、
前記与えられる材料の重量をw、一の注文の前記単重上限をuua、前記単重下限ula、マージン上限値rua、マージン下限値rla、もう一つの注文の前記単重上限をuub、前記単重下限ulb、マージン上限値rub、マージン下限値rlb、ua=uuaまたはula、ub=uubまたはulb、ceil(x)をxの天井関数、floor(x)をxの床関数として、
ua・x+ulb・y≦w、ua・x+uub・y≧w、
ceil(max｛rla,w-rub｝/ua)≦x≦floor(min｛rua,w-rlb｝/ua)
にて形成される領域の格子点の有無を算出することにより、前記与えられる材料を引当可能であるとする、請求項１に記載の方法。
【請求項３】
前記判断するステップでの領域とは、前記注文の数が三つであることに応答して、
前記与えられる材料の重量をw、一の注文の前記単重上限をuua、前記単重下限ula、マージン上限値rua、マージン下限値rla、二の注文の前記単重上限をuub、前記単重下限ulb、マージン上限値rub、マージン下限値rla、三の注文の前記単重上限をuuc、前記単重下限ulc、マージン上限値ruc、マージン下限値rlc、ua=uuaまたはua=ula、ub=uubまたはub=ulb、ceil(x)をxの天井関数、floor(x)をxの床関数、
xl=ceil(rla/ua)、xu=floor(rua/ua)、
yl=ceil(rlb/ub)、yu=floor(rub/ub)、
zl=ceil(rlc/uuc)、zu=floor(ruc/ulc)、
として、
zl≦z≦zuを満たす整数値zそれぞれについて、
ua・x+ub・y≦w-ulc・z、ua・x+ub・y≦w-uuc・z
max{ceil((w-z・uuc-yu・ub)/ua),xl}≦x≦min{floor((w-zu・lc-yl・ub)/ua),xu}、
max{ceil((w-z・uuc-xu・ua)/ub),yl}≦y≦min{floor((w-z・ulc-xl・ua)/ub),yu}
にて形成される領域の格子点の有無を検出することにより、前記与えられる材料を引当可能であるとする、請求項１に記載の方法。
【請求項４】
前記判断するステップでの前記格子点の有無を、二分探索法を用いて検出する請求項1乃至３のいずれかに記載の方法。
【請求項５】
マージンのある引当材料の重量を算出する装置であって、
与えられる材料の重量の入力を受け、かつ、二つ以上の注文について各々の注文に対する単重、単重上限、単重下限、マージン上限値、マージン下限値の入力を受ける入力部と、
入力された前記注文に対して、所定の算出式に基づいて、前記材料を余剰なく引当てることが可能であるかを判断する判断部と、
前記材料を余剰なく引当てることが可能であると判断したことに応じて、引当材料の重量を算出する算出部と、
を含み、
前記判断部は、
入力された前記注文に対して、引当可能な引当量の組み合わせを、ユークリッド空間内の多面体の格子点で表し、前記与えられる材料の重量、前記注文の各々の 前記単重上限、および、前記単重下限とで形成される領域の前記格子点の有無を検出することにより、前記材料を余剰なく引当てることが可能であるかを判断する装置。
【請求項６】
マージンのある引当材料の重量を算出するためのコンピュータ・プログラムであって、入力部と演算処理部とを備えるコンピュータに、
前記入力部により与えられる材料の重量の入力を受け、かつ、二つ以上の注文について各々の注文に対する単重、単重上限、単重下限、マージン上限値、マージン下限値の入力を受けさせるステップと、
入力された前記注文に対して、前記演算処理部により所定の算出式に基づいて、前記材料を余剰なく引当てることが可能であるかを判断させるステップと、
前記材料を余剰なく引当てることが可能であると判断したことに応じて、前記演算処理部により引当材料の重量を算出させるステップと、
を実行させ
前記判断させるステップでは、
入力された前記注文に対して、引当可能な引当量の組み合わせを、ユークリッド空間内の多面体の格子点で表し、前記与えられる材料の重量、前記注文の各々の 前記単重上限、および、前記単重下限とで形成される領域の前記格子点の有無を検出することにより、前記材料を余剰なく引当てることが可能であるかを判断させる、コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、材料引当方法、装置、プログラムに関する。さらに具体的には、材料を注文に応じて余剰なく引当てる計算方法、およびこれを実現する装置、プログラムに関する。
【背景技術】
【０００２】
従来より、顧客からの注文に応じて製品を製造する受注生産の場合、製品素材への注文の引当の際に、製品素材と注文の引当方法を最適化する手法やシステムが知られている。特に、鉄鋼業界においては、顧客からの注文は通常、全体の注文量とは別に各納入製品の重量（単重）がそれぞれマージンをもって指定されて行われることが多く、このような注文方法に対して材料の引当の最適化を試みる手法が提案されている。
【０００３】
例えば、特許文献１には、最終工程における製品の採取の際に単重外れが生じないような材料単位編成、及び注文製品の採取ができる生産管理システムが開示されている。また、特許文献２には、複数種類の製品の注文および複数種類の余剰素材を予め特性に基づいてそれぞれグルーピングし、グループ単位に特性を基準に引当の可否を判定する方法などが開示されている。
【特許文献１】特開平５−１９８０９号公報
【特許文献２】特開平６−１４９８５０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
鉄鋼業界においては、一つの材料は、通常、小さく切断して、数個の注文に引当てる（図２に、一つの材料を三つの注文へ切り分けて引当てた例を示す）。各注文には、注文量とその上下のマージン（引当量の許容範囲）、そして、単重上下限が設定されている。材料は、各注文に対して、単重上下限の範囲内の大きさに切断し、引当量が許容範囲におさまるように引当てる。この際、材料に余剰（どの注文にも引当てられなかった余り）が出ないように引当てることが課題である。
【０００５】
製鋼所では、原則として、顧客からの注文に応じて材料（スラブ・コイル等）を生産するため、各生産工程において注文と材料は関連付いた状態が保持されている。しかし、材料が各工程を通過するうちに、様々な原因により、注文と材料の関係が崩れることがある。こうした場合に、注文に関連付いていない材料を改めて注文に引当て直すシステムのことを材料引当システムという。
【０００６】
材料引当システムでは、基本的には、注文量に合わせて材料を引当てる。例えば、１５ｔの注文に対して１０ｔの材料が二つあれば、１０ｔの材料一つを引当て、もう一つの１０ｔの材料は５ｔだけ切断して引当てる。ただし、注文には、引当てる材料ひとつひとつの重量の上下限である、単重上限と単重下限が設定されている。そのため、材料を引当てる際には、この単重の範囲内に収まるように材料を切断して引当なければならない。
【０００７】
例えば、１４ｔの注文に単重制限４ｔ〜６ｔという制限がある場合、１０ｔの材料を一つと４ｔの材料を一つ用いて引当てることは可能であるが（１０ｔの材料は、５ｔずつ二つに切断すれば単重制限を満たすので引当可能）、７ｔの材料二つのみを用いて１４ｔの注文を満たすことはできない（７ｔの材料は、どのように切断して引当も余剰無く引当てることはできず、１４ｔに届かない）。単重制限があるため、材料を注文量と同じになるように引当ていくと、材料には小さな余剰（およそ５ｔ未満）が多数発生してしまう。小さな余剰は廃棄される公算が高く、製鋼所にとっては損失になるため、注文には一定のマージンが設けられており、余剰が発生しない場合に限り、注文量の上下限の範囲内で注文への総引当量を調整することが許されている。逆に、注文量に合わせて引当てると小さな余剰が発生するときは、注文のマージンを使って余剰が発生しないように引当てることが望まれる。
【０００８】
以上のような条件のもとで、どの材料をどの注文に引当てるかについて最適化を行うのが、材料引当システムの最適化である。各材料は均質ではなく、個々の材料と注文の組み合わせについて、望ましい組み合わせやそうでない組み合わせがあるため、引当量を注文量に合わせるだけではなく、様々な引当の組み合わせを調べて最適な引当を探索する必要がある。しかし、たとえ組み合わせの候補となる注文と材料が数個程度ずつであったとしても、可能な引当方法は膨大な数があり、全ての可能性を網羅して最適な引当方法を求めるのは現実的ではない。キログラム単位で与えられる注文量や単重上下限について、１キログラムずつ引当量を変えながら全ての場合を調べつくすのは計算時間の面で困難だからである。
【０００９】
そのため、何らかの経験則を用いて調べる引当の候補を限定することになる。実用上は、引当は原則として注文量に合わせて行うこととし、余剰が発生するケースについては例外的に対応する方法で、解決することが多い。つまり、原則として注文量にあわせて引当を行い、小さな余剰が発生する場合にのみ注文量のマージンを調べ、余剰の大きさがマージンの範囲内に入っていればマージンを利用して余剰を無くすアルゴリズムである。例えば、５ｔの注文が一つ、６ｔの注文が一つ、１２ｔの材料が一つあるとき、まず材料を５ｔだけ切断して一方の注文に引当て、残り７ｔをもう一方の注文に引当てることを考える。このとき、注文に１ｔ以上のマージンが設定されていれば、注文量の６ｔではなく７ｔを引当てることによって、余剰の発生を無くす。
【００１０】
しかし、このような解決方法では、余剰を無くす引当が可能な場合でも、余剰を発生させてしまうことがある。例えば、１１ｔの材料と、５ｔの注文が二つある場合を考える。二つの注文がともに、引当量上下限は４．５ｔ〜５．５ｔ、単重上下限は２．７ｔ〜５．１ｔとされているとする。このとき、上記解決方法では、まず一つの注文に５ｔで引当を行い、次に、残りの６ｔの材料を５ｔの注文に引当てることを試みる。しかし、この場合、マージンが足りないので（上記アルゴリズムを適用した場合は）余剰を発生させてしまうことになる。ただし、実際には、二つの注文に５．５ｔずつ引当を行えば余剰無く引当てることができる。
【００１１】
そこで、材料を余剰無く引当てることができる場合には、そのような引当て方も探索候補に追加するのが自然な考え方である。ところが、単重制限のもとでは、一つの材料を複数の注文に余剰無く引当てることができるかどうかを判定する問題は困難であり、効率的なアルゴリズムは知られていない。ただ、通常、一つの材料は多くとも三つ程度の注文にしか引当てられないので、注文の数を限定すれば問題の困難さは低減するが、それでも、余剰を無くす引当ができるかどうかを効率的に判定することは簡単な問題ではない。
【００１２】
本発明で解決しようとする課題は、この余剰を無くす引当ができるかどうかを判定し、引当可能な場合は、その引当てる方法を提供することである。上記で述べたように、余剰が出ない引当を探す処理は、膨大な数の回数が実行されることが想定される。そのため、十分に高速なアルゴリズムであることが必要である。
【課題を解決するための手段】
【００１３】
マージンのある引当材料の重量を算出する方法において、与えられる材料の重量の入力を受け、かつ、各々の注文に対する単重、単重上限、単重下限、マージン上限値、マージン下限値の入力を受けるステップと、入力された注文に対して、所定の算出式に基づいて、材料を余剰なく引当てることが可能であるかを判断するステップと、材料を余剰なく引当てることが可能であると判断したことに応じて、引当て材料の重量を算出するステップと、を含む方法、およびその方法を実現する装置、プログラムを提供する。
【００１４】
前記の判断するステップでは、注文の数が一つである場合、材料の重量を単重下限で除算した商を超えない最大の整数と、単重上限との積が、材料の重量以上の重量であるとする算出式に基づいて判断する。
【００１５】
また、前記の判断するステップでは、注文の数が複数の場合、入力された注文に対して、与えられる材料の重量、注文の各々の単重上限、単重下限に基づいて、引当が可能な引当量の組み合わせを、ユークリッド空間領域の格子点で表し、この格子点の有無を検出することにより、材料を余剰なく引当てることが可能であるかを判断する。
【発明の効果】
【００１６】
上記発明によれば、余剰を無くす引当が存在するか否かを判定し、存在する場合は、その引当を提供する高速な処理を実現することができる。処理の高速性は、注文が一つの場合では、一つの不等式で判定することができるようになったことによる。注文が複数の場合では、二分探索などの手法を組み合わせて実現したことで、早く確実に余剰を無くす引当ができるかどうかを実用的な時間で判定することができるようになったことによる。
【発明を実施するための最良の形態】
【００１７】
以下、発明の実施形態を通じて本発明を説明する。なお、以下の実施形態は特許請求の範囲にかかる発明を限定するものではない。また、実施形態の中で説明されている構成要素の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【００１８】
図１は、上記機能を備えた材料引当装置１００の概略図である。材料引当装置１００は、ユーザからの入力を受け付ける入力部１１０、演算処理を行う実行部１１５、アルゴリズム記憶部１３０、関数記憶部１４０、および出力部１７０で構成される。
【００１９】
入力部１１０は、キーボードやマウスなど人間からの操作を受け付ける入力装置の他、他のプログラムなどの出力を入力データとして受け取る装置であってもよい。また、通信機能を備え、遠隔地の他のシステムからデータを受信してもよい。入力部１１０を介して、実行部１１５には、材料の重量、注文の数、各注文ごとの注文量の上限値、注文量の下限値、単重の上限値、単重の下限値が与えられる。
【００２０】
実行部１１５は、注文の数によって適用されるアルゴリズムを選択するアルゴリズム選択部１２０、選択されたアルゴリズムの実行結果によって、材料が余剰なく引当可能かどうかを判断する引当判断部１５０、引当られた材料の重量を算出する重量算出部１６０によって構成される。実行部１１５は、入力部１１０から与えられた入力によって材料が各注文に対して余剰なく
引当可能かどうかの判断、および引当可能な場合はその引当量を各注文ごとに計算する。
【００２１】
アルゴリズム記憶部１３０は、注文の数によって選択される複数のアルゴリズムを記憶する。また、各アルゴリズムは、演算を行うために必要な一または複数の関数を呼び出すために関数記憶部１４０と接続される。各アルゴリズムと関数は、後述するように、それぞれ再帰的に呼び出されることが可能である。
【００２２】
出力部１７０は、実行部１１５によって得られた結果、すなわち、余剰なく引当が可能かどうかの判断、引当が可能と判断された場合は、各注文に対する引当重量の計算結果を表示する。出力部１７０は、実行部１１５の結果を出力する機能を備え、ＣＲＴや液晶ディスプレーなどの表示装置であってよく、また、他のシステムやプログラムにデータを受け渡す通信部であってもよい。
【００２３】
本発明の実施形態では、一つの材料を、余剰が出ないように複数個の注文に引当てることが可能な場合、その引当のパターンは少数のパターンに限定できるので、全てのパターンについて余剰が出ない引当が存在するかどうかを判定する。個々の引当パターンについて、余剰が出ない引当の探索は、以下の二つのアルゴリズムを組み合わせて実現した。一つは、ある一つの注文への引当量が、その注文の単重制限を満たすか否かを高速に判定するアルゴリズム。もう一つは、複数の注文に一つの材料を引当てるとき、引当が可能な引当量の組み合わせをユークリッド空間（実施形態では二次元平面上）の多面体内（面上を含む）の格子点で表現し、その多面体内の格子点を高速に見つけるアルゴリズム。多面体内の格子点を見つけるアルゴリズムは、２次元平面にマップした三角形内の格子点の数を高速に数えるアルゴリズムと二分探索法を用いて実現した。以下、これらのアルゴリズムについて詳しく説明する。
【００２４】
[解くべき問題]
以下、簡単のため注文数は１〜３の場合で説明するが、本発明に係る手法は、注文数が４以上の場合でも拡張が可能である。
入力：  注文の数n(1≦n≦3)が与えられ、各注文Oi(1≦i≦n)について、以下の制限が与えられる。
１）注文量の上限rui
２）注文量の下限rli
３）単重の上限uui
４）単重の下限uli
材料については、材料の重さwが与えられる。
出力：  制約条件を満たす、各注文Oi(1≦i≦n)への引当量AQi。制約条件を満たさない場合は、その旨を出力する。
制約条件：  各注文Oi(1≦i≦n)への引当量AQiは、以下の制約を満たす必要がある。
１）rli≦AQi≦rui（引当量の制約）
２）ある整数kiが存在して、uli・ki≦AQi≦uui・ki（単重制限）
３）w=AQ1+AQ2+・・・+AQn  (余剰はゼロでなければならない)
【００２５】
[アルゴリズム]
以上の制約条件を解くために注文の数に応じて、適用するアルゴリズムが異なる。注文の数が一つのときは後述のアルゴリズム１を適用し、注文の数が二つのときは後述するアルゴリズム２を適用し、注文の数が三つのときは後述のアルゴリズム３を適用する。また、注文の数によらず共通に使用する関数を以下に記述する。
【００２６】
[注文数によらない関数]
＜床関数、天井関数＞
以降、実数xについて、floor(x)(床関数)は、xを超えない最大の整数、ceil(x)（天井関数）はxを下回らない最小の整数と定義する。また、図中では、簡単化のため、
【数１】
0004636609.tif 000002
と表記する。
【００２７】
＜関数１(Oi,w)＞
入力:  注文Oiと引当可能な材料の重量w
if  w≦floor(w/uli)・uui  then  注文Oiに引当量wで引当可能と判定
else
余剰を無くす引当は不可能と判定
図１１に関数１のアルゴリズムのフローチャートを示す。
【００２８】
＜関数２(Oa,Ob,a,b,c,xu,xl)＞
入力：  注文Oa,Obと整数a,b,c、および実数xu,xl
拡張ユークリッド互除法を用いてa,bの最大公約数dと、ax0+by0=dを満たす整数x0,y0を求める
if  cがdで割り切れる、かつ、ceil((xl-(c/d)x0)・(d/b))≦floor（(xu-(c/ｄ)x0)・(d/b)）  then
注文Oaに引当量a((c/d)x0+(b/d)ceil（(xl-(c/d)x0)・(d/b)）)
注文Obに引当量c-a((c/d)x0+(b/d)ceil((xl-(c/d)x0)・(d/b)))
で引当可能と判定する
else
余剰を無くす引当は不可能と判定
図１２に関数２のアルゴリズムのフローチャートを示す。
【００２９】
＜関数countT(a,b,m)＞
if  m<0  then  return  0
if  a<b  then  return  countT(b,a,m)
p=floor(m/a)とおく。
if  a=b  then  return  p(p-1)/2
k=floor((a-1)/b)とおく。
q=floor((c-ap)/q)とおく。
return  countT(a-bk,b,c-b(kp+q))+kp(p-1)/2+pq
図１３に関数countTのアルゴリズムのフローチャートを示す。
【００３０】
[注文が一つの場合のアルゴリズム]
＜アルゴリズム１(Oi,w)＞
入力:  注文Oiと引当可能な材料の重量w
if  rli≦w≦rui  then
関数１(Oi,w)の判定結果をそのまま返す
else
余剰を無くす引当は不可能と判定
図３にアルゴリズム１のフローチャートを示す。
【００３１】
以下、前述のアルゴリズムが正しく動作することを示す。アルゴリズムの正しさを示すために、後述で示される補題を利用している。アルゴリズム１では、まず、材料の重量が注文Oiの引当量が注文量の上下限内に入っているかどうかをチェックしている。注文量の上下限内に入っているときは、次に、単重の制約を満たすかどうかを判定する必要がある。引当量xが単重制約を満たすということは、単重上限uuと単重下限ulについて、ある正の整数nを用いてn・ul≦x≦n・uuと書き表せることにほかならない。これは、補題１より、x≦floor(x/ul)・uuの関係を満たすことと同値である。アルゴリズム１では、関数１を用いて、その判定をしている。引当量が注文量の上下限内に入っているかどうかと単重制約を満たしているかどうかを正しくチェックしているので、アルゴリズム１は、正しく動作することがわかる。
【００３２】
[注文が二つの場合のアルゴリズム]
＜アルゴリズム２(Oi,Oj,w)＞
入力:注文Oi,Ojと引当可能な材料の重量w
if  関数１(Oi,rui)=引当可能、かつアルゴリズム１(Oj,w-rui)=引当可能  then
注文Oiに引当量rui、注文Ojに引当量w-ruiで引当可能と判定
else  if  関数１(Oi,rli)=引当可能、かつアルゴリズム１(Oj,w-rli)=引当可能  then
注文Oiに引当量rli、注文Ojに引当量w-rliで引当可能と判定
else  if  関数１(Oj,ruj)=引当可能、かつアルゴリズム１(Oi,w-ruj)=引当可能  then
注文Ojに引当量ruj、注文Oiに引当量w-rujで引当可能と判定
else  if  関数１(Oj,rlj)=引当可能、かつアルゴリズム１(Oi,w-rlj)=引当可能  then
注文Ojに引当量rlj、注文Oiに引当量w-rljで引当可能と判定
else  if  関数３(O1,O2,w,uu1)=引当可能、または関数３(O1,O2,w,ul1)=引当可能  then
関数３の判定結果を用いて引当可能と判定
else  if  関数３(O2,O1,w,uu2)=引当可能、または関数３(O2,O1,w,ul2)=引当可能  then
関数３の判定結果を用いて引当可能と判定
else
余剰を無くす引当は不可能と判定
図４〜６にアルゴリズム２のフローチャートを示す。
【００３３】
＜関数３(Oa,Ob,w,ua)＞
入力:  材料の重量wと、注文Oa,Ob、注文Oaの単重上下限の一方をua
xl=ceil(max{rla,w-rub}/ua)とおく
xu=floor(min{rua,w-rlb}/uaとおく
if  xl>xu  then
余剰を無くす引当は不可能と判定
else  if  ceil((w-xl・ua)/uub)≦floor((w-xl・ua)/ulb)  then
注文Oaに引当量xl・ua、注文Obに引当量w-xl・uaで引当可能と判定
else  if  ceil((w-xu・ua)/uub)≦floor((w-xu・ua)/ulb)  then
注文Oaに引当量xu・ua、注文Obに引当量w-xu・uaで引当可能と判定
else  if  関数２(Oa,Ob,ua,ulb,w,xu,xl)=引当可能  then
関数２の引当を用いて引当可能と判定する
else  if  関数２(Oa,Ob,ua,uub,w,xu,xl)=引当可能  then
関数２の引当を用いて引当可能と判定する
else
関数４(Oa,Ob,w,ua,xu,xl)の判定をそのまま返す
図１４に関数３のフローチャートを示す。
【００３４】
＜関数４(Oa,Ob,w,ua,xu,xl)＞
入力:  材料の重量wと、注文Oaの単重（上限もしくは下限）uaと、二分探索する範囲xl≦x≦xu
if  xu-xl<2  then  余剰を無くす引当は不可能と判定
else
xp=floor((xl+xu)/2)とおく
if  ceil((w-xp・ua)/uub)≦floor((w-xp・ua)/ulb)  then
注文Oaに引当量xp・ua、注文Obに引当量w-xp・uaで引当可能と判定
else
kp=countT(ua,ulb,w-ua・xp)-countT(ua,uub,w-ua・xp)
ku=countT(ua,ulb,w-ua・xu)-countT(ua,uub,w-ua・xu)
kl=countT(ua,ulb,w-ua・xl)-countT(ua,uub,w-ua・xl)
if  kp-ku>0  then  関数４(Oa,Ob,w,ua,xu,xp)の判定をそのまま返す
else  if  kl-kp>0  then  関数４(Oa,Ob,w,ua,xp,xl)の判定をそのまま返す
else
余剰を無くす引当は不可能と判定
図１５に関数４のアルゴリズムのフローチャートを示す。
【００３５】
以下、注文が二つの場合のアルゴリズムについて説明する。補題２（後述）より、もし余剰を無くす引当が可能ならば、一つの引当を除いて他の全ての引当の引当量が、単重上下限いずれかの倍数、もしくは、引当量の上下限に一致するような引当をつくることができる。よって、一つの引当を除いて、残りの全ての引当の引当量は単重上下限いずれかの倍数、もしくは、引当量の上下限に一致する引当を求めることを考える。
【００３６】
アルゴリズム２では、まず、一つの引当が注文量の上下限の一方に一致するケースを処理する。一つの注文への引当量を注文量の上下限の一方に一致させると、他方の注文について余剰を無くす引当ができるかどうかは、アルゴリズム１を用いて判定できるからである。
【００３７】
次に、一つの引当が単重上下限の一方の倍数に一致するケースを処理する。二つの注文について、単重上下限それぞれについて調べるため、関数３を最大４(=２×２)回呼び出して全ての可能性を調べる。関数３は、注文Oaの引当量を単重uaの倍数に限定して、余剰を無くす引当ができるかどうかを判定する。
【００３８】
関数３では、まず、Oaの引当量の上下限を求めている。Oaに単重uaのx倍で引当てる場合、max{rla,w-rub}≦ua・x≦min{rua,w-rlb}を満たす必要がある（逆に、この不等式を満たせば、Obに引当量w-ua・xで引当てることができることにも注意）。これより、max{rla,w-rub}/ua≦x≦min{rua,w-rlb}/ua。xl=ceil(max{rla,w-rub}/ua),xu=floor(min{rua,w-rlb}/ua)とおくと、xl>xuのとき、上記不等式を満たす整数xは存在しないので、余剰を無くす引当はないと判断する。
【００３９】
図２２は、注文が二つのときの領域と格子点を表す図である。xl≦x≦xuを満たす整数xが存在するとき、余剰を無くす引当ができるのは、x-y平面上の四つの直線x=xl,  x=xu,  P:ua・x+ulb・y=w,  Q:ua・x+uub・y=wに囲まれる領域（図２２の領域ADFC）に（直線上を含め）格子点が存在することと同値である。（格子点(x′,y′)が存在すれば、Oaに引当量ua・x′,Obに引当量w-ua・x′で引当てることができる。）直線x=xlと直線ua・x+ulb・y=w,  ua・x+uub・y=wとの交点は、それぞれ(xl,(w-ua・xl)/ulb),  (xl,(w-ua・xl)/uub)なので、floor((w-ua・xl)/ulb)≧ceil((w-ua・xl)/uub)を満たすとき、直線x=xl上に格子点が存在する。このとき、注文Oaに引当量ua・xl、注文Obに引当量w-ua・xlで引当可能である。同様に、直線x=xu上に格子点があるかどうかも判定できる。
【００４０】
次に、直線P:ua・x+ulb・y=w,  直線Q:ua・x+uub・y=w上に格子点があるかどうかを確認する。補題５より、正しく判定できていることがわかる。残るケースは、領域ADCF内に格子点があるかどうかを判別することである。関数４では、その判別を、領域を分割して二分探索することで実現している。
【００４１】
関数４では、まず、直線x=xlと直線x=xuの中間にある直線x=floor((xl+xu)/2)上に格子点があるかどうかを調べている。この直線上にも格子点がない場合、左右それぞれの領域（領域ADEBと領域BEFC）内の格子点の数を調べ、どちらか一方の領域に格子点が存在すれば、その領域について再帰的に関数４を適用することで格子点を探す。いずれの領域にも格子点が無い場合、余剰を無くす引当は不可能と判断する。
【００４２】
領域内の格子点の数は、補題６（後述）より、関数countTを用いて計算できる。例えば、領域ADEBについては、((△AGJ内の格子点の数)-(△DGJ内の格子点の数))-((△BHJ内の格子点の)-(△EHJ内の格子点の数))で計算できる。関数４では、これを利用して、格子点の数を求めている。
【００４３】
[注文が三つの場合のアルゴリズム]
＜アルゴリズム３(Oi,Oj,Ok,w)＞
入力:注文Oi,Oj,Okと引当可能な材料の重量w
if  関数１(Oi,rli)=引当可能、かつアルゴリズム２(Oj,Ok,w-rli)=引当可能  then
注文Oiに引当量rli、注文Oj,Okは、アルゴリズム２が出力した引当量で引当可能と判定
else  if  関数１(Oj,rlj)=引当可能、かつアルゴリズム２(Oi,Ok,w-rlj)=引当可能  then
注文Ojに引当量rlj、注文Oi,Okは、アルゴリズム２が出力した引当量で引当可能と判定
else  if  関数１(Ok,rlk)=引当可能、かつアルゴリズム２(Oi,Oj,w-rlk)=引当可能  then
注文Okに引当量rlk、注文Oi,Ojは、アルゴリズム２が出力した引当量で引当可能と判定
else  if  関数１(Oi,rui)=引当可能、かつアルゴリズム２(Oj,Ok,w-rui)=引当可能  then
注文Oiに引当量rui、注文Oj,Okは、アルゴリズム２が出力した引当量で引当可能と判定
else  if  関数１(Oj,ruj)=引当可能、かつアルゴリズム２(Oi,Ok,w-ruj)=引当可能  then
注文Ojに引当量ruj、注文Oi,Okは、アルゴリズム２が出力した引当量で引当可能と判定
else  if  関数１(Ok,ruk)=引当可能、かつアルゴリズム２(Oi,Oj,w-ruk)=引当可能  then
注文Okに引当量ruk、注文Oi,Ojは、アルゴリズム２が出力した引当量で引当可能と判定
else  if  関数５(Oi,Oj,Ok,w,uui,uuj)=引当可能、または関数５(Oi,Oj,Ok,w,uli,uuj)=引当可能  then
関数５の判定結果を用いて引当可能と判定
else  if  関数５(Oi,Oj,Ok,w,uui,ulj)=引当可能、または関数５(Oi,Oj,Ok,w,uli,ulj)=引当可能  then
関数５の判定結果を用いて引当可能と判定
else  if  関数５(Oj,Ok,Oi,w,uuj,uuk)=引当可能、または関数５(Oj,Ok,Oi,w,ulj,uuk)=引当可能  then
関数５の判定結果を用いて引当可能と判定
else  if  関数５(Oj,Ok,Oi,w,uuj,ulk)=引当可能、または関数５(Oj,Ok,Oi,w,ulj,ulk)=引当可能  then
関数５の判定結果を用いて引当可能と判定
else  if  関数５(Ok,Oi,Oj,w,uuk,uui)=引当可能、または関数５(Ok,Oi,Oj,w,ulj,uuk)=引当可能  then
関数５の判定結果を用いて引当可能と判定
else  if  関数５(Ok,Oi,Oj,w,uuk,uli)=引当可能、または関数５(Ok,Oi,Oj,w,ulj,ulk)=引当可能  then
関数５の判定結果を用いて引当可能と判定
else
余剰を無くす引当は不可能と判定
図７〜１０にアルゴリズム３のフローチャートを示す。
【００４４】
＜関数５(Oa,Ob,Oc,w,ua,ub)＞
入力:  材料の重量wと、注文Oaの単重（上限もしくは下限）uaと、注文Obの単重（上限もしくは下限）ub
xl=ceil(rla/ua),  xu=floor(rua/ua)とおく
if  xl>xu  then  余剰を無くす引当は不可能と判定する
else
yl=ceil(rlb/ub),  yu=floor(rub/ub)とおく
if  yl>yu  then  余剰を無くす引当は不可能と判定する
else  if  関数１(Oc,w-xl・ua-yl・ub)=引当可能  then
Oaに引当量xl・ua,  Obに引当量yl・ub,  Ocに引当量w-xl・ua-yl・ubで引当可能と判定する
else  if  関数１(Oc,w-xl・ua-yu・ub)=引当可能  then
Oaに引当量xl・ua,  Obに引当量yu・ub,  Ocに引当量w-xl・ua-yl・ubで引当可能と判定する
else  if  関数１(Oc,w-xu・ua-yl・ub)=引当可能  then
Oaに引当量xu・ua,  Obに引当量yl・ub,  Ocに引当量w-xu・ua-yl・ubで引当可能と判定する
else  if  関数１(Oc,w-xu・ua-yu・ub)=引当可能  then
Oaに引当量xu・ua,  Obに引当量yu・ub,  Ocに引当量w-xu・ua-yu・ubで引当可能と判定する
else
zl=ceil(rlc/ulc),  zu=floor(ruc/ulc)とおく
z=zlとおく
while  z≦zu
su=min{floor((w-z・uuc-yl・ub)/ua),xu}とおく
sl=max{ceil((w-z・uuc-yu・ub)/ua),xl}とおく
if  関数２(Oa,Ob,ua,ub,w-z・uuc,su,sl)=引当可能  then
注文Oa,Obに関数２の引当量を用いて引当、注文Ocに引当量w-z・uucで引当可能と判定する
else
tx=max{floor((w-z・ulc-yu・ub)/ua),xl-1}とおく
if  sl≦tx  then
注文Oaに注文量tx・ua、注文Obに注文量yu・ub、注文Ocにw-tx・ua-yu・ubで引当可能と判定する
else
ty=max{floor((w-z・uuc-xu・ua)/ub),yl-1}とおく
if  su=xu、かつ(w-uuc・z-xu・ua)/ub≦ty  then
注文Oaに注文量xu・ua、注文Obに注文量ty・ub、注文Ocにw-xu・ua-ty・ubで引当可能と判定する
else  if  関数６(Oa,Ob,Oc,w,ua,ub,uuc・z,ulc・z)=引当可能  then
関数６の判定をそのまま返す
else
z=z+1
while  end
図１６〜１９に関数５のアルゴリズムのフローチャートを示す。
【００４５】
＜関数６(Oa,Ob,Oc,w,ua,ub,ru,rl)＞
入力:  材料の重量wと、注文Oaの単重（上限もしくは下限）uaと、注文Obの単重（上限もしくは下限）ubと、Ocの引当量の上限ruと下限rl
rp=floor((ru+rl)/2)とおく
su=min{floor((w-rp-yl・ub)/ua),xu}とおく
sl=max{ceil((w-rp-yu・ub)/ua),xl}とおく
if  rpがdで割り切れる、かつ関数２(Oa,Ob,ua,ub,w-rp,su,sl)=引当可能  then
注文Oa,Obに関数２の引当量を用いて引当、注文Ocに引当量w-rpで引当可能と判定する
else
kp=countT(ua,ub,w-rp-xl・ua-yl・ub)-countT(ua,ub,w-rp-xu・ua-yl・ub)-countT(ua,ub,
w-rp-xl・ua-yu・ub)
ku=countT(ua,ub,w-ru-xl・ua-yl・ub)-countT(ua,ub,w-ru-xu・ua-yl・ub)-countT(ua,ub,
w-ru-xl・ua-yu・ub)
kl=countT(ua,ub,w-rl-xl・ua-yl・ub)-countT(ua,ub,w-rl-xu・ua-yl・ub)-countT(ua,ub,
w-rl-xl・ua-yu・ub)
if  kp-ku>0  then
関数６(Oa,Ob,Oc,w,ua,ub,rp,ru)の判定をそのまま返す
else  if  kl-kp>0  then
関数６(Oa,Ob,Oc,w,ua,ub,rl,rp)の判定をそのまま返す
else
余剰を無くす引当は不可能と判定
図２０〜２１に関数６のアルゴリズムのフローチャートを示す。
【００４６】
以下、注文が三つの場合のアルゴリズムについて説明する。注文が二つのときと同様、補題２より、もし余剰を無くす引当が可能ならば、一つの引当を除いて他の全ての引当の引当量が、単重上下限いずれかの倍数、もしくは、引当量の上下限に一致するような引当をつくることができる。よって、一つの引当を除いて、残りの全ての引当の引当量は単重上下限いずれかの倍数、もしくは、引当量の上下限に一致する引当を求めることを考える。
【００４７】
アルゴリズム３では、まず、少なくとも一つの引当が注文量の上下限の一方に一致するケースを処理する。一つの注文への引当量を注文量の上下限の一方に一致させると、残りの注文について余剰を無くす引当ができるかどうかは、アルゴリズム２を用いて判定できるからである。
【００４８】
次に、二つの引当が単重上下限の一方の倍数に一致するケースを処理する。引当量を単重上下限の倍数に一致させない注文の選び方が３通りで、二つの注文について、単重上下限それぞれについて調べるため、関数５を最大１２（＝３×２×２)回呼び出して全ての可能性を調べる。関数５は、注文Oaの引当量を単重uaの倍数、注文Obの引当量を単重ubの倍数に限定して、余剰を無くす引当ができるかどうかを判定する。
【００４９】
関数５では、まず、注文Oaへの引当量をx・ua、注文Obへの引当量をy・ubとしたとき、x,y（ともに整数）の上下限xl≦x≦,yl≦y≦yuを求めている。次に、注文Oaへの引当量をそれぞれxl・ua,xu・uaにしたときと、注文Obへの引当量をそれぞれyl・ub,yu・ubにしたときの４通りについて、余剰を無くすことができるかどうかを関数１を利用して判定している。
【００５０】
そして、整数zを用いて、注文Ocへの引当量をz・ulc以上z・uuc以下の範囲に限定したとき、余剰を無くす引当ができるかどうかについてチェックしている（整数zを、いろいろな値に変更して、全ての場合を網羅している）。図２３は、注文が三つのときの領域と格子点を表す図である。余剰を無くす引当ができるとき、図２３の領域BDFGECの内部（辺上を含む）に格子点が存在する。領域内に格子点があるかどうかは、関数６で判定している。
【００５１】
関数６で行っていることは、注文が二つの場合と同様、格子点の数を数えるアルゴリズムと二分探索を組み合わせである。二分探索時、半分に分ける方法が、直線Pと直線Qに平行な直線に変わっていることを除けば、おおむね関数４と同様の判定をしているだけなので、詳細な説明は省略する。
【００５２】
ここでは、前述アルゴリズムの説明で使用した補題について説明する。
【００５３】
[補題１]
実数x>0,  b≧a>0について、an≦x≦bnを満たす自然数nが存在することは、x≦floor(x/a)・bが成り立つことと同値である。
（証明）
an≦x≦bnを満たす自然数nが存在するとき、an≦xよりn≦x/a。
nは自然数なので、n≦floor(x/a)もまた成り立つ。x≦bnより、x≦floor(x/a)・b。
次に、x≦floor(x/a)・bが成り立つとする。n=floor(x/a)とおくと、an≦a・floor(x/a)≦a・x/a≦x。また、bn≧b・floor(x/a)≧x（最後の不等式は仮定より）。よって、an≦x≦bnが成り立つ。
（証明終）
【００５４】
[補題２]
各注文Oiについて、引当量をpiとすると、単重制約を満たしかつ引当量上下限の範囲内にあるとする。このとき、一つの引当を除いて、他の引当の引当量が全て、単重（上限あるいは下限）の整数倍、もしくは、引当量上下限のいずれかと一致するような引当量p′iを求めることができる。
（証明）
二つの引当がともに、単重上下限の整数倍にも引当量上下限にも一致しないとき、この二つ以外の引当の引当量を変化させずに、二つの引当のうち一つを単重の整数倍あるいは引当量上下限に一致させることができることを示す。この操作を繰り返すことによって、所望の引当が得られることは、容易にわかる。
p1,p2が、単重の整数倍にも引当量上下限にも一致しないとする。ここで、
d1=min{ceil(p1/b1)・b1,  floor(p1/a1)・a1,u1-p1-p1-l1},
d2=min{ceil(p2/b2)・b2,  floor(p2/a2)・a2,u2-p2,p2-l2}
とおく。d1>0,  d2>0であることに注意されたい。
このとき、d1<d2ならば、(p′1,p′2)=(p1-d1,p2+d1)あるいは(p′1,p′2)=(p1+d1,p2-d1)とすると、p′1が単重の整数倍あるいは引当量上下限に一致する。d1≧d2ならば、(p′1,p′2)=(p1-d2,p2+d2)あるいは(p′1,p′2)=(p1+d2,p2-d2)とすると、p′2が単重の整数倍あるいは引当量上下限に一致する。また、いずれの場合も(p′1,p′2)が単重制限・引当量上下限内にあることは容易に確認できる。
（証明終）
【００５５】
[補題３]
整数a,bの最大公約数をd=GCD(a,b)とする。このとき、ax+by=cが解をもつための必要十分条件は、cがdで割り切れることである。解が存在する場合、解の一組を(x,y)=(x0,y0)とすれば、他の任意の解は、以下の式で一般的に与えられる。
x=x0+(b/d)k,  y=y0-(a/d)k
（証明）
前半は、ほぼ自明。aとbはdで割り切れるから、ax+byもdで割り切れる。よって、cはdで割り切れる必要がある。
後半については、まず、a′=a/d,  b′=b/dとおく。a′x+b′y=c/d,  a′x0+b′y0=c/dが成り立つから、a′(x-x0)+b′(y-y0)=0。a′,b′は互いに素なので、整数kを用いてa′(x-x0)=-b′(y-y0)=a′・b′・kと表せる。よって、x=x0+b′・k,  y=y0-a′・k。
（証明終）
【００５６】
[補題４]
正の整数a,bに対してa,bの最大公約数d=GCD(a,b)を求めると同時に、ax+by=dを満たす整数x,yの組x=x0,  y=y0を一組求めるアルゴリズムが存在する（拡張ユークリッド互除法）。計算量は、通常のユークリッドの互除法と同程度で、O(max{log  a,log  b})。
【００５７】
[補題５]
a,b,cは正の整数とする。直線ax+by=c上に格子点(x′,y′)が存在し、かつ、xl≦x′≦xuの関係が満たされていることは、以下の条件(1)と(2)が共に成り立つことと同値である。ただし、a,bの最大公約数をdとする。
(1)  cがdで割り切れる
(2)  ceil((xl-c/d・x0)(d/b))≦floor((xu-c/d・x0)(d/b)
（証明）
補題４より、拡張ユークリッド互除法を用いて、a,bの最大公約数dと、ax0+by0=dを満たす整数x0,y0の組を求めることができる。aとbはdで割り切れるから、ax+byもdで割り切れる。よって、cはdで割り切れる必要がある（(1)が成り立つ）。x=(c/d)x0,y=(c/d)y0は、ax+by=cを満たすから、補題３より、x′=(c/d)x0+(b/d)kと表せる。xl≦x′≦xuであるためには、(xl-(c/d)x0)(d/b)≦k≦(xu-(c/d)x0)(d/b)を満たす整数kが必要である。これより、(2)が成り立つ必要があることがわかる。逆に、(1)と(2)が成り立てば、格子点(x′,y′)が見つけられることは、容易に分かる。
（証明終）
【００５８】
[補題６]
a,bを互いに素な正の整数とする。領域T(a,b,c)={(x,y)∈R2｜ax+by≦c,  x>0,  y>0}に含まれる格子点の数をN(a,b,c)とおく。ここで、R2は２次のユークリッド空間を表す。N(a,b,c)は、O(max{log  a,log  b})時間で計算できる。
【００５９】
（証明）
p=floor(c/a),  q=(c-ap)/bとおく。p=0のとき、明らかにN(a,b,c)=0なので、p>0とする。
三角形T(a,b,c)の面積を、N(a,b,c)を用いて表すことを考える。T(a,b,c)内にある、一辺の長さが１の正方形の数は、N(a,b,c)に等しい。よって、残りの領域について、複数の台形と一つの三角形に分割することを考える（数３を参照）。各0<j≦pについて、台形Sjを以下のように定義する。実数xについて、{x}はx-floor(x)で定義する。
【００６０】
Sj={(x,y)∈R2｜ax+by≦c,  j-1≦x≦j,  y≧floor((c-aj)/b)}
次に、三角形Rを以下のように定義する。
R={(x,y)∈R2｜ax+by≦c,  p≦x,  y≧0}
このとき、三角形T(a,b,c)の面積は以下のように表せる。
【数２】
0004636609.tif 000003
【００６１】
｜T(a,b,c)｜=c2/(2ab)、｜R｜=q(c/a-p)/2が成り立つので、以下の関係が導ける。
【数３】
0004636609.tif 000004
【数４】
0004636609.tif 000005
【００６２】
次に、台形Sjの面積について考える。台形Sjの面積｜Sj｜は、以下のように表せる。
【数５】
0004636609.tif 000006
【００６３】
よって、N(a,b,c)は以下のように表せる。
【数６】
0004636609.tif 000007
【００６４】
二番目の等式は、q=(c-ap)/bの関係から成り立つ。ここで、N(a,b,c)=N(b,a,c)が成り立つので、一般性を失わずにa≧bとする。また、a=bの場合、N(a,b,c)=floor(c/a)(floor(c/a)-1)/2であることは、容易に示せる。よって、a>bの場合について考えれば良い。aがbで割り切れる場合、k=a/b-1、そうでない場合、k=floor(a/b)とおく。c′=c-b(kp+floor(q))とおくと、直線(a-bk)x+by=c′は二点(0,c′/b)と(p,{q})を通る。これより、N(a-bk,b,c′)は以下のように表せる。
【数７】
0004636609.tif 000008
【００６５】
整理して、
【数８】
0004636609.tif 000009
【００６６】
よって、N(a,b,c)は、以下のアルゴリズムで計算可能。
Algorithm  calc(a,b,c)
a,b,c  は  a≧bとなる正の整数
begin
if  (a  mod  b)=0  then  k:=a/b-1;  else  k:=floor(a/b);
p:=floor(c/a);
q:=floor((c-ap)/b);
if  p=0  then
return  0;
else  if  a＝b  then
return  p(p-1)/2;
else
return  calc(b,a-bk,c-b(kp+q))+kp(p-1)/2+pq;
endif
end
【００６７】
アルゴリズムcalcの計算時間は、calcの再帰呼び出し回数に比例する。calcの再帰呼び出し回数は、aとbにユークリッドの互除法を適用したときの再帰呼び出し回数に等しいので、アルゴリズムcalcの計算時間は、O(max{log  a,log  b})。
（証明終）
【００６８】
以下、上記述べた計算方法の具体的実施例を示す。
【００６９】
実施例１：注文量１０．０ｔ（許容範囲８．０ｔ〜１２．０ｔ）、単重制限４．５ｔ〜５．５ｔの注文と１０．０ｔの材料が与えられたとき、アルゴリズム１を適用すると１０．０ｔの材料が引当可能であると判定される。
【００７０】
実施例２：注文量１０．０ｔ（許容範囲８．０ｔ〜１２．０ｔ）、単重制限４．５ｔ〜５．５ｔの注文と８．０ｔの材料が与えられたとき、アルゴリズム１を適用すると、関数１で、８．０≦floor(８．０/４．５)*５．５の関係が満たされないので、８．０ｔの材料を余剰無く引当てることは不可能と判定される。
【００７１】
実施例３：注文量９．０ｔ（許容範囲１．４５ｔ〜１０．０ｔ）、単重制限１．４５ｔ〜１．５５ｔの注文Ａと注文量３．０ｔ（許容範囲２．５ｔ〜３．５ｔ）、単重制限２．５ｔ〜２．９ｔの注文Ｂと１２．０ｔの材料が与えられたとき、アルゴリズム２を適用すると、注文Ａに９．３ｔ、注文Ｂに２．７ｔを引当てることで、余剰無く引当可能であると判定される。
【００７２】
実施例４：注文量９．０ｔ（許容範囲２．５ｔ〜１０．０ｔ）、単重制限１．５ｔ〜１．６ｔの注文Ａと注文量４．０ｔ（許容範囲２．５ｔ〜５．５ｔ）、単重制限１．５５ｔ〜１．７ｔの注文Ｂと１２．０ｔの材料が与えられたとき、アルゴリズム２を適用すると、余剰無く引当てることは不可能と判定される。
【００７３】
実施例５：注文量１．９ｔ（許容範囲１．５ｔ〜５．０ｔ）、単重制限１．５ｔ〜１．９ｔの注文Ａと注文量４．８ｔ（許容範囲２．５ｔ〜５．０ｔ）、単重制限２．５ｔ〜３．０ｔの注文Ｂと注文量４．０ｔ（許容範囲３．５ｔ〜８．０ｔ）、単重制限１．２ｔ〜１．５ｔの注文Ｃと１１．０ｔの材料が与えられたとき、アルゴリズム３を適用すると、注文Ａに１．５ｔ、注文Ｂに５．０ｔ、注文Ｃに４．５ｔを引当てることで、余剰無く引当可能であると判定される。
【００７４】
実施例６：注文量４．３ｔ（許容範囲１．５ｔ〜１０．０ｔ）、単重制限１．５ｔ〜１．９ｔの注文Ａと注文量４．８ｔ（許容範囲４．５ｔ〜９．０ｔ）、単重制限１．５ｔ〜１．７ｔの注文Ｂと注文量４．８ｔ（許容範囲４．５ｔ〜９．０ｔ）、単重制限１．５ｔ〜１．７ｔの注文Ｃと９．０ｔの材料が与えられたとき、アルゴリズム３を適用すると、余剰無く引当てることは不可能と判定される。
【００７５】
上記発明の実施形態によれば、余剰を無くす引当が存在するか否かを判定し、存在する場合は、その引当を提供する高速な処理を実現することができる。処理の高速性は、注文が一つの場合について言えば、一つの不等式で判定することができるようになったことによるものである。従来手法では、通常、単重上限と下限を２倍、３倍していくことで、材料の重量が単重制約を満たす区間に入っているかどうかチェックする必要があった。この部分が高速化したことによって、注文が複数の場合の判定の高速化に寄与したばかりではなく、ある引当が単重制限を満たすかどうかを判定する部分等、材料引当プログラム全体の高速化にも大きく貢献する。注文が複数の場合について言えば、二分探索などの手法を組み合わせて実現したことで、早く確実に余剰を無くす引当ができるかどうかを実用的な時間で判定することができるようになる。
【００７６】
以上、本発明を実施形態、具体例を用いて説明したが、本発明の技術的範囲は上記実施形態に記載の範囲に限定されない。上記実施形態に、多様な変更または改良を加えることができる。そのような変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。また、上記実施例からも理解されるように、本発明の方法および装置は重量の大小に関係なく適用可能である。例えば材料の重量に単重制約のあるお菓子や、小材料の引当てにも本願本質を逸脱することはなく適用可能である。
【００７７】
本発明は、一つの実施形態として、材料引当装置１００(図１)上のコンピュータ・プログラムによって実現可能である。上記プログラムを格納する記憶媒体は、電子的、磁気的、光学的、電磁的、赤外線または半導体システム（または、装置または機器）あるいは伝搬媒体であることができる。コンピュータ可読の媒体の例には、半導体またはソリッド・ステート記憶装置、磁気デープ、取り外し可能なコンピュータ可読の媒体の例には、半導体またはソリッド・ステート記憶装置、磁気テープ、取り外し可能なコンピュータ・ディスケット、ランダム・アクセス・メモリ（RAM）、リードオンリー・メモリ(ROM)、リジッド磁気ディスクおよび光ディスクが含まれる。現時点における光ディスクの例には、コンパクト・ディスク−リードオンリー・メモリ(CD-ROM)、コンパクト・ディスク−リード／ライト(CD-R/W)およびDVDが含まれる。
【図面の簡単な説明】
【００７８】
【図１】材料引当装置概略図である。
【図２】一つの材料を三つの注文へ切り分けて引当てた例である。
【図３】アルゴリズム１のフローチャートである。
【図４】アルゴリズム２のフローチャート（１／３）である。
【図５】アルゴリズム２のフローチャート（２／３）である。
【図６】アルゴリズム２のフローチャート（３／３）である。
【図７】アルゴリズム３のフローチャート（１／４）である。
【図８】アルゴリズム３のフローチャート（２／４）である。
【図９】アルゴリズム３のフローチャート（３／４）である。
【図１０】アルゴリズム３のフローチャート（４／４）である。
【図１１】関数１のフローチャートである。
【図１２】関数２のフローチャートである。
【図１３】関数countTのフローチャートである。
【図１４】関数３のフローチャートである。
【図１５】関数４のフローチャートである。
【図１６】関数５のフローチャート（１／４）である。
【図１７】関数５のフローチャート（２／４）である。
【図１８】関数５のフローチャート（３／４）である。
【図１９】関数５のフローチャート（４／４）である。
【図２０】関数６のフローチャート（１／２）である。
【図２１】関数６のフローチャート（２／２）である。
【図２２】注文が二つのときの領域と格子点を表す図である。
【図２３】注文が三つのときの領域と格子点を表す図である。
【符号の説明】
【００７９】
１００  材料引当装置
１１０  入力部
１１５  実行部
１２０  アルゴリズム選択部
１３０  アルゴリズム記憶部
１４０  関数記憶部
１５０  引当判断部
１６０  重量算出部
１７０  出力部
【図１】
0004636609.tif 000010
【図２】
0004636609.tif 000011
【図３】
0004636609.tif 000012
【図４】
0004636609.tif 000013
【図５】
0004636609.tif 000014
【図６】
0004636609.tif 000015
【図７】
0004636609.tif 000016
【図８】
0004636609.tif 000017
【図９】
0004636609.tif 000018
【図１０】
0004636609.tif 000019
【図１１】
0004636609.tif 000020
【図１２】
0004636609.tif 000021
【図１３】
0004636609.tif 000022
【図１４】
0004636609.tif 000023
【図１５】
0004636609.tif 000024
【図１６】
0004636609.tif 000025
【図１７】
0004636609.tif 000026
【図１８】
0004636609.tif 000027
【図１９】
0004636609.tif 000028
【図２０】
0004636609.tif 000029
【図２１】
0004636609.tif 000030
【図２２】
0004636609.tif 000031
【図２３】
0004636609.tif 000032