2024-03-29T06:25:00Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000171622020-10-27T05:02:56Z00934:00989:00999:01000
ニューラルネットワークによる複数機械の協調タスクを含んだ並列機械スケジューリングA Neural Network Model for Parallel Machine Scheduling Problems Considering Tasks with Machine Synchronizationjpn事例紹介論文http://id.nii.ac.jp/1001/00017162/Articlehttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=17162&item_no=1&attribute_id=1&file_no=1Copyright (c) 2006 by the Information Processing Society of Japan慶應義塾大学SFC研究所慶應義塾大学環境情報学部坂口, 琢哉石崎, 俊本稿では並列機械スケジューリング問題の一種として,特に複数のマシンが同期・協調的に処理する「協調タスク」を含み,さらに目的関数として「滞留時間和」「納期ずれ時間和」の双方を扱う問題に言及し,これを解決する手法としてリカレント型ニューラルネットワークの組合せ最適化を応用した新たなモデルを提案した.提案モデルは「タスク」「マシン」および「処理時刻」を符号化した3次元構造のスケジュール層と,問題に内在する制約や目的関数を符号化した制約層から構成される構造とした.特に処理時刻を直接符号化したことで,協調タスクにともなうマシンの同期が容易になった.また,周囲に配置された複数の制約層が中央のスケジュール層を制御する構造により,複数の制約や目的関数の同時並行的な処理が可能となった.評価実験ではタスク数とマシン数の増加に対する提案モデルの効率性を調査したほか,協調タスクを含まない場合と含む場合の双方のスケジューリングについて,既存手法との比較を行った.その結果,特に納期ずれ時間和に関して従来手法より優れた結果が得られ,モデルの有効性が示された.In this paper, we considered a kind of parallel machine scheduling problems with “cooperative tasks” accomplished with two or more synchronizing machines, mentioning to multiple objective functions of “total residence time” and “delivery time lag”. We proposed a novel model for this problem based on a recurrent type of neural network architecture for combinatorial optimization. It consists of one “Schedule Layer” of 3D structure representing combinations of tasks, machines and process time and several “Constraint Layer” representing each constraint or objective function. Direct encoding of process time simplifies a synchronization of machines for cooperative tasks, while the mechanism that peripheral constraint layers control a central schedule layer realizes parallel treatments of multiple constraints and objective functions. We evaluated the performance of our model with increasing the number of tasks and machines, compared it with traditional model for both situations with and without cooperative tasks and finally obtained the superior result of our model especially for delivery time lag.AA11464803情報処理学会論文誌数理モデル化と応用(TOM)47SIG14(TOM15)1711782006-10-151882-77802009-06-30