確かにあなたの仕事の多くは、スケジューリング理論の問題に関連する計画の問題を解決する必要性に出くわしました。 アルゴリズム自体に影響を与えることなく、このようなプログラムの作業を高速化する方法を説明したいと思います。
これらの問題を解決するには、さまざまなヒューリスティックな近似アルゴリズムとブルートフォース削減アルゴリズムを組み合わせて使用することで、膨大な数のアプローチが実装されています。 人生では、すべての実装は企業の詳細に非常に依存しているため、別のソリューションを掘り下げることなく、結果を構築する時間を短縮する一般的な手順を検討します。
「投稿によるジョブの分散」という非常に重要なタスクを実行してください。 また、一連の作品を作成して計画に送信するユーザー。 そして、彼は1つではなく2つのオプションを引き出す必要がありますが、その日のすべての可能な間隔を引き出します。 つまり この作品セットを8.00に固定することが可能かどうかを言いますか？ そして、8.30で？ そして、一日中。
データ構造
各投稿は、実行できる作業の種類によって特徴付けられます。 各投稿では、作業間隔がわかっています（つまり、休憩やその他の作業で占有されていない期間）。 計画された各作業は、時間と種類の標準によって特徴付けられます。
サーバーからの空きギャップに関する情報は、次のようなプレートにドラッグされます。
作品は次の構造のリストに保存されます。
private class JobTypes { public JobTypes(int jId, TimeSpan time, int type, string job_code = "0") { this.JobId = jId; this.JobRuntime = time; this.JobType = type; this.JobCode = job_code; } public int JobId { get; private set; } public TimeSpan JobRuntime { get; private set; } public int JobType { get; private set; } public string JobCode { get; set; } }
同じタイプの複数のジョブを連続して実行する場合、それらを別の投稿に転送することは望ましくない状況であり、時間のリソースがかかります。 計画するとき、計算されたスケジュールの品質を決定する「パスの重み」の概念を導入することは理にかなっています。 投稿間の遷移ごとに重みが増し、不適切な種類の投稿でのパフォーマンスごとに全体的なスケジュールがさらに重くなります。 また、取得された完了時間と基準との差、選択された投稿の作業負荷、および顧客の要求に応じた要因の束が、重量に影響を与える可能性があります。
ユーザーが可能なスケジュールのみを表示する必要がある場合は、簡単な近似方法を使用して実行します。 ただし、重みが最も低いスケジュールを表示する必要がある場合は、検索メソッドのメソッドを実装する必要があります。 この方法の期間は、ジョブの数に応じて指数関数的に増加します。 したがって、1〜2個のジョブを含むスケジュールの作成速度が100分の1秒以内に、4〜5個が10分の1以内に変化する場合、20分以上の小さなジョブを含むスケジュールを数分で計算できます。 もちろん、すべての数値は概算であり、状況に大きく依存していますが、一般的な原則は明確です。
ビルドアビリティチェック
プログラムの作業時間を短縮できる最初のステップは、計算する前にワークショップリソースを確認することです。 計画された作業のタイプと各作業を完了する時間は既知であり、ワークショップのスケジュールと構成は既知です。 したがって、空き時間と空き時間を指定せずに、各タイプの投稿の合計空き時間を取得し、対応するタイプの作業の合計期間に課す必要があります。 時間が足りない場合、選択した時間にスケジュールを作成できないことは明らかです。ワークショップに十分なリソースがなく、別の日を選択するようにというメッセージをユーザーに送信します。
private bool CheckPeriodsAvailable(SchData sch_data) { var jTime = from s in sch_data.jobs group s by new { jType = s.JobType } into g select new { g.Key.jType, qty = g.Sum(s => s.JobRuntime.TotalMinutes) }; var pTime = (from s in (sch_data.BasicData.Tables["MonthFree"]).AsEnumerable() group s by new { jType = s.Field<int>("JobType") } into g select new { g.Key.jType, qty = g.Sum(s => (s.Field<DateTime>("FinTime") - s.Field<DateTime>("StartTime")).TotalMinutes) }).ToList(); foreach (var j in jTime) { double p = pTime.Find(item => item.jType.Equals(j.jType)).qty; if (j.qty > p) return false; } return true; }
それでもリソースが見つかった場合は、2番目のステップである検索の削減に進みます。 最小重量のソリューションが、各タイプの作業が中断することなく1つのポストでのみ実行されるようなソリューションであることは明らかです。 人生では、これはサービスセンターのマシンが1つのポストで処理され、ワークショップの周りに引きずられないという事実に表れています。 作業を後で開始する必要がある可能性がありますが、ここでは、遅延の重みをマシンの転送の重みと比較し、2つの悪の小さい方を選択する必要があります。
反復回数を減らす
計画プロセスの開始前に、すべての作業は作業の順序でタイプごとにグループ化された単一のブロックに結合されます。 タスクの条件がタスクの依存性について述べていない場合（つまり、i + 1が終了する前にその作業i + 2を完了できない場合）、タイプ別に予備作業をソートします。 各ブロックの期間は、ブロックに含まれるすべての作品の合計期間に等しいと見なされます。
したがって、最も単純なケースでは、20の小さな作品ではなく、1つの長い作品が計画のために送られます。 実行時間の違いについては前述しました。 結合された作業の表示されたパスはすべて、決定ツリーに保存する必要があります。 結果が負の場合、グループ化密度を徐々に減らし、ツリーに既に追加されているパスを検索エリアから削除する必要があります。
必要な最小の重みを持つパスが見つかるとすぐに、検索プロセスを停止し、グループを個別の作品に分割して、いつどの作品が実行されるかについての情報を提示します。
private List<PeriodElems> SeparateSch(List<PeriodElems> resultList, List<JobTypes> jobs, DataTable PostsData) { int j = 0; while (j < resultList.Count) { if (((j) < jobs.Count) && (resultList[j].time > jobs[j].JobRuntime) && (resultList[j].type == jobs[j].JobType)) { PeriodElems ins_elem = resultList[j].Clone(); // , var periods = from item in (PostsData).AsEnumerable() where item.Field<int>("PostId") == resultList[j].post_id && ( (item.Field<DateTime>("StartTime") <= resultList[j].start && item.Field<DateTime>("FinTime") > resultList[j].start) || (item.Field<DateTime>("StartTime") > resultList[j].start && item.Field<DateTime>("FinTime") < resultList[j].fin) || (item.Field<DateTime>("StartTime") < resultList[j].fin && item.Field<DateTime>("FinTime") >= resultList[j].fin) ) select item; DataView OldMonthRows = periods.AsDataView<DataRow>(); if (OldMonthRows.Count == 0) { return null; } // - ok, , . TimeSpan shift_time = OldMonthRows.Count == 1 ? jobs[j].JobRuntime : GetShiftTime(jobs[j].JobRuntime, OldMonthRows, DateTime.Parse(OldMonthRows[0]["FinTime"].ToString()) - resultList[j].start); // - TimeSpan delta = DateTime.Parse(OldMonthRows[0]["StartTime"].ToString()) - ins_elem.start; if (delta > TimeSpan.Zero) { resultList[j].start += delta; resultList[j].fin += delta; } ins_elem.start = resultList[j].fin = resultList[j].start + shift_time; if (!ins_elem.start.Equals(ins_elem.fin)) resultList.Insert(j + 1, ins_elem); } j++; } return resultList; }
難点は、ワークショップが中断される可能性があるという事実にあります。作業が中断された場合は、中断を考慮する必要があります。 この場合、作業の開始が休憩に該当しないことを確認する必要があります。作業が終了した場合、次の作業期間まで延長されます。
private TimeSpan GetShiftTime(TimeSpan jTime, DataView OldMonthRows, TimeSpan fndTime) { TimeSpan sftTime = jTime; if (OldMonthRows.Count > 0) { //, . if (fndTime < sftTime) { sftTime = fndTime + TimeSpan.FromMinutes(Convert.ToInt32(OldMonthRows[0]["TimeToNext"])); for (int per_numb_s = 1; per_numb_s < OldMonthRows.Count - 1; per_numb_s++) { if (fndTime >= jTime) break; fndTime += Convert.ToDateTime(OldMonthRows[per_numb_s]["FinTime"]) - Convert.ToDateTime(OldMonthRows[per_numb_s]["StartTime"]); sftTime += Convert.ToDateTime(OldMonthRows[per_numb_s]["FinTime"]) - Convert.ToDateTime(OldMonthRows[per_numb_s]["StartTime"]) + TimeSpan.FromMinutes(Convert.ToInt32(OldMonthRows[per_numb_s]["TimeToNext"])); } sftTime += jTime - fndTime; } } return sftTime; }
上記のアプローチを使用する場合、常に障害が発生する可能性があることを理解する必要があります。その場合、計画を通じて標準スキームに従って作業セットを排除する必要がありますが、合計時間がより多く費やされます。 私の場合、顧客は10個すべてを少しずつ苦しめるよりも10回に1回苦しむ方が良いと判断し、この方法には青信号が与えられました。
視覚的に非常に高速化するには、計算全体を個別のストリームに入れ、計算された時間間隔ごとにイベントをヤンクする価値があります。 クライアントは、イベントにサインアップして、計算が完了する前にユーザーに結果を提供します。 また、進行状況バーを表示して、コンピューターの人がすべてが機能していること、何もぶら下がっていないこと、神経質になっていないことを理解できるようにすることも役立ちます。 また、クライアントと一緒に仕事をする場合（たとえば、サービスセンターで車を録音する場合）、彼はすでに午前中に録音の最初の提案を発表しています。
いつか私の記事に記載されていることが役に立つことを心から願っています。 ご清聴ありがとうございました。