リニアプログラミングを使用したm台のジョブの計画

Question

リニアプログラミングを使用して問題を計画できると聞きました。リニアプログラミングは最適であり、大規模な計画（例えば、m台のマシン上のn個のジョブの計画）が指数関数的な困難を持っているため、実際にその方法を理解できません。

どうすれば100のジョブと10台の機械で線形計画を使って問題を解決できますか？あなたは私に何か説明をしたり、さらに読むことができますか？

Answer 1

したがって、100のジョブと10のマシンを線形プログラミングで問題をどのように解決できますか？

通常はできません。これは、リニアプログラミング（LP）が適用可能な計画上の問題ではありません。

LP問題では、解決したい変数があります。これらの変数の制約を表す線形不等式があります。そして、あなたは、与えられた解のコスト（または利益）を表すそれらの変数の線形関数を持っています（つまり、指数なし、除算なし、 "if-then-else"など）。

このような問題がある場合は、LPを使用して最適なソリューションを効率的に生成できます。ショップフロアスケジューリングは、あなたが尋ねていることのように、そのような問題ではありません。

LPは「より高いレベル」の計画に役立つ傾向があります。どの工場で各製品をどれくらい作りますか？このような問題では、LPを使用するために必要なように、線形不等式として制約を指定し、線形関数としてコスト（または利益）を指定できることがよくあります。注意して、私は「どれくらいの製品がどれくらい...」と言っていますが、「どれくらい...」とは言いませんでした。それはLPのもう一つの制限です - 変数は実際の値をとることができなければなりません。整数ソリューションを提供するソリューションが必要な場合は、整数プログラミング（または混合整数プログラミング）の問題があります。