日本オペレーションズ・リサーチ学会
第3回関西支部講演会

	基礎概念，代表的手法，理論結果の総括，最近の動向，
	事例への適用例，実装上のノウハウ

	日時：２００６年１１月１８日（土）１３：００〜１７：００

１３：００〜１３：５５ 「いま一度ジョンソン法 －スケジューリング理論入門に代えて－」
軽野 義行 氏（京都工芸繊維大学工芸科学研究科）

今さらジョンソン法？と思われる向きも多いかもしれない．ジョンソン法は1954年に発表された２機械フローショップ・スケジューリング問題を厳密に解く多項式時間アルゴリズムである．２機械フローショップ問題に課された前提条件から，あたかもジョンソン法は実際には役に立たないと言わんばかりの記述が，生産システムの教科書にしばしば見られる．正直に言えば，昔の研究はのんびりした感じがして羨ましいな，と私自身も思っていた．しかし，最近，スケジューリング問題に対する近似アルゴリズムの研究を通して，これまで知られていなかったジョンソン・スケジュールの興味深い特徴が明らかにされつつある．これらの結果を眺めていると，役に立たないのではなく，うまく活用する十分な力がまだ我々についていないだけのような気がしてくる．

温故知新．この講演では，スケジューリング問題に対する離散アルゴリズムの基礎事項について，ジョンソン法を中心に説明する．

１３：５５〜１４：５０ 「割当型問題に対する汎用解法構築の試み」
柳浦 睦憲 氏（名古屋大学情報科学研究科）

n 個の仕事を m 個のエージェントに割り当てるとき，各エージェントの資源制約を満たしつつ割当に伴う総コストの最小化を図る問題は，一般化割当問題と呼ばれ，代表的な組合せ最適化問題のひとつとして古くから研究されてきました．問題の基本構造がこの様な割当であるような問題は世の中に多数存在し，その重要性は今更言うまでもありません．たとえば，並列機械スケジューリング問題や配送計画問題などは，解の基本構造が「割当 ＋ 順序付け」であることから，広い意味で割当型問題の一種と捉えることができます(順序付けの部分をオラクルが計算してコストを返してくれると考えます)．

一般化割当問題に対しては，メタ戦略に基づく効率的な解法の開発に成功しましたが，その経験を生かし，より一般的な種々の割当型問題に対する汎用解法を構築すべく研究を進めています．本講演ではその一端を紹介します．

１５：０５〜１６：００ 「モデリング　－スケジューリング問題の捉え方－」
池上 敦子 氏（成蹊大学 理工学部）

スケジューリング問題は，一般に，なんらかの資源（人，機械，車，部屋，競技場，時間，等々）を，なんらかの需要（看護，介護，製造，運搬，授業，試合，等々）に割り当てる問題だと考えます．例えば，ナース・スケジューリングでは，各日の各シフトはナースを必要とし，ナースがそこに資源として割当てられますが，看護の質を守るための「シフト側の都合」と「ナース側の都合」の両方を考慮する問題となっています．一見，トレードオフの関係にあるような2組の「都合（制約や要望）」のそれぞれを高いレベルで達成し，そのバランスを考えなければなりません．モデリングにおいての「真の目的（ナース・スケジューリングでは看護の質を守ること）」と「資源側からの制約や要望」「需要側からの制約や要望」との関係，そして，モデリング＝問題把握の難しさについて，これまで扱ってきた問題をベースに述べさせて頂きたいと思います．

１６：００〜１６：５５ 「スケジューリング最適化ソルバ」
野々部 宏司 氏（法政大学工学部）

世の中に見られるさまざまな離散最適化問題を，包括的に，そして（非常に曖昧な表現ですが）実用的に解決することのできる最適化ソルバがあるとすれば，その有用性は計り知れません．残念ながら，現時点でそのような巧い方法を見い出すことはあまり期待できませんが，対象とする問題タイプをある程度限定すれば，質の高い解を実用的な計算時間で求めることは可能かも知れません．そして，「適用範囲の広さ」と「アルゴリズムの性能」という相反する指標をバランスよく考慮して開発した最適化ソルバは，実用上，十分有用になり得ると考えます．

この思想のもと，これまでに，制約充足問題や資源制約スケジューリング問題に対して，メタヒューリスティクスと呼ばれる手法を用いた最適化アルゴリズムを開発してきました．これらは，実際のスケジューリングシステムに組み込まれるなど，一定の成果を得ています．この講演では，これらのソルバの解説と，スケジューリング問題への適用例について説明する予定です．

	委員長　　永持　仁 （京都大学）
	副委員長　吉冨 康成（京都府立大学）
		　宇野 裕之（大阪府立大学）
		　増山 博之（京都大学）

	一般 ３，０００円（講演資料・懇親会を含む）
	学生 無料（懇親会は含まない）

	場所：芝蘭会館本館 山内ホール (80名収容）

	懇親会：芝蘭会館別館 研修室1 18:00-20:00

	永持　仁
	〒606-8164 京都市左京区吉田本町
	京都大学情報学研究科数理工学専攻離散数理分野
	TEL/FAX: 075-753-4920
	nag \at amp \dot i \dot kyoto-u \dot ac \dot jp

軽野 義行 氏（京都工芸繊維大学 工芸科学研究科）

	Email: karuno \at kit \dot ac \dot jp

	経歴：
	1966年北海道生まれ，
	1992年京都工芸繊維大学大学院博士前期課程修了，
	1993年京都大学大学院博士後期課程中退，
	京都工芸繊維大学工芸学部助手，同助教授を経て，
	現在，京都工芸繊維大学大学院工芸科学研究科助教授．
	博士(情報学）．

	興味ある研究分野：
	スケジューリング問題に対する近似アルゴリズム．

柳浦 睦憲 氏（名古屋大学 情報科学研究科）

	E-mail: yagiura \at nagoya-u \dot jp

	経歴：
	1968年島根県生まれ，
	1993年京都大学大学院修士課程修了，
	同博士後期課程進学後，
	1994年京都大学助手，講師を経て，
	現在名古屋大学助教授．
	博士(工学)．

	興味ある研究分野：
	組合せ最適化問題に対するメタ戦略．

	著書：
	「組合せ最適化 ─ メタ戦略を中心として」朝倉書店．

	受賞など：
	2005年日本OR学会文献賞
	2006年スケジューリング学会賞（学術賞）

池上 敦子 氏（成蹊大学 理工学部）

	Email: atsuko \at st \dot seikei \dot ac \dot jp
	URL: http://cleo.is.seikei.ac.jp/~atsuko/

	経歴：
	東京生まれ,
	立教大学数学科卒業後，成蹊大学工学部/理工学部助手，
	2001年 博士学位取得を経て，
	2006年 成蹊大学講師．

	興味ある研究分野：
	組合せ最適化．特に現実の問題のモデル化に興味をもつ．

	受賞等：
	1997年 日本ＯＲ学会「事例研究奨励賞」
	2003年 日本人間工学会「研究奨励賞」
	2004年 日本ＯＲ学会「事例研究賞」

野々部 宏司 氏 （法政大学 工学部）

	経歴：	
	2000年 3月  京都大学大学院情報学研究科博士後期課程修了
	2000年 4月  京都大学大学院情報学研究科助手
	2005年 4月  法政大学工学部専任講師
	2006年 4月  法政大学工学部助教授 現在に至る

	興味ある研究分野：  
	メタヒューリスティクス，スケジューリングアルゴリズム

	受賞等：
	2003年 スケジューリング学会賞（学術賞）
	2006年 スケジューリング学会賞（学術賞）