大学（ MESIのヤロスラヴリ支部 ）、専門「経済学における応用情報学」を卒業した最近の2002年に、課題は論文を選択することでした。 提案されたトピックのリストは気のめいるようなもので、ほとんどが退屈なデータベース開発です。 原則として、私の既存の開発の1つは、ヘッドが示唆するように、基礎として採用することができます。 椅子が、血がにじんでいた、私は自分自身のために面白いと新しい何かをしたかった。 特に大学のITサービスで働いていたので、スケジューリングのトピックを頭に提案し、ヤロスラブリの会社の製品であるKIS UZ（学校の統合管理情報システム）システムを担当しました。 KIS UZは良かったが、スケジュールを立てることができなかった。 また、これで私は何か役に立つことを目指していましたが、それを実装する試みはなかったことが判明しました。ハブで公開することで誰かの利益になるかもしれません。
そのため、可能な限り最善の方法で毎週のクラスのスケジュールを作成するようにコンピューターに教える必要がありました。 探索空間の規模を認識して、彼は最良の選択肢を見つけるという目標を設定しませんでした。 最初に、クラスとは何か、何が良いか、何が悪いかを判断する必要があります。 次のモデルは、そのような入力データに対して選択されました。
-週の日数
-1日のレッスン数
-教師のリスト
-グループ、サブグループ、およびストリームのリスト
-特定のタイプのオーディエンスの数
-タスク（クラス）のグループのセット：
- 職業
- 先生
- ストリームまたはグループ
- 聴衆のタイプ
- このクラスのグループ内のクラスの数
- 時間、監督が特定の時間にこのレッスンを「厳格に」確立したい場合
プロセスは、クラスを一時的なグリッドに配置する必要があります-スケジュール。 スケジュールの評価には、4つのパラメーターが参加します。グループと教師のスケジュールの「ウィンドウ」の数、グループと教師の日別のクラスの均等な分布です。 これらのパラメーターの重要性は、ディレクターによって設定されます。 最初は目的関数に階層分析の方法を適用したかったのですが、これらのパラメーターのペアワイズ比較を導入する必要があるため、線形関数を管理しました。
オーディエンスについては、単純化のためにスケジュールを削除しました。これにより、検索時に特定の時間の無料オーディエンスの数が考慮されました。 時間内にスケジュールを生成した後、聴衆が配置されました。 一般に、このような単純なモデルの概要を説明しました。 日中にプログラムをスケッチしたライブラリに基づいて、遺伝的アルゴリズムを少し実験しましたが、結果が気に入らず、考え直さずに他のアルゴリズムに切り替えました。 悪い結果は、私の薄っぺらなアプローチによるものだと思います。おそらく、モデルはGA用語でうまくエンコードされていません。 枝と境界の方法について考え始めました。 サーチスペースはツリーであり、レベルは占有を意味し、ブランチはタイムグリッドの要素です。 スケジュールは、ツリーのルートからハンギングピークの1つまでの方法と見なされます。 途中で、分岐の過程で、さまざまな理由でバイパスの可能性と便宜がチェックされます：教師、グループ、評価の雇用。 自然に、内陸の木をバイパスします。 各レベルには、現在のタスク用の無料のグリッドセルがあります。 ディレクターがこのタスクを特定の時間「厳密に」修正した場合、特定の時間に対応する1つのブランチが構築されます。 次に、ブランチに沿って、上限が推定され（さらに、これはこのタイプの無料視聴者の存在について監視されます）、上限が現在見つかった最適なスケジュールの推定値より高い場合（およびこのタイプの無料視聴者がいる場合）、それ以外の場合は、次のブランチに進みます。 分枝限定法では、重要なポイントは上限の推定値を見つけるためのアルゴリズムです。 さらに苦労せずに、現在の不完全なスケジュールを評価し、現在の最適なスケジュールと比較します。 さらに潜ると、不完全なスケジュールの推定値が悪化するため、すでに最良のスケジュールの推定値よりも悪化している場合、ブランチは拒否されます。 そして、このすべてをプログラムし、データを準備して（実際のデータに基づいてシステムから取得）、彼は夕方にそれを開始して帰宅しました。 午前中に職場に到着すると、彼はKIS UZに見つかった10億のスケジュールのうち最高のものをアップロードしましたが、涙なしでそれを見るのは不可能でした。 私は失望し、落胆し、次に何をすべきか分からなかった。 夕方、私たちは友達とビールを飲みに行きました、そして今、私はホップの下の停留所に立ち、最後の路面電車を待っています、そして私の頭の中には木、枝、境界、グレードだけがあります...それらを並べ替え、最初に他のオプションよりも良いスケジュールの一部である可能性が高いオプションがあることを確認してください。 しかし、それを行う方法は？ 彼がすでに2本目のタバコを吸っていたときに考えた。 最初に、スケジュールの各主題に対して独自の理想的なスケジュールを作成し、各ブランチについて、これらのスケジュールに入る度合いを計算し、それによってソートする必要があります。 朝、いつもより早く仕事に行き、途中で技術的な詳細を頭に描きました。正午までにヒューリスティックが組み込まれ、結果はKIS UZでかなり良く見え、残りの半日は微笑んでいました。
PS。 その後、PageRankについて聞いたとき、このヒューリスティックに似たものがあると思いました。