0

特定の問題で問題が発生しています。14日間で5人の従業員が働くようにスケジュールする必要があります。各従業員は14日のうち9日しか働けず、毎日3人の従業員がスケジュールされている必要があります。重要な部分は、各従業員が特定の日に働くことに対して与えられたペナルティを持っているということです。したがって、その日に仕事ができない場合は、ペナルティが10になります。ペナルティがゼロであってもかまいません。最後に、ペナルティが5になりたくない場合は、ペナルティが10になります。

毎日の各従業員のペナルティ値のマトリックスがあります。私は自分の制約を書き出す方法を見つけようとしています。

マトリックスA（ペナルティマトリックス）とマトリックスB（スケジュールマトリックス）とマトリックスC（C（i、j）= A（i、j）* B（i、j））を作成することを考えました。この設定では、A（i、j）が0に等しい（従業員が働いていない）場合、ペナルティは考慮されません。その逆も同様です。

だから私は私の制約として言うことができます：

A（1,1）+ A（1、m）+ A（1、n）<= 9

と

A（1,1）+ A（m、1）+ A（n、1）= 3

そして私は最小化しています：C（1,1）+ C（m、m）+ C（n、n）

このように見る際の私の問題は、これを最適化アルゴリズムで使用しようとすることです。シンプレックスアルゴリズムはLPの問題を解決できるはずですが、最も遅くなる可能性があります。私は立ち往生していて、これを間違った方法で見ていると確信しています。誰かが私に新鮮な目と、おそらく私がこれを間違った方法で見ている理由についての説明を与えることができれば、私はそれをいただければ幸いです。

4

1 に答える 1

0

モデリングを間違えたため、問題が必要以上に難しくなったと思います。

ペナルティ関数を使用して、「可能で喜んで」、「可能であるが不本意」、「不可能」をモデル化するのはなぜですか。従業員が仕事をすることはできるが、仕事をしたくないというタイムスロットが従業員に割り当てられる回数を最小限に抑えたいだけではありませんか？（もちろん、彼らが働くことができないスロットを従業員に割り当てることなしに？）

上で提案したように問題を修正すると、これは単純な最小コストフロー問題としてモデル化できます。従業員用に1セットのノードがあり、タイムスロット用に1セットのノードがあります。従業員がそのタイムスロットで作業できる場合は、容量1のエッジを持つタイムスロットに従業員を接続します。従業員がその時点で働く意思がある場合は0のコストを、従業員がその時点で働く意思がない場合は1のコストを与えます。ソースとシンクを追加します。ソースには、キャパシティ9（作業できる日数）とゼロコストの各従業員に対するエッジが必要です。一方、各タイムスロットには、キャパシティ3とゼロコストのシンクに対するエッジが必要です。

最小コストフローソルバーを最初からコーディングするのは比較的簡単です。

タイムスロットに2人以上の不本意な従業員が配置されることを禁止したい場合は、問題を整数計画としてモデル化することに固執していると思います。 GLPKは、無料の線形および整数計画ソルバーです。最先端ではありませんが、多くの問題に対して非常にうまく機能します。あなたのような小規模なインスタンスを解決するのに問題があるとは思えません。

于 2013-02-19T18:58:22.593 に答える