Skip to content

HACK TO THE FUTURE 2022 予選

問題概要

  • N=1000 個のタスクを M=20 人のチームメンバーに割り振りたい
    • 各タスクは高々 1 人に割り振る
    • タスクは割り当てられると、そのタスクが終わるまで他のタスクは割り当てられない
  • 各メンバーは K 種類の技能レベルがあり、ベクトル s で表されるが、入力としては与えられない
  • 各タスクは各技能に対する要求レベルが決まっており、ベクトル d で表され、入力として与えられる
    • また、タスク間には依存関係(1000<=R<=3000 個の有向辺で与えられる)があり、あるタスクを割り振るためにはそれに依存するすべてのタスクが前日までに終わっている必要がある
  • メンバー j がタスク i を行った場合、「各技能の要求レベルに満たない分」の合計を w として、w=0 なら 1 日、w>0 なら w±r(-3 ～ 3 の一様乱数)日だけかかる
  • できるだけ短い日数ですべてのタスクが終わるように、各日のタスクの割り当てを求めよ
    • interactive 問題で、各日ごとに、完了したタスクを受け取り、その日の割当を返却するプログラムを作成せよ

時間

240 時間

個人的メモ

  • ざっくり「スキル推定」と「タスク割当」パート
  • 特に、「タスク割当」は、手が空いている人に割り当てだと良くないケースがあり、タスク中の人にも割り当てを考える部分がどの程度できたかで差が出ていた模様

スキル推定

  • それまでに選択したタスクとかかった時間を保持して、絶対誤差/二乗誤差(MSE)あたりが最小になるように山登り/焼きなましなど
    • 自由度があるので、正則化項(L2 ノルムとか)なども
  • 最初の方は、あえて探索要素をいれるなど
  • ベイズ推定、MCMC

タスク割り当て

  • クリティカルパス(一番時間がかかるタスクのパス)がボトルネックになるので、そのようなパスを重視するなどは必要
    • 深さ、などでも良い
    • クリティカルパス分析
  • greedy なタスク割当で難しいところは、人が余ってないときや強い人がタスク中のときに、タスクが終わったからといってその人が不得意な仕事を割り当てることになりえること
    • そこで、「人(全員)と、割り当て可能なジョブ」の組み合わせに対して評価値を考える
      • 手が開いてる人に対してだけだと、評価関数をちゃんとやってても、活かされないような割り当てする可能性がある
      • タスク中でも、終わってからタスクをやった場合というのを考える
      • ここが、R が大きいときに重要で、暫定 97k 点台と 101k 点台ぐらいの差がでていたキモ
    • 反省: 自分は「終わりが近い人も含めて割当を考える」だけをしていた(全員ではない)
    • 人 i にタスク j を割り当てるときの評価関数
      • パスの重み/最長経路/要求技能レベルの総和
      • かかる時間(タスク終了見込み時間)
      • 自分にどのぐらい向いている仕事か
      • あえて少し待ってから仕事をするペナルティ
      • 全タスクが終わるまでにかかる最短時間(可能であれば。終盤だけでも)
      • 先読みしたときのコスト(依存が強い場合)
      • などで調整
    • 実際の割り当て方は、評価関数をもとに、貪欲、山登り/焼きなましなど
  • 割り当て方は、最小費用流＋アドホックや、LP ソルバで計算していた方も
    • マッチングを最小費用流で解くやつで、かかる時間の合計が小さくなるような割り当てを求める
      • s->人の部分で辺を複数本に分けてそれぞれコストを分けることで均等になるような工夫(terry_u16さん)
    • 能力が低い人は別処理、など

その他

  • R によって問題の性質が違っていた
    • R が小さい(1000 付近)と、依存が少ないので、やれるタスクが多い → 自分が得意な仕事ができる
    • R が大きい(3000 付近)と、依存が多く、やれるタスクが少なく、暇になっている人が多い → 得意な人が全部やったほうが早いのに、手があいてるからと不得意な人が手をつけてしまうと逆に遅くなる(あえてやらないほうがよい)
  • 「R ごとに調整」するとよかった可能性

解説

(50 位まで&発言を見つけられた方のみ)