2nd Asprova Programming Contest

2nd Asprova Programming Contest

Asprova プログラミングコンテストとは

  • Asprova株式会社が開催するマラソン型のプログラミングコンテストです。
  • アスプローバ株式会社は、生産スケジューラ(工場の詳細スケジュールを計算するソフトウェア)を開発・販売している日本の会社で、製品開発は日本で行っています。日本ではトップシェア、中国・韓国・東南アジア・欧米など全世界で販売・技術サポート活動を展開し、世界ナンバーワンの生産スケジューラを目指して研究開発を行っています。

問題

  • 工場はM(≦20)台の設備で、I(≦20)種類の品目を生産する。各品目は最大P(≦5)工程で生産される。工程は合流も分岐もしません。今、R(≦200)個のオーダ(注文)がある。オーダは数量と最早開始時刻と納期が指定される。各設備で品目を切り替えるとき、品目の前後関係に依存して切り替えのための段取り時間が発生する。もちろん納期に遅れたくないが、着手は遅いほうが望ましい。着手が遅い方が、オーダの変更やキャンセルに対応でき、かつ、仕掛在庫や製品在庫が少なくなるからです。極力、段取りが少なく、納期を守り、着手が遅いスケジュール求めたい。

  • コンテストの開始に先立って、予定している暫定問題を本ページ最下部に公開します。この先、詳細部分は変更される可能性がありますが、骨子の部分は変更いたしませんので、コンテスト開始まで時間を十分に使って解法、実装方法を検討してください。

ルール

  • 参加資格:所属・年齢・居住地を問いません。(アスプローバ株式会社と同業関係者はご遠慮ください)
  • 参加登録:参加希望の方はこのページの参加登録ボタンから参加登録を行ってください。ベータ版からは参加登録できませんので、ご注意ください。
  • 参加登録期間:2018年11月1日~2019年1月6日
  • コンテスト開催期間:2018年12月24日~2019年1月6日
  • コンテストは、オンラインで実施します。
  • コンテスト期間中は何回でも解答を提出できます。但し、提出後1時間は再提出できません。
  • 使用可能言語:C++, C#, Python 3, Java8
  • 問題文は日本語と英語で提供します。
  • その他、AtCoder社の利用規約、チュートリアル、ルール、用語集、よくある質問 をお読みください。

審査と評価方法

  • 入力ファイルを入力し、問題を解く処理を行い、結果を指定されたフォーマットの出力ファイルに出力するプログラムを作成していただきます。処理は指定された時間以内で終了してください。結果の評価式により評価値を計算し優劣を競います。

賞金

  • 成績上位者には、以下の賞金を授与いたします。
  •  1位 160,000円
  •  2位 80,000円
  •  3位 40,000円
  •  4位 20,000円
  •  5位 10,000円
  • 表彰式に参加される場合は表彰式当日にお渡しします。参加しない場合はオンラインでお渡しできるギフト券などでお渡しします。

表彰式

  • 日時:2019年1月11日(金) 17:00から
  • 会場:SALON,CAFE & BAR ToiToiToi(トイトイトイ 東急電鉄 大岡山駅 徒歩5分)
       〒145-0062 東京都大田区北千束3-20-8 TEL 03-6425-7578
  • 定員:25名
  • 備考:表彰式は日本語で行われます
  • 予定:
  •    16:30 受付開始
  •    17:00 主催者挨拶
  •    17:10 入賞者によるプログラム解説
  •    17:40 コンテスト講評 (東京工業大学 工学院 経営工学系 水野教授)
  •    17:50 表彰式
  •    18:00 懇親会(食事あり)
  •    20:00 閉会
  • 申し込み:
  •    コンテストに参加しなかった方でも参加できます。食事のみを目的とした方は、ご遠慮ください。
  •    定員をオーバする場合は以下の順番で参加の可否を決めさせていただきます。
  •     1.入賞者5名
  •     2.コンテスト参加者
  •     3.その他、本プログラミングコンテストに興味のある方
  •    参加ご希望の方はこちらから、お申し込みください。

特典

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

