好ましい配列アルゴリズム

Question

私は彼らのセットアップ時間に応じた製品を製造する順序を決定するアルゴリズムを記述する必要がEXPLANATION

私は、SQL Server 2012を使用しています。

は、私が何を意味：ABCD私が行列を持って

そのように各製品のセットアップ時間で満たされた（表Changeover）：

Xasis Yasis Time 
-------------------- 
A  B  10 
A  C  15 
A  D  5 
B  A  5 
B  C  20 
B  D  10 
C  A  10 
C  B  15 
C  D  5 
D  A  0 
D  B  5 
D  C  25 

ルール：

例えば、我々は4つの製品を生産する必要があります

• 最初に製品Aを生産し、製品Bを生産した後、10分のセットアップ時間があります。

• 我々は、製品Aを生産し、我々は製品Cを生成します後、15分のセットアップ時間があるでしょう最初の場合は...

• 我々は製品Bを生産する最初の場合は、我々は製品を生産ます後...ように

とを.... 5分のセットアップ時間があるでしょう

所望の出力：

目標は最短時間で製品を製造するシーケンスを作ることです。このサンプルデータを持つので、それは次のようになります。

5  0  10  (Total 15 minutes) 
C ----> D ----> A ----> B 

この出力が正しくありません：テーブルProductsで

Product Rank 
A   1 
B   2 
C   3 
D   4 

ランク値：

15  10  0  (Total 25 minutes) 
C ----> B ----> D ----> A 

私はそのようなデータを別のテーブルProductsを持っています製品を生産する順序を示しているので、このサンプルシーケンスでは、

10  20  5  (Total 35 minutes) 
A ----> B ----> C ----> D 

合計セットアップ時間が35分であるため、間違っています。

望ましい結果：私はそのようなProductsテーブルを更新するためのアルゴリズムを必要とする：

Product Rank 
A   3 
B   4 
C   1 
D   2 

    5  0  10  (Total 15 minutes) 
C ----> D ----> A ----> B 

あなたはこれを行うことができる方法任意のアイデアを持っていますか？

サンプル・データ（実のために140以上の製品があります）：

CREATE TABLE #Attr 
(
    Id NVARCHAR(20), 
    [Rank] INT 
) 

INSERT INTO #Attr (Id, [Rank]) 
VALUES ('A',1), ('B',2), ('C',3), ('D',4) 

CREATE TABLE #Change 
(
    Xasis NVARCHAR(20), 
    Yasis NVARCHAR(20), 
    [Time] INT 
) 

INSERT INTO #Change (Xasis, Yasis, [Time]) 
VALUES ('A','B',10), ('A','C',15), ('A','D',5), 
     ('B','A',5), ('B','C',20), ('B','D',10), 
     ('C','A',10), ('C','B',15), ('C','D',5), 
     ('D','A',0), ('D','B',5), ('D','C',25); 

私が試したもの：

WITH filtered AS 
(
    SELECT 
     *, 
     ROW_NUMBER() OVER(PARTITION BY Xasis ORDER BY [Time]) AS RankPerGroup 
    FROM #Change AS c 
) 
SELECT 
    *, ROW_NUMBER() OVER(ORDER BY [Time]) AS [Rank] 
FROM filtered f1 
WHERE RankPerGroup = 1 

と私：私は、次の各グループの最低のセットアップ時間を得ることができます次の出力を得ました：

Xasis Yasis Time RankPerGroup Rank 
D  A  0  1    1 
A  D  5  1    2 
B  A  5  1    3 
C  D  5  1    4 

私はその順序で生産することができません：

0  D already produced, so that's incorrect 
D ----> A --X--> D --- 

私はそれを明確に説明してくれました。ご質問やご迷惑をおかけした場合は、私に詳細情報をお送りください。

Answer 1

あなたが行うことができます4つの製品をお持ちの場合：

select co1.Xasis as x1, co2.Xasis as x2, co3.Xasis as x3, co3.Yasis as x4, 
     (co1.time + co2.time + co3.time) as total_time 
from changeover co1 join 
    changeover co2 
    on co1.Yasis = co2.Xasis join 
    changeover co3 
    on co2.Yasis = co3.Xasis 
where col2.Xasis not in (col1.Yasis) and 
     col3.Xasis not in (col1.Yasis, col2.Yasis) and 
     col3.Yasis not in (col1.Xasis, col2.Xasis, col3.Xasis) 
order by total_time desc; 

これは、SQLでのブルートフォースアルゴリズムを実装しています。一般的に、これは1つのクエリで実行することができます。

joinは、シーケンスが可能であることを保証しています。 not inは、チェーン内の新しいリンクが以前の製品に戻らないことを保証します。

さらに多くの製品をお持ちの場合は、お持ちの製品数のクエリをカスタマイズできます。また、再帰的サブクエリを設定することもできます。しかし、私は注意が必要です。あなたが約10の製品を手に入れる時には、これはおそらく非常に高価になります。

大きな問題がある場合は、グラフデータベースまたは高度な分析ソフトウェアを使用して、他の種類の最適化アルゴリズム（おそらくおおよそのもの）を調べることをお勧めします。