エレベータアルゴリズムとエレベータのアルゴリズム

ちょっと検索してみたところウィキペディアに英語記事はあるけど（ http://en.wikipedia.org/wiki/Elevator_algorithm ）日本語版の記事はまだのようだし、ジャストな解説も検索したところ出てこないようなので、そう難しいものでもないしちょっと書いてみる。

エレベータアルゴリズム

「エレベータアルゴリズム」というのは、特定のアルゴリズムのことであり、一般のエレベータのアルゴリズムのこと（特に、多数のエレベータがあるビルでは、連携させて複雑な制御がされる。後述）ではない。
コンピュータのディスクドライブのヘッドのシークへの応用が特に知られている。
原理は簡単で、次のようなものである（ここではディスクドライブではなくエレベータの用語で説明する）。

上の階へ行く要求（乗客の要求、および、上の階からの呼）がある限り、上昇して要求に応える。上の階への要求が無くなったら 2. へ
下の階へ行く要求がある限り、下降して要求に応える。下の階への要求が無くなったら 1. へ

これを繰り返すものである（正確にはエレベータの場合、呼の上行きと下行きを分けて、遷移の直前の「上の階からの下行きの呼だけがある」といった状況への対処が必要）。
ディスクドライブの場合は、たとえば「上の階への要求」を「ヘッドの現在位置より外周のセクタの読み書き要求」のように読み替えれば意味はわかるだろう。MS-DOS 時代にファイルサーバとして一世を風靡した NetWare の高性能さの理由の一つともされている。
斎藤由多加氏がテレビ番組で（おそらくNHKの『クローズアップ現代』1995年6月20日「ゲームを作り出す頭脳」ではなかったかと思うが、確信はない）エレベータのメーカに聞いても教えてもらえなかったが「円運動」というヒントをもらって、ゲーム「The Tower」を作ることができた、と、大層苦労されたように演出されていたが、このアルゴリズムは実践的な OS の教科書（たとえば Minix 本）であれば、まず書いてあるものである。
アルゴリズムの特性としては、必ずしも最適ではない（場合によっては、小さく行ったり来たりさせたほうが良い成績の出るパターンがあるかもしれない）が、とても単純で、かつ放置されるリクエストが発生しないという点がすぐれている。
なお、近年の soft update のように、ファイルシステム側からの要求として、書込み要求をディスクドライバの都合で任意の順にはできない場合もあり、そういった場合にはそのまま使うことはできない。

エレベータのアルゴリズム

ビルに 1 基だけのエレベータであれば、上記のエレベータアルゴリズム以外に選択の余地は（一般的には）無い。しかし、2 基（ないし 3 ～ 4 基程度）のエレベータがあるビルで、常に各階から各階への要求がある場合について観察すると、2 基のエレベータが常に「連れ立って」動くような振舞をするということが知られている。日本の文献では、既に戦前に寺田寅彦が指摘している（青空文庫で読める。 http://www.aozora.gr.jp/cards/000042/files/2483_11319.html の 2 節目「二　エレベーター」を参照）。
もし、2 基のエレベータが交互になるように動いていてくれれば、乗客の待ち時間は少なくなるだろう。要求に応じて動くのではなく、自動運転で各階に必ず停止する運用のエレベータ（銀座アップルストアのエレベータはそんな感じである）であれば、2 基が交互に動くよう調整することもできると思われる。しかし、一般には 2 基程度では、複雑な調整の余地はあまりなく、各個に前述のアルゴリズムに従って動かしているものがほとんどのようである。
これが、エレベータシャフトに 6 基とか 8 基のエレベータがあり、それぞれのかごが高速まで加速する（すぐ止められない）ようなビルになってくると、話はそう単純ではなくなってくる。
群管理（ぐんかんり）と呼ばれているもので、前述の斎藤氏の話ではないが、こちらのほうは詳細は各メーカのノウハウの詰まった秘密と思われる。実際にそういったビルでは、一例としては、状況によって待っている人がいても先行するかごを素通しさせ、後からのかごを止める、といったことがおこなわれている。そういったビルは利用者に不快に思われないよう、かごが今何階にいるかの表示はせず、フロアからシャフト内が見えないようになっているのが普通だが、扉のすきまからの風や音でそれとわかる（中には見えるようにしていて不評を買っているビルもあるようだが）。
こちらについての解説は、私の読んだものでは、コンピュータサイエンス誌『bit』の 1999年1月号 pp. 70～73「エレベータの群管理」（ http://iss.ndl.go.jp/books/R000000004-I4621476-00 ）にあるので、気になる人は図書館などで見てみるといいと思う。中には複数組の乗客が乗り合わせないよう特殊な制御をしているエレベータもある（ラブホ）といった小話も載っていた。私は未見だが、CQ出版『Interface』誌 1996年8月号付録 CD-ROM『InterGiga』No.3（ http://www.cqpub.co.jp/interface/intergiga/ig03.html ）にも「●絵解きシステム解説新幹線文字ニュース･システム／エレベータ群管理システム」という記事があるようだが、雑誌付録 CD-ROM なので参照は難しいかもしれない。
（追記。検索するとメーカーの広告等や、学術論文のデータベースの情報なども出てくるが、ネットですぐ読めるテクニカルな文献としては http://www.net.c.dendai.ac.jp/~s98kc607/thesis.html が良いと思う）