第11回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 037）

• このコンテストはAHCレーティングの対象です。
• このコンテストは AWTF2025 選考の対象です。
• writer/tester: iaNTU, kozima, niuez, 他数名

アスプローバ株式会社について

アスプローバ株式会社は、工場の生産スケジュールを立案するソフトウェアであるAsprovaを開発・販売しています。日本ではトップシェア、中国・韓国・東南アジア・欧米など全世界で販売・技術サポート活動を展開し、世界ナンバーワンの生産スケジューラを目指して研究開発を行っています。エンドユーザーの業種は自動車、電子部品、食料品、化学、医薬、化粧品、素材など多岐に亘ります。具体的な導入事例については、事例紹介をご覧ください。

工場のスケジューリング問題は多くの場合、最適解を求めるのが困難です。したがって AHC と同じように何らかのヒューリスティックを使うことが有力な選択肢となります。

ここ数年、複数名の AtCoder ユーザをはじめとする組合せ最適化の知見を持ったメンバーが入社し、焼き鈍し法などの手法を取り入れることで、以前の Asprova では良い計画を立てるのが難しかったケースに対しても現実的な時間で良い解が求まるようになってきました。

アスプローバで取り組んでいるスケジューリング問題とは

アスプローバでは顧客の課題に応じて様々な最適化アルゴリズムを開発していますが、ここではよくある課題である「段取りを減らしながら、納期に間にも合うようにしたい」というものをご紹介します。

段取りとは生産する製品の切り替えの際に発生する作業のことを言います。例えば原料の変更、機械の設定の変更、金型の変更などです。段取りが多くなると、製造効率が下がったり余計なコストが発生します。特に多品種少量生産では段取りを減らすことが重要な目的になります。

段取りを減らすためには同じ製品をまとめて生産することが有効ですが、まとめることを優先すると他の製品の生産が後回しになり、納期遅れの発生につながります。

納期遅れを減らすためには、納期が近いものを優先して生産することが考えられます。しかし、多くの場合段取りが増えて生産効率が悪化します。

このような事情から、段取りと納期遅れの少なさをちょうどよいバランスで両立させる計画を立てることは難しく、人の手で長時間かけて計画を立てている場合もあります。

アスプローバではこういった問題に対して、人の手で行うよりはるかに効率的な計画を短時間で立てることができるアルゴリズムを開発しています。

実際には現場に応じて様々な要件があり、作業量なども膨大になるため、それぞれの顧客に合わせたアルゴリズムを開発する必要があります。

アスプローバでは最適化を含む以下の開発を行っています。

1. ヒューリスティックを使って工場のスケジューリングの最適化をする開発 (C++)
2. Asprovaを使い勝手が良いソフトウェアにしていくための開発 (スケジューリングロジック、UI/UX、データ連携など。C++)
3. Asprovaと連携するWebシステムの開発 (フロントエンド、バックエンド。javascript / typescript / html / css)

• 企業からのメッセージ | AtCoder Career Design
• 働く競技プログラマー図鑑 | AtCoder Career Design
• アスプローバ株式会社 求人一覧

Asprova 開発者からのひとこと

• 「最適化の仕事の中では、問題の解き方を考えるのに加えて、そもそもどんな問題を解くべきなのか、どう定式化すればよいのかも考えます。AHC の問題を解くのとはまた違った難しさ・面白さがあります」
• 「競技プログラミングが好きな方、これからも問題に対して智慧を絞りたい方にとって、やりたいことができる会社です！」
• 「SIMDを使用した定数倍高速化、stack pivotingによるスタックサイズ制限の回避など、OSやハードウェアの仕様を使ったhackがお好きな方はぜひどうぞ」
• 「データ構造・計算量なども基礎として必要ですが、アルゴリズムコンテストのように完璧に多項式時間で解くことは難しいため、近似・ヒューリスティックを使います。ユーザーごとに仕様が大きく異なったり、途中で要件の変更や調整もあり得ます。汎用的に作らないといろいろ大変になります。どうすれば性能と汎用を両立できるかを考えています」

