納期を守り稼働時間を最小にしたい～複雑な問題に挑戦

2022.10.11X5:プログラミングコンテスト

第9回プログラミングコンテスト

　アスプローバ社主催の第９回プログラミングコンテストが、８月から９月にかけて行われました。今回の問題は、工場の設備稼働パターンを調整し、納期を守りながら、なるべく稼働時間を少なくするプログラムを作ることです。参加者には約１週間の期間が与えられました。そして9月14日、オンラインで表彰式と懇親会が開かれました。優勝したのは、bowwowforeach（ばうわうふぉーいーち）さん。16万円の賞金を獲得しました。「うれいしいです！」と感想を寄せてくれました。

　実際の問題文は10㌻を超える長さです。調整プログラムと計画プログラムがあり、作成するのは調整プログラムです。ただし納期を知っているのは計画プログラムなので、それと対話しながら、納期遅れが発生しないよう、ぎりぎりの稼働時間を見つけます。

　田中智宏社長はこう説明します。「こんどの問題は、今の生産スケジューラーではできないような案件です。一般に、設備の稼働パターンは、スケジューラーに初めから入力しておく情報で、必要に応じて手修正しています。ユーザーからの要望もあり、稼動パターンを調整できるよう試行している段階です。これからまさに仕上げようとしている機能の一部なのです」

　この複雑な問題に挑んだ参加者からは「楽しかった」という声が多く聞かれました。どんな方法で解いたのか、上位入賞者に聞きました。

１位　bowwowforeachさん

ー どんな解法を用いたのですか。

　初めに、稼働パターンを81パターンとして扱いました。パターン同士のコストを比較すると「稼働時間は少ないのにコストが高い」といったパターンが見つかります。これらは無駄なパターンとして除外し、さらに間引いて26パターンぐらいにしました。

　全設備/全週の稼働パターンをまとめて変更して出力、というのを二分探索的に繰り返し、納期に間に合い稼働時間のできるだけ少ない稼働パターンを見つけます。そして少しずつ稼働時間を減らすことを試していきます。どの設備のどの週を減らすかを評価値で決めます。評価値は多くのパラメータからなります。納期遅れの発生する可能性の高さで減点するイメージです。

ー 勝因はどこに?

　大きく稼働時間を減らすとスコアは大きく上がるけれども、納期遅れのリスクが高い。一方、少しずつ稼働時間を減らすと納期遅れリスクは低いが、探索回数制限によりスコアが上がり切らない、といったリスク・リターンの関係があります。これのバランスをとって探索できたのがよかったのではないかと思います。

ー 得意にしている分野は？

　最適解を出すのが難しく、できるだけ良い解を求める系のコンテストですね。いろんなアイデアを試したいので1～2週間ぐらいのコンテストが好きです。これからもどんどんコンテストに参加して強くなりたいです！

2位　玉寄修一（たまよせ・しゅういち）さん

ー シーマンのニックネームで知られる入賞常連の方ですね。今回の感想は?

　別のプログラム（計画プログラム）を十分に見る時間がありませんでした。あと１週間あれば１位がとれたかもしれません。二分探索から始め、調整案をランダムに作成、そしてその中でコストが小さいものを採用するといった手順で進めました。詳しくは後述します。

　これまでスケジューリングの問題は『焼きなまし法』で解くのが定石だったけれど、今回はそうではなく、新たな方法を試すことができました。自分の考えに従ったシステムが実装され、それがスコアになって反映されるのが面白いところです。

ー 今回工夫したところと今後の抱負をどうぞ

　出題されたのは、限られた回数の中で最適なスケジュールを求めるというものでした。方針としては、設備のおおまかな稼働パターンを求める際に 1つの設備に注目すれば、ある特定の稼働時間を境界にして「有効なスケジュール」と「無効なスケジュール」に分かれるため、その境界部分を求めるのに二分探索を用いました。

　また、細かくスケジュールを調整を行う部分では、「一番コスト削減が大きくなる案」を採用するのではなく「ランダムに調整案を作成しその中で一番良いものを選択する」といった「乱択」+「貪欲」を組み合わせた方針がうまくいきました。今後も 1位を目指して精進したいと思います。

3位　aconaite（あこないと）さん

ー 入賞おめでとうございます。

　アスプローバのコンテストは２回目の参加です。前回21位で今回はぜひ上位に入りたい、と挑戦しました。

ー 解法の工夫は

　現行の解法にこだわらず、常に新しい解法を考えるという点を意識しました。初めは二分探索法などの解法を試してみました。そして最初の週から貪欲に稼働パターンを変える解法を思い付きました。結果として、３回方法を転換してよいスコアが出ました。解法を複数持っていると、以前の解法とテストケースの得点を比較して、現行解法の弱点を見つけて改善案を考えることができ、解法のブラッシュアップにつながりました。複数の方法を用意していたのがよかったのではないか、と思います。

ー 今後の抱負をお願いします

　全体として、解いていくのが楽しい問題でした。これからは焼きなまし法やビームサーチをコンテストで使えるように、さらに修練したいですね。そして、Ｃ＋＋で実用的なツールやゲームを作っていきたいとも考えています。

　今一番興味があるのは、パズルの盤面に対して適用可能な手筋を検出するツールの開発です。また、数学の基礎知識を一つ一つ自分の手で証明し、その結果をオンラインにまとめるという活動もしていきたいと思っています。

タグ : 納期