担当者・機械への最小費用割当

担当者や機械と作業の対応を、費用と適格条件から最適化する。

作業数は担当数以下にしてください。費用は各割当の総額(円)とし、勤務時間・工程順序・能力制限は考慮しません。

入力すると自動で計算します。Enterで次の項目へ進めます。次の入力欄を選んで進めます。

必要な入力・選択は3項目です。

担当者・機械(匿名ID)必須
行担当ID操作
1
2

1列を左端の欄へタブ区切りで貼り付けられます。16行まで。

英数字で識別します。最大16件。同じ担当が複数の作業を担当することはできません。

作業(匿名ID)必須
行作業ID操作
1
2

1列を左端の欄へタブ区切りで貼り付けられます。12行まで。

最大12件。すべての作業にちょうど1件の担当を割り当てます。

割当費用と適格条件必須
行担当ID作業ID適格条件費用(円) 任意操作
1
2

4列を左端の欄へタブ区切りで貼り付けられます。192行まで。

登録済みの全「担当×作業」を1行ずつ入力します。割当可能は整数円(0円可)、割当不可は費用を空欄にします。表へのTSV貼り付けも使えます。


計算結果

必要な値を入力すると自動で計算します。

お気に入り一覧

計算方法・適用範囲・出典

計算方法

xᵢⱼ∈{0,1}を担当iと作業jの割当とし、費用cᵢⱼについて ΣᵢΣⱼ cᵢⱼxᵢⱼ を最小化。各作業jでΣᵢxᵢⱼ=1、各担当iでΣⱼxᵢⱼ≤1、割当不可の組はxᵢⱼ=0。実装は作業の割当済み集合を状態とする動的計画法で、許容範囲内の厳密最小値を求めます。

全作業を一対一で割り当てる最小合計費用、作業別の担当ID・費用、未割当担当。

計算例(架空の数値)

Google OR-Toolsの公開例:5担当×4作業の最小合計費用は265(資料中の無単位の数値例。円建て換算は利用者の仮定です)。

適用対象と限界

各作業をちょうど1担当に配分し、担当側は最大1作業を受け持つ独立作業。費用はユーザー定義の円単位。複数作業を同一担当へ割当、担当の能力・時間制約、工程の開始時刻・順序、割当外注、分割・輸送、負の費用、小数金額、未完了作業の許容、作業数12件超は扱いません。。

方法と出典

方法:E290-exact-subset-dp-v1.0 (2026-11-13)。データ記録日:2026-11-13。