権利関係

  • 本コンテスト参加者は、提出プログラムの著作権(著作権法第27条および第28条に規定する権利を含む)を主催者に移転し、著作者人格権を行使しないものとします。

当コンテストの問題と、実社会の問題との関係

  • 実際の工場のスケジューリングに、どう役に立つのか
    例えば、金属加工のプレス工程で金型が変わると段取りが入ります。 段取りは機械を止めるため、極力少ないほうが時間ロスがありません。 しかし、各オーダには納期があり、納期遅れは、顧客満足度を低下(顧客を激怒)させ、 以降オーダを頂けなくなる可能性があり、会社にとって死活問題です。 納期は最終工程の終了時刻に対するものですが、段取りは各工程で発生するので、 段取りと納期遅れを両方とも少なくするスケジュールを作成することは難しい問題です。 プレス工程では、同一オーダが同一のプレス機を複数回通ることがあり、スケジュールの最適化はより困難になります。

    多工程の段取りと納期の問題は、プレス以外でも、色替え、幅替え、原料替えなど様々な段取りの種類が存在し、すべての工場にとって重要な解決すべき問題です。

    現実問題はさらに多くの複雑な要素が絡みますが、この問題をコンピュータでうまく解くことができれば、全世界の製造業の生産効率と、顧客満足度の向上に大いに貢献することが期待できます 。

リンク

更新履歴

  • 2018年11月 :公開
  • 2018年12月3日:暫定問題を公開
  • 2018年12月7日:表彰式の参加申込み開始



暫定問題

工場にはM台の設備があり、I種類の品目を生産できます。各品目は最大P工程で生産されます。工程は合流も分岐もしません。今、R個のオーダ(注文)を受け付けました。オーダrは品目i、数量q、最早開始時刻e、納期dが指定されます。各設備では品目の前後関係に依存した段取り時間が発生します。このとき、以下に述べる制約に従い、すべてのオーダrの工程pの作業O_{rp}に対して設備m、製造開始時刻t_2を決定し、計画の評価値Vが最大になる計画を作成してください。

用語

    BOM
  • Bill Of Materialsの略。生産管理で用いられる専門用語。ある作業を行うときの製造方法に関する情報のこと。品目、設備、製造時間など。
  • 割り付ける
  • 各作業を行う設備と製造開始時刻を決定すること。例:作業O_{rp}を設備mに割り付ける。

入力

  • M :設備数(1..20,整数)
  • I :品目数(1..20,整数)
  • P :最大工程数(1..5,整数)
  • R :オーダ数(1..200,整数)
  • BL :BOM行数(1,2..,整数)
  • A_1 :段取り時間ペナルティ係数(0 \leq A_1 \leq 100,実数)
  • A_2 :納期遅れペナルティ係数(0 \leq A_2 \leq 100,実数)
  • A_3 :着手遅延ポイント係数(0 \leq A_3 \leq 100,実数)
  • B_1 :段取り時間べき乗数(0 < B_1 \leq 2,実数)
  • B_2 :納期遅れべき乗数(0 < B_2 \leq 2,実数)
  • B_3 :着手遅延べき乗数(0 < B_3 \leq 2,実数)
  • C_m :設備mの製造時間係数(1..10000,整数) (m=1..M)
  • D_m :設備mの段取り時間係数(1..10000,整数) (m=1..M)
  • i :品目番号(1..I,整数)
  • p :工程番号(1..P,整数)
  • m :設備番号(1..M,整数)
  • t :一個当たりの製造時間(1..20,整数)
  • r :オーダ番号(1..R,整数)
  • e :最早開始時刻(0,1..,整数)
  • d :納期(0,1..,整数)
  • q :製造数量(1,2..,整数)
HEADER M I P R BL
EVALUATIONFACTOR A_1 A_2 A_3 B_1 B_2 B_3
PRODUCTIONFACTOR C_1 C_2C_M
SETUPFACTOR D_1 D_2D_M
BOM i p m t
:
ORDER r i e d q
:
BOMの行数はBL、ORDERの行数Rです。

計画

