2段階行程における仕事の割付けと順序づけ問題の解法

概要

論文の詳細を見る
機械M_1のあとで機械M_2で処理されるn個の処理対象が与えられていて、任意の1つの処理対象iは、例えば切削、孔あけ、研磨といったように3つの要素作業、〈a_i〉、〈p_i〉、〈b_i〉の処理を必要とする。このとき、〈a_i〉はM_1、〈b_i〉はM_2でしか処理できないが〈p_i〉はM_lまたはM_2のいずれの機械でも処理できるとすると、〈pi〉の割付け方により処理対象iについて代替的な2つの処理方法が考えられることになる。ここで、〈p_i〉をM_lに割付けたとき処理対象iの"I型のジョブ"と呼び、〈P_i〉をM_2に割付けたとき処理対象iの"II型のジョブ"と呼んでおこう。本稿で扱う問題は、総所要時間を最小にするスケジュールすなわち、n個の処理対象についての"ジョブの型"とその処理順序を求めることである。この問題は全ての処理対象についてジョブの型が決まったもとでは、Johnsonが扱った2工程フローショップ・スケジューリング問題になるので、総所要時間を最小にする各処理対象についてのジョブの型の決め方が考察すべき課題となる。I型のジョブを選択した処理対象の集合をλとしたもとでのJohnsonの先行順序関係を満たす順序列をS_λとする。S_ψから出発し、II型のジョブからI型のジョブヘの一方向の選択変更の操作により、すべてのS_λを網羅したネットワーク構造が生成される。本稿では、このネットワーク構造のうえで、S_ψから最適スケジュールに至る任意の変更系列上のスケジュールについて、総所要時間が狭義の単調減少することを証明し、任意のS_λから生み出されるすべてのスケジュールの集合についての総所要時間のLower-Boundを導き、解法を示している。
社団法人日本オペレーションズ・リサーチ学会の論文

2段階行程における仕事の割付けと順序づけ問題の解法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク