しばらくの間、私を悩ませている問題があります。
「ワーカー」w_0、w_1 ... w_n、およびタスク t_0、t_1、... t_m、および期間 D_ij があり、w_i はその時間数で t_j を完了することができます。各ワーカーには、最大 m_0,m_1... m_n 勤務できる時間数もあります。
複数の作業者が、比例配分された工数で同じタスクに取り組むことができます。たとえば、D_11 = 2 かつ D_21 = 4 の場合、ワーカー 1 はタスク 1 でワーカー 2 の 2 倍効率的です。したがって、たとえば、1 時間の 1 時間と 2 時間の 2 時間でタスクを完了することができます。
すべてのタスクを完了できる最小時間数をどのように決定できますか。
貪欲な手法を使用して、各タスクに最適なワーカーを選択しようとしましたが、それはすべてのケースで機能しません。たとえば、ワーカー 1 がタスク 1 を 2 時間で、タスク 3 を 4 時間で完了できるとします。ワーカー 1 がタスク 1 に取り組むために選択されることは明らかですが、タスク 3 は他のワーカーにとって非常に時間がかかり、ワーカー 1 はその仕事に最適だったとしましょう。
問題を割り当て問題に減らすことを考えましたが、方法を見つけることができませんでした。
この問題はどのように解決できますか?