ジョブショップのスケジューリング：どのソリューションを考慮する必要がありますか？

Question

開発者が異なるプロジェクトの番号 でチームで作業するソフトウェア会社があるとします。プロジェクトには、割り当てられた デベロッパーのスキルが必要です。私の目的のために、私はそれを単純にしておき、1つの スキル、すなわちプログラミング言語に制限したいと考えています。したがって、Javaを必要とするプロジェクトもあれば、 などが必要なプロジェクトもあります。プロジェクトの期間は固定されており、各プロジェクトには2人の開発者が割り当てられます。

いずれの時点でも、いくつかのプロジェクトが進行中で、新しいプロジェクトは になり、将来、ある時点で計画する必要があります。私は開発者がどんなプロジェクトにいつ取り組むべきかのスケジュールを計算したいと思います。

私は最適な解決策を探していません（それが可能でも）。私は人間のマネージャーが作成できるスケジュールで内容が です。

私はリソース制限付きスケジューリング問題 と割り当て問題についての記事を読んだことがありますが、正式なCSトレーニングはほとんどありません。これらの問題のさまざまなバリエーションですべてのニュアンスが失われることがよくあります。

私の問題は、ジョブが プロジェクトであり、開発者がマシンなので、ジョブショップスケジューリングの単純なバリエーションだと思うので、ジョブは複数のマシンを同時に にする必要があります。実行中のプロジェクト は中止できないため、最初に終了する必要があるという点で、先例制約は1つしかありません。

遺伝的アルゴリズムを使用する傾向があります。主に私が で良い結果を得ている人を読んでいて、他のプロジェクトに使用していたためです。 。 リニアプログラミングでも良い結果が得られましたが、それについてはほとんどわかりません。

遺伝的アルゴリズムは、このタイプの問題の実現可能なソリューションですか？または、より良い解決策がありますか？

Answer 1

一方の側の開発者ともう一方の側に必要なプロジェクトメンバーからなる2部グラフを作成します。 「必要なプロジェクトメンバー」とは、プロジェクトPが3人の開発者を必要とする場合、おそらくP0、P1、P2という3つのノードを追加するということです。

開発者とそのプロジェクトが必要とするすべてのスキルを持っている場合は、必要なプロジェクトメンバーとの間にエッジを描きます。あなたの問題は、このグラフの中でmatchingを見つけるまで減らされます。これを行うために使用できる標準的なアルゴリズムがあります。

Answer 2

遺伝的アルゴリズムを使用することは実現可能なアプローチですが、非常に野心的です。

greedy algorithmで始まります。