会議予定表の再編成に関する基礎的考察

菊野　亨  吉田　典可  杉原　一夫  荒目　一紀 

誌名
電子情報通信学会論文誌 D  Vol.J66-D  No.4  pp.361-368
発行日: 1983/04/20
Online ISSN: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


本文: PDF(550.6KB)

あらまし: 
オフィスオートメーションへの関心の高まりとともに，ローカルコンピュータネットワークとデータベースシステムを統合したシステムが開発されてきている．このシステムに期待される重要な機能の1つに会議予定表の自動編成がある．自動編成においては，既に編成されている会議予定表に新たな会議を追加するという会議予定表の更新が基本的かつ重要な問題である．本論文では，会議予定表の更新問題を再編成問題として定式化し，その計算複雑さについて議論する．会議予定表の再編成問題とは，既に編成されている会議予定表と新たに追加すべき会議が与えられて，会議予定表の更新に伴って予定変更を余儀なくされる人間の総数が最小となるように，会議予定表を更新する問題である．ここで，会議予定表の更新には，単なる開催時刻の変更以外に，各人間に対し出席すべきものとして編成されている会議そのものの変更をも含んでいる．この問題の時間計算量に関し得られる主な結果は次の2つである．（1）会議予定表の再編成問題は一般にNP−困難である．（2）実用的に重要と考えられる2，3の部分問題は効率良く解ける．