11th Asprova Programming Contest(AtCoder Heuristic Contest 037)

Can Participate: All Rated Range: All Penalty: None

コンテスト情報

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

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

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

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

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

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

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

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

段取り優先)同じ製品をまとめると段取りは減るが、後に回された黄色や紫の製品で納期遅れが発生する。


納期遅れ5件 段取り2回
※色のついた枠が製造作業を表し、色が製品の種類を、数字が納期を表す。
※右下に赤い丸のついているものは納期に間に合っていないもの。
※黒い小さい枠が段取り作業を表す。

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

納期優先)納期が近いものを優先すると納期遅れは減るが、段取りが増えて効率が落ちる。

納期遅れ3件 段取り9回

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

ちょうどいい計画例)納期遅れがなく、段取りも少なくなっている

納期遅れ0件 段取り5回

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

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

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

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

Asprova 開発者からのひとこと

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

賞金・賞品

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

対象者内順位賞金
1位80,000円
2位50,000円
3位30,000円
4位20,000円
5-10位10,000円
11-30位5,000円

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

また、上位の方にパーカーを進呈する予定です。対象は日本国内在住者で、参加登録時にパーカーの受け取りを希望し、必要事項を入力された方の中から上位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円)採用を優遇します。

過去のコンテスト

AtCoder Heuristic Contest(AHC)とは?

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

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

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

ルール

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

メニューについて

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

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

その他

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

Contest Information

About Asprova Corporation

Asprova Corporation is a company in Japan that develops and sells production scheduling software to factories for planning detailed workflows. Software development and headquarters are in Japan.

Asprova Corporation conducts sales and provides technical support in Japan and all over the world, including China, South Korea, South East Asia, Europe, and the United States. The company is dedicated to build the best production scheduler in the world.

Software development is done in Japan. While we make our product more handy to the users, we also study and develop optimization algorithms to solve highly complicated scheduling problem.

We are looking for world class programmers to help develop Asprova with us here in Japan.

Links to recruitment. The following contents are written only in Japanese.

Other privileges

  • The top performers will be prioritized when applying for a full time or part-time (2,500 yen per hour) job.

Links to past contests

About AtCoder Heuristic Contest(AHC)

This is a new series of programming contests that will be held regularly on AtCoder. Unlike algorithm contests such as ABC/ARC/AGC, the goal is to create a better solution to a problem for which it is difficult to find the optimal solution. For examples of problems, see past contests of similar format.

AHC has a new rating system that is different from the existing ABC/ARC/AGC rating system. Unlike the ABC/ARC/AGC ratings, AHC rating does not decrease even if contest performance is poor. Please feel free to participate.

Rules

  • There is one problem. You can use any programming language available on AtCoder.
  • There is no penalty for resubmission, but you must wait at least 5 minutes between submissions.
  • The is an individual competition. It is prohibited to publish your solution before the end of the contest. However, you are free to share information on how to run the provided tools.
  • For other rules, see here.