オーダrp番目の工程の作業O_{rp}の計画は以下で定義されます。

  • 設備:m (1,2..)
  • 段取り開始時刻:t_1 (0,1..)
  • 製造開始時刻:t_2 (0,1..)
  • 製造終了時刻:t_3 (1,2..)
  • 段取り終了時刻=製造開始時刻

出力

  • OL :作業数(1,2..,整数)
OL
m r p t_1 t_2 t_3
:
全体で1 + OL行、出力してください。

制約

  • BOM
  • 品目iの工程pは一部またはすべての設備で製造が可能であり、それらに依存して 1個あたりの製造時間tが決まっています。それらの組合せは入力データBOMで定義されます。入力データBOMの行数は品目iと工程pごとに使用可能な設備の数だけあります。
  • 1つのオーダの複数の作業で同一の設備を使えるように定義されていることもあります。つまり、あるオーダは工程pで設備mで製造を行なった後、どこかの工程で再び設備mを使うこともあります。
  • 計画開始時刻
  • 計画開始時刻は0とし、0 \leq t_10 \leq t_2 とします。
  • 設備キャパシティ
  • 各設備 m は計画開始時刻以降のいつでも割り付けられます。休日や休憩時間はありません。ただし同一時刻に一つの段取りまたは一つの製造しか割り付けられません。
  • 製造時間
  • 設備 mには製造時間係数C_mが定義されており、設備 m での作業 O_{rp} の製造時間は、t×q×C_mです。
  • 段取り時間
  • 設備 mには段取り時間係数D_mが定義されており、設備 m での作業 O_{rp} の段取り時間は(|後品目番号-前品目番号|%3)×D_mです。つまり、設備m上で直前の作業との品目番号の差を3で割った余りにD_mを掛けた値です。直前に作業がない場合(つまり時系列上の先頭)は、段取り時間は0です。
  • 段取り開始時刻
  • p = 1のとき、e \leq t_1 です。
  • p \geq 2のとき、t_{3r(p-1)} \leq t_{1rp}です。(t_{3r(p-1)} は1つ前の工程の作業O_{rp-1}の 製造終了時刻、t_{1rp}はその工程の作業O_{rp}の段取り開始時刻の意味です。) つまり、前工程での製造が完了するまでは次工程の段取りを開始できません。
  • 下図は 2工程からなるオーダ1、2が割付いた図で、灰色が段取り時間です。作業O_{22}の段取り開始時刻は左図がNG、右はOKです。
  • NG OK

  • 分割禁止
  • オーダの数量 q を複数のオーダに分割してはいけません。
  • 作業の数量 q を複数の作業に分割してはいけません。
  • 未割り付け禁止
  • すべてのオーダの作業を割り付けなければいけません。

評価値

制約に違反した場合は評価値は無効となります。すべての制約を満たす計画に対しては以下の評価値を計算します。
 V  = 10^6  -  A_1 × Σ (段取り時間^{B_1}) - A_2 × Σ (納期遅れ時間^{B_2}) + A_3 × Σ (着手遅延時間^{B_3})
(ただし V < 0 のときは、 V = 0 とする。また小数点以下は最後に切り捨てる。)

  • V :評価値。正の整数
  • A_1 :段取り時間ペナルティ係数
  • A_2 :納期遅れペナルティ係数
  • A_3 :着手遅延ポイント係数
  • B_1 :段取り時間べき乗数
  • B_2 :納期遅れべき乗数
  • B_3 :着手遅延べき乗数
  • st = オーダの先頭工程の作業のt_1
  • et = オーダの最終工程の作業のt_3
  • 段取り時間 = t_2 - t_1 :作業ごと
  • 納期遅れ時間 = max( et - d,0 ) :オーダごと
  • 着手遅延時間 = min( st, d )- e :オーダごと

評価値Vを最大にすることにより、極力、段取りが少なく、納期を守り、着手が遅い計画を求めます。着手が遅い方が良いのは、オーダの変更やキャンセルに対応でき、かつ、仕掛在庫や製品在庫が少なくなるからです。

出力データの評価用プログラムはこちらからダウンロードできます。


入力例

