0

私は車の修理サービス店を持っています, 多くのサービスがあります (診断, エンジン修理. 電気修理...) 順序の保存は問題ではありません

次に、現在の 1 台の車が 1 つのサービスに必要な時間を把握します。たとえば、次のようになります。

  1. フォード - 診断に 120 分、エンジンに 360 分、電気修理に 80 分
  2. BMW - 診断に 90 分、エンジンに 480 分、電気修理に 140 分
  3. メルセデス - 診断に 90 分、エンジンに 42 分、電気修理に 160 分

などなど、車の大きなリストがあります。

それで、サービスボックスに車を最適に割り当て、ボックスの時間を無駄にせず、車の待ち時間を最小限に抑えて最良の結果を得るための優れたアルゴリズムまたは数式はありますか.

4

2 に答える 2

2

これはいわゆる「オープンショップ」問題の一例です。Job Shop Scheduling との違いは、後者ではジョブがマシン上で実行される順序が関連することですが、これはあなたの例には当てはまりません。

残念ながら、問題はあなたのケースでは NP 困難です。(2 台のマシンの場合は、多項式時間で解決できます。) 絶望する必要はありません。問題のサイズに合わせて適切に機能するアルゴリズムが多数あるためです。

ウィキペディアには、「Open-Shop Scheduling」の下にいくつかの適切な出発点があり、この分野の古典的な論文を参照しています。

于 2012-12-07T20:42:13.280 に答える
0

あなたの問題は、「Job-Shop Scheduling」問題または単に「Shop-Scheduling」と呼ばれることもあります。変数の数が増えると非常に難しくなるため、広く議論されています (「NP-Hard」問題と呼ばれるものです)。

簡単な答えはありませんが、計算時間と引き換えに精度を追求する優れたアルゴリズムがいくつかあります。リソースとして Dorit Hochbaum が編集した本「NP 困難な問題の近似アルゴリズム」をお勧めします。

于 2012-12-07T20:27:40.257 に答える