成績上位者には、以下の賞金を授与いたします。賞金はAmazonギフトカードでお渡しします。

賞金の対象は日本国内在住で、参加登録時に賞金の受け取りを希望し、必要事項を入力された方となります。順位は賞金対象者内の順位です。

また、上位の方にパーカーを進呈する予定です。対象は日本国内在住者で、参加登録時にパーカーの受け取りを希望し、必要事項を入力された方の中から上位20名となります。詳細は対象者に個別にお知らせします。

コンテスト上位の方をアスプローバ株式会社 五反田オフィス（JR五反田駅 徒歩6分）にご招待して、表彰式・懇親会を行う予定です。

• 日時：2024年9月27日（金） 17:30 から
• 予定：
  • 17:00　受付開始
  • 17:30　主催者挨拶
  • 17:40　Asprovaユーザの問題紹介
  • 17:50　上位の方による解法の解説（10分×3名程度を予定）
  • 18:20　表彰式
  • 18:30　懇親会（食事あり）
  • 20:00　閉会
• 対象者：参加登録フォームで表彰式・懇親会に参加希望と回答された方のうち、上位15名程度を予定
• 遠方の方には旅費を支給します。

• 成績優秀者は正社員またはアルバイト(時給2,500円)採用を優遇します。

• 第1回 Asprova プログラミングコンテスト
• 第2回 Asprova プログラミングコンテスト
• 第3回 Asprova プログラミングコンテスト
• 第4回 Asprova プログラミングコンテスト
• 第5回 Asprova プログラミングコンテスト
• 第6回 Asprova プログラミングコンテスト
• 第7回 Asprova プログラミングコンテスト
• 第8回 Asprova プログラミングコンテスト
• 第9回 Asprova プログラミングコンテスト
• 第10回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 023）

AtCoderにて新たに定期的に開催されるプログラミングコンテストです。ABC/ARC/AGCなどのアルゴリズムコンテストと異なり、最適解を出すのが難しい問題に対し、出来るだけ良い解を作成するコンテストとなります。出題例などについては過去の類似形式のコンテストを参照下さい。

AHCでは、ABC/ARC/AGCでのレーティングとは異なる、ヒューリスティック部門用の新しいレーティングが付与されます。ABC等でのレーティングと異なり、コンテスト成績が悪くても下がることのない単調非減少型を採用し、平均的に良いパフォーマンスを出すことよりも、ベストパフォーマンスが評価される形式となります。気軽にご参加下さい。

腕に覚えがある人も、まだまだプログラミングは始めたばかりという人も、一度参加されてみてはいかがでしょうか？

• 問題は1問です。AtCoderで使用できるすべてのプログラミング言語を使用可能です。
• 誤提出・再提出のペナルティはありませんが、解答を提出する際は前回の提出から5分以上の間隔を開ける必要があります。
• コンテストは個人戦です。2人以上で結託し、解答する行為は禁止しております。
• コンテスト終了前に、問題の考察や解答を公開する行為は禁止しております。ただし、提供されたツール類の動かし方に関する情報は自由に共有して構いません。
• その他のルールは こちら を参照してください。

なお、上メニューバーの各ボタンの機能は、以下の通りです。

• トップ : 現在閲覧中のページです。
• 問題 : コンテストの問題の閲覧ができます。
• 提出 : コンテストの問題に対する、解答ソースコードを提出することが出来ます。
• 質問 : コンテスト全体、および各問題に対して、コンテスト中に質問し、その回答を閲覧することが出来ます。
• 結果 : 今までに自分が提出した解答を閲覧することができます。また、コンテスト終了後には他の参加者の解答状況を閲覧することが出来ます。
• 順位表 : 現在のコンテストの順位表が閲覧できます。

利用規約 、ルール 、用語集 、よくある質問 をご一読下さいませ。