HEADER 3 2 2 2 6
EVALUATIONFACTOR 1 5 0.1 1 1.1 1
PRODUCTIONFACTOR 3 2 1
SETUPFACTOR 1 1 1
BOM 1 1 1 1
BOM 1 1 2 1
BOM 1 2 3 1
BOM 2 1 1 1
BOM 2 1 2 1
BOM 2 2 3 1
ORDER 1 1 0 3 1
ORDER 2 2 1 4 1
  • ※BOM は 品目i=1の工程p=1は設備m=1,2へ割り付け可能、工程p=2は設備m=3のみに割りつけ可能という指定。i=2も同様。
  • A_1=1, A_2=5, A_3=0.1は、段取り時間、納期遅れ時間、着手遅延時間はその比率で重視するという指定。
  • B_2=1.1は、納期遅れ時間のペナルティは遅れ時間に比例するのではなく、1.1乗されて評価されるという指定。

出力例 1

4
1 1 1 0 0 3
2 2 1 1 1 3
3 1 2 3 3 4
3 2 2 4 5 6

例

  • オーダ1:納期d=3、最終工程作業のt_3 = et = 4、段取り時間 = 0、納期遅れ時間 = 1、着手遅延時間 = 0
  • オーダ2:納期d=4、最終工程作業のt_3 = et = 6、段取り時間 = 1、納期遅れ時間 = 2、着手遅延時間 = 0

評価値 V = 10^6 − 1 × 1^1 − 5 × (1^{1.1}+2^{1.1}) + 0.1 × 0^1 = 10^6 − 1 − 5 × ( 1 + 2.143… ) + 0 = 10^6 − 16.717... = 999983.282… = 999983

出力例 2

4
1 2 1 1 1 4
2 1 1 0 0 2
3 1 2 2 2 3
3 2 2 4 5 6

例

  • オーダ1:納期d=3、最終工程作業のt_3 = et = 3、段取り時間 = 0、納期遅れ時間 = 0、着手遅延時間 = 0
  • オーダ2:納期d=4、最終工程作業のt_3 = et = 6、段取り時間 = 1、納期遅れ時間 = 2、着手遅延時間 = 0

評価値 V = 10^6 − 1 × 1^1 − 5 × (0^{1.1}+2^{1.1}) + 0.1 × 0^1 = 10^6 − 1 − 5 × 2.143… + 0 = 10^6 − 11.717… = 999988.282… = 999988

出力例2の方が評価値Vが大きいため、評価が高い。


入力データ

入力データ数は全部で45個あります。順位は45個の入力データの評価値Vの合計の大きい順で決まります。

Asprova Programming Contest

  • This is a marathon style programming competition hosted by Asprova Corporation.
  • Asprova Corporation is a company in Japan which develops and sells production scheduling software to factories for planning detailed workflows. Development of the software is done in Japan. Asprova Corporation has the leading market share in Japan, and the software is also sold and supported worldwide in China, Korea, South East Asia, Europe, United States. The company aims to research and develop the number one production scheduler in the world.

Problem

  • In a factory, there are M(<=20) machines, and I(<=20) types of items to be manufactured. Every item type have at most P(<=5) contiguous process in the manufacturing workflow. There are no convergence or branching of processes. Currently, there are R(<=200) orders, where each order has a specified quantity for an item, the earliest production start date, as well as the due date. If a machine switches item type in between tasks, a delay is incurred. Preferably, each order should be delivered as late as possible while still meeting the delivery due date, as this would leave room for modifications to the order or cancellations to occur as well as reduce the amount of time manufactured items would sit in inventory. In summary, the schedule should have as little delays, as little missed due dates, and the latest deliveries as possible.

  • Prior to the start of the contest, we will publish an example question to be released at the bottom of this page. Although details may be changed in the future, the core question would remain the same, so you have time to think about the solution and implementation before the start of the contest.

Rules

  • Participation requirement: Anyone can enter regardless of age, organisation or location. (Person in the same business is not allowed.)
  • Participation registration: Click on the Register button to register. Please note that participation can not be registered from the beta version.
  • Participation registration period: 1st November 2018 - 6th January 2019
  • Contest period: 24th December 2018 - 6th January 2019
  • This contest will take place online.
  • During the contest period, answers may be submitted as many times as one may like, although one may not submit within an hour of the previous submission.
  • Language that can be used: C++, C#, Python 3, Java 8
  • The question would be provided in both Japanese and English.
  • Please also read AtCoder's Terms of Service, tutorial, rules, glossary, FAQ for other information.

Judging and evaluation criteria

  • The program will have to finish processing the input data within the time limit and the output result will be scored. The winner is the result with the highest score.

Prizes

  • The following cash prizes will be awarded to the top performers:
  •  1st: 160,000 yen
  •  2nd: 80,000 yen
  •  3rd: 40,000 yen
  •  4th: 20,000 yen
  •  5th: 10,000 yen
  • Cash prizes will be given in the awards ceremony. If you do not participate the ceremony, you will be given with a gift certificate etc. that you can hand in online.

Awards Ceremony

  • Date: 11th January 2019 (Friday), 5.00pm
  • Place: SALON,CAFE & BAR ToiToiToi (5 minutes walk from Tokyu Dentetsu, Ookayama station)
    Tokyo, Ota, Kitasenzoku 3-20-8, Postal Code 145-0062, TEL 03-6425-7578
  • Capacity: 25 people
  • Remarks: The award ceremony will be in Japanese.
  • Schedule:
  •    16:30 Reception start
  •    17:00 Greeting from organizer
  •    17:10 Program explanation by winners
  •    17:40 Contest review (Professor Mizuno, Department of Industrial Engineering and Economics, School of Engineering, Tokyo Institute of Technology)
  •    17:00 Awards Ceremony
  •    18:00 Social gathering (with meals)
  •    20:00 Closing
  • Application:
  •    Even those who did not participate in the contest can participate. Those who only aim for meals, please refrain.
  •    When overloading the capacity, we will decide whether to participate in the following order.
  •     1. 5 winners
  •     2. Contest participants
  •     3. Other interested in this programming contest
  •    If you wish to participate please click here.

Other priviledges

  • The top performers will be given priority for consideration for a full time job or part-time (Hourly pay 2,500 yen).

Copyrights

  • The rights of the source code (Japanese copyright law article 27 and article 28) submitted by the contest participants will be transferred to the contest holder, and the author may not exercise his/her personal rights over it.

How does the contest question relate to real world problems?

  • How to make a good production schedule for real factories?
    Given an example such as molding metal, if the next task requires a different mold, the molding equipment has to be changed and it incurs a downtime. Thus to avoid large amounts of downtime, such changes should be kept to a minimum. As every order has a due date, customer satisfaction will decrease if the order is overdue, and the customer may not order from that factory again. This is a major problem for factories worldwide. Although only the final manufacturing process has to finish in time before the due date, there will be downtime in between processes due to various circumstances and it is a great challenge making a production schedule that minimizes downtime and missed due dates. In a molding process, the same order would repeatedly use the same machine multiple times, making schedule optimization difficult.

    The problem of downtime and missed due dates apply to many processes besides molding, and it is a problem common to all factories that must be tackled.

    Although this is a very complicated issue, if a computer can be used to solve these problems, it would contribute to raising production efficiencies in factories worldwide and improving customer satisfaction.

Link

Revision History

  • November 2018: Created contest page.
  • December 3, 2018: Publish qestion to be released at the start of the contest.
  • December 7, 2018: Start application for participation of the awards ceremony.



Question to be released

In a factory, there are M number of machines that could manufacture I number of types of items. For each item, there are up to P number of consecutive processes in the manufacturing workflow. Process does not have convergence or branching. The factory has received R number of orders. Each order, r, specifies an item i, quantity q, earliest manufacturing start date e, and due date d. For each machine, setup times are incurred when swapping items to be manufactured. Under these constraints, compute the scheduling plan with the highest evaluation score V for all orders r, processes p, operations O_{rp}, and manufacturing start time t_2.

Glossary

    BOM
  • Abbreviation for Bill Of Materials. It is an industry term used in Manufacturing Process Management. The BOM specifies how items are to be manufactured, using which machines, manufacturing times etc The factory's operations are generated from the BOM.
  • Assignment
  • To specify a machine and manufacturing start time for an operation. E.g. Operation O_{rp} is assigned to machine m at t_1 time.

Input data

  • M: Number of machines (1..20, integer)
  • I: Number of items (1..20, integer)
  • P: Max number of processes (1..5, integer)
  • R: Number of orders (1..200, integer)
  • BL : Number of BOM lines (1,2.., integer)
  • A_1: Setup time penalty (0 \leq A_1 \leq 100, float)
  • A_2: Overdue penalty (0 \leq A_2 \leq 100, float)
  • A_3: Assignment lateness bonus (0 \leq A_3 \leq 100, float)
  • B_1: Setup time exponent (0 \leq B_1 \leq 2, float)
  • B_2: Overdue exponent (0 \leq B_2 \leq 2, float)
  • B_3: Late assignment exponent (0 \leq B_3 \leq 2, float)
  • C_m: Machine manufacturing time multiplier (1..10000, integer) (m=1..M)
  • D_m: Machine setup time multiplier (1..10000, integer) (m=1..M)
  • i: Item number (1..I, integer)
  • p: Process number (1..P, integer)
  • m: Machine number (1..M, integer)
  • t: Manufacturing time (1..20, integer)
  • r: Order number (1..R, integer)
  • e: Earliest start time (0,1.., integer)
  • d: Due date (0,1.., integer)
  • q: Manufacturing quantity (1,2.., integer)
HEADER M I P R BL
EVALUATIONFACTOR A_1 A_2 A_3 B_1 B_2 B_3
PRODUCTIONFACTOR C_1 C_2C_M
SETUPFACTOR D_1 D_2D_M
BOM i p m t
...
ORDER r i e d q
...
The number of BOM lines is BL、the number of ORDER lines isR.

Scheduling plan

For order r's process p's operation O_{rp}, an assignment is defined like this:

  • Machine: m (1,2..)
  • Setup start time: t_1 (0,1..)
  • Manufacturing start time: t_2 (0,1..)
  • Manufacturing end time: t_3 (1,2..)
  • *The setup end time is the manufacturing start time.*

Output

  • OL : Number of operations(1,2.., integer )
OL
m r p t_1 t_2 t_3
...
Output 1 + OL lines.

Constraints

  • BOM
  • Each item i's process p can utilize some or all types of machines, and manufacturing time t for one item is based on the machine used. The specifications are defined in the BOM input data. The BOM input data will have as many lines as the number of items i and processes p's usable machines.
  • An order's operations may also use the same machine multiple times. For example, after an order's process p finishes manufacturing using machine m, another process may use machine m again.
  • Scheduling start time
  • Scheduling start time is between t_1 and t_2 where 0 \leq t_1 and 0 \leq t_2
  • Machine capacity
  • Any machine m can be assigned to at anytime after the scheduling start time. There are no rest days nor break times. However each machine can only be assigned a maximum of one setup or manufacturing task at any one time.
  • Manufacturing time
  • Machine m has a manufacturing time mulitplier C_m defined, and the manufacturing time in an operation O_{rp} using machine m is calculated as t*q*C_m.
  • Setup time
  • Machine m has a setup time multiplier D_m defined, and setup time in an operation O_{rp} using machine m is calculated as (|Next item's number - Previous item's number|%3)*D_m. In other words, take the difference of the previous operation's and next operation's items' number, modulate it by 3, and then multiply by D_m. If there is no previous operation (which is the first operation assigned to the machine), the setup time is 0.
  • Setup start time
  • When p = 1, e \leq t_1.
  • When p \geq 2,t_{3r(p-1)} \leq t_{1rp}. (t_{3r(p-1)} is the previous process's operation O_{rp-1} manufacturing end time, t_{1rp} is the current process's operation O_{rp} setup start time.) In other words, you can not start the setup of the next process until the production in the previous process is completed.
  • The figure below is a diagram in which orders 1 and 2 consisting of two processes are assigned, gray part is the setup time. The setup time of operation O_{22} is NG on the left and OK on the right.
  • NG OK

  • Splitting is not allowed
  • Order's quantity q cannot be split into mulitple orders.
  • Operation's quantity q cannot be split into multiple operations.
  • Unassigned operations are not allowed.
  • All operations for all orders must be assigned.

Evaluation score

Any violation of the constraints results in a score of 0. When all constraints were fulfilled, the evaluation is calculated using the following formula:
 V  = 10^6  -  A_1 × Σ (Setup time^{B_1}) - A_2 × Σ (Time overdue^{B_2}) + A_3 × Σ (Assignment lateness^{B_3})
(When  V < 0 ,  V = 0 . Any decimals are discarded.)

  • V: Evaluation score, integer.
  • A_1: Setup time penalty multiplier
  • A_2: Overdue penalty multiplier
  • A_3: Assignment lateness bonus multiplier
  • B_1: Setup time exponent
  • B_2: Overdue exponent
  • B_3: Assignment lateness exponent
  • st = Order's first process's operation's t_1
  • et = Order's last process's operation's t_3
  • Setup time = t_2 - t_1 : For each operation
  • Time overdue = max( et - d,0 ) : For each order
  • Assignment lateness = min( st, d )- e : For each order

To maximize evaluation score V, create a schedule that minimizes setup times, and assign as late as possible while still meeting due dates. The reason late assignment is preferable is because in real life, it allows orders to be modified, as well as reduce the amount of time inventory sits in the warehouse. (In this question, orders will not get modified.)

The output evaluation program can be downloaded in this link: Download


Input example

HEADER 3 2 2 2 6
EVALUATIONFACTOR 1 5 0.1 1 1.1 1
PRODUCTIONFACTOR 3 2 1
SETUPFACTOR 1 1 1
BOM 1 1 1 1
BOM 1 1 2 1
BOM 1 2 3 1
BOM 2 1 1 1
BOM 2 1 2 1
BOM 2 2 3 1
ORDER 1 1 0 3 1
ORDER 2 2 1 4 1
  • *The process p = 1 of the item i = 1 can be assigned to the resource m = 1, 2 , the process p = 2 can be assigned only to the resource m = 3 . The same is true for i = 2 .
  • *A_1=1, A_2=5, A_3=0.1 are the weights given to setup times, late deliveries, and assignment lateness.
  • *B_2=1.1 is the exponent factor for late deliveries.

Output example 1

4
1 1 1 0 0 3
2 2 1 1 1 3
3 1 2 3 3 4
3 2 2 4 5 6

Example

  • Order 1: Due date d=3, final process's operation's t_3 = et = 4, setup time = 0, time overdue = 1, assignment lateness time = 0
  • Order 2: Due date d=4, final process's operation's t_3 = et = 6, setup time = 1, time overdue = 2, assignment lateness time = 0

Evaluation score V = 10^6 − 1 × 1^1 − 5 × (1^{1.1}+2^{1.1}) + 0.1 × 0^1 = 10^6 − 1 − 5 × ( 1 + 2.143… ) + 0 = 10^6 − 16.717... = 999983.282… = 999983

Output example 2

4
1 2 1 1 1 4
2 1 1 0 0 2
3 1 2 2 2 3
3 2 2 4 5 6

Example

  • Order 1: Due date d=3, final process's operation's t_3 = et = 3, setup time = 0, time overdue = 0, assignment lateness time = 0
  • Order 2: Due date d=4, final process's operation's t_3 = et = 6, setup time = 1, time overdue = 2, assignment lateness time = 0

Evaluation score V = 10^6 − 1 × 1^1 − 5 × (0^{1.1}+2^{1.1}) + 0.1 × 0^1 = 10^6 − 1 − 5 × 2.143… + 0 = 10^6 − 11.717… = 999988.282… = 999988

As output example 2's evaluation score V is higher, it is better than output example 1.


Input data

There are a total of 45 input data. Calculate the scheduling plans for all 45 input data, and the sum of all 45 evaluation scores V will be used to decide the ranking.