2014年（平成26年)CCPM法の枠組みにおける資源競合の解消方法 CCPM法の枠組みにおける資源競合の解消方法 ∼局所探索法と遺伝的アルゴリズムの活用∼ ResOlutionofResourceConnictsintheCCPMFramewOrk UtilizationofaLocalSearchMethodorGeneticalgorithm 古賀裕紀五島洋行千葉英史 HimkiKOGAHiroyukiGOTOEishiCHIBA 法政大学大学院理工学研究科システムエ学専攻修士課程 Wepmmsea"IDximatemethodsibrIEsolvingIEsc山℃econnictsintheCrincalchainPInj"t MaImgement(CCPM)method.T11eCCPMmelhOdcomistsomvePImesSCS.111el℃aIEefYEtiveapproaches f b r f b u r o f t h e f i v e p I w e s s e S ・ H o w e v " l b r t h e m m a i n i n g u n 爬 s o l v e d p I w e s s l h a t r ℃ s o 1 v " E u r C e c o n n i c t s , a n e f Y i e c t i v e m e t h c d h a s y e t t o k p m m s e d . H e n c e , w e d e v e l o p l l l I E e s i m p l e a p p m x i m a l e s o i v i n g m e l h o d s , andmpmvEtherusingalocal=IEhorgenelicalgorithmMelhMsmsedontheearlieSiandlaleststart t i m e s a r e u " d . T h m u g h n u m e r i c a l e x " r i m e n t a t i o n s , w e i b u n d i h a t t h e p m m s e d m e t h o d s 劃己 p m c t i c a l i f t h e n u m k r o r o u l p u t s i s O n e . K匂，〃わ":"〃加切ﾙo4FEsα"℃ecoJW"""ﾉs“'℃〃,gaiefにα妙師〃"1,"J"やA"α陸6m 1 ．はじめに本研究では,CCPM法の手順の一つである資源競合の解消を行うための近似解法を提案する.CCPM法とは，プロことができる．と定実数全体をRとし'Rmax=RU(-CO}, 実数全体をRとし,Rmax=RU(-"),X,yERmaxと定挺する.max-plus代数系では，加算eと乗算③を x$y=max(x,y),(1) ジェクトエ程の実行時間の不確実性を考慮し，プロジェクトにかかる時間の短縮と遅延防止の両立を目的としたプ x y = x + y ( 2 ) と定接する．演算子の優先順位は，通常の代数系を同様にロジェクト管理手法である．その運用手順は,1.タスク ③は＄よりも高いとする．また，通術の代数系での0と'にの洗い出し，2．余裕時間の没収，3．資源競合の解消，4．相当するゼロ元と単位元をそれぞれご(=-"),e(=0)と工程の分類とネックエ程の検出,5．時間バッファの挿入，の五つに分けることができ，各手順の詳細は2章で説明する．文献l)では，手順4,5の二つをmax-plus線形方程式表記し， x$E=E$x=E,(3) xee=ex=x(4) が成立する．また，諾②E=E③蛇=E(5) を用いることで，従来のCCPM法の計算に比べて簡素な線形方程式に定式化することに成功した．文献2)では，時間バッファを考慮しない資源競合の解消問題の定式化に成功した．しかし，時間バッファを考慮した資源競合の解が成り立つ．さらに，減算子、を次式のように定義する． xly=-x+y.(6) (2)CCPM法の運用手順まず，使用する文字や記号を定錐する．消の具体的な解法は提案されていない．そこで本研究では， ●加：工礎数三つの初歩的な近似解法と，その近似解法を局所探索や遺伝アルゴリズムを用いて改群する手法を提案する．また計・9：外部入力数 ●p:外部出力数算実験を行い,提案する近似解法が実用的な近似解法かど ●FoERIMW:0,i)に枝がある場合は[Fo]【ノ=eで，枝がうか検証する． 2．背景知識 (1)Max-plus代数 Max-plus代数3)とはpmaX演算と+演算を基本減算とする代数系であり，生産システムやプロジェクト符理，交通システムなどの離散班象システムのモデリングに利用するない場合はE ・BoER":外部入カノにつながる工程iが存在すれば [Bo1〃=EDそれ以外の場合はE OCOER":工鋤が外部出力iに接統されているならば [co]"=e,それ以外の場合はE ●aERn:各工程の実行時INIを表すベクトル ●P:diag(d) 7