平成１０年度第７回KSMAP

日時：３月２６日（金）　１５：００〜

場所：京都大学 工学部７号館(建築) ４階 第一講義室


          京都大学へのアクセス

講演題目と講演者

 「段取り替え数の最小化を目的とするカッティングストック問題について」
  ○ 梅谷 俊治 (京都大学大学院情報学研究科数理工学専攻)

 「相補性問題に対する平滑化法と内点法」
  ○ 吉瀬 章子 (筑波大学社会工学系)

講演要旨：

● 段取り替え数の最小化を目的とするカッティングストック問題について

カッティングストック問題とは, 定型の母材料(ストック)から, 顧客の注文に応じて様々な大きさの製品を切り出す問題であり, 切り出しにかかる費用の最小化を目的とする. 本問題は, 鉄鋼, 製紙, 繊維業を始めとする多くの分野に応用があり, 切り出す製品の形状や材質, 切り出しを行う機械等の制約, 切り出しに関わる諸経費のバランスにより, 様々なバリエーションが存在する. これまでの研究では, ストック材料費の最小化を目的とするカッティングストック問題が多く取り上げられてきた. しかし, 製造業におけるストック等の材料費の低下に伴い, ストック材料費の最小化を行う従来のアルゴリズムでは, 現実の問題に十分に対処できない場合が増加している. 特に, 鉄鋼など切り出し機械の段取り替え作業に多くの時間と労力を必要とする業種では, ストックの切り残しを減らすよりも, むしろ, 切り出しに伴って起こる段取り替えの回数を減らすことで, 経費を大きく削減できる. この観点から, 本研究では, 製品の過不足を一定範囲内に抑えるという制約のもとで, 段取り替え数を最小化する１次元カッティングストック問題を取り上げる. 本発表で提案するアルゴリズムでは, 段取り替え数を一時的に固定した上で, 制約を満たす解を局所探索法を用いて探索する. また, 近傍の評価回数を削減する手法を用い, アルゴリズムの高速化を実現している. なお, 化学繊維業における実問題をもとに計算機実験を行い, 本アルゴリズムが少ない段取り替え数の解を短時間で探索できることを確かめた.

● 相補性問題に対する平滑化法と内点法

相補性問題に対する平滑化法、とりわけChen-Harkar-Kanzow-Smale 関数とと呼ばれる平滑化関数を用いた解法と、内点法について、堀田、稲葉、吉瀬の共同研究をもとに、パスの性質、収束性、計算の手間の導出方法等を比較し、それらの関係について述べる。また、計算機実験の結果についても報告する。

１８名の参加がありました．参加していただいた方々，どうもありがとうございました．

柳浦睦憲(yagiura@kuamp.kyoto-u.ac.jp)

<最終更新作成日時 1999年3月26日 >