bevorzugte Sequenz-Algorithmus in T-SQL

Question

ERKLÄRUNG

Ich bin mit SQL Server 2012. Ich brauche Algorithmus zu schreiben Sequenz zur Herstellung von Produkten, zu entscheiden, auf ihre Rüstzeiten abhängig.

Was ich meine: zum Beispiel müssen wir 4 Produkte produzieren: ABCD

Ich habe eine Matrix (Tabelle Changeover), gefüllt mit Rüstzeiten von jedem Produkt wie folgt aus:

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 

Regeln:

• Wenn zuerst produzieren wir das Produkt A, und nachdem wir das Produkt B produzieren werden, wird es eine 10 Minuten Rüstzeit sein ...

• Wenn zuerst produzieren wir das Produkt A, und nachdem wir Produkt C produzieren werden, wird es eine 15 Minuten Rüstzeit sein ...

• Wenn wir zuerst das Produkt B produzieren, und nachdem wir Produkt produzieren A, wird es eine 5 Minuten Rüstzeit sein ...

und so weiter ....

Wunsch Ausgabe:

Ziel ist es zur Herstellung von Produkten mit kürzester Zeit zu machen Sequenz. Also mit diesen Beispieldaten wäre es:

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

Dieser Ausgang ist falsch: Products

Product Rank 
A   1 
B   2 
C   3 
D   4 

Rang Wert in der Tabelle:

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

ich eine andere Tabelle Products mit Daten so habe sagt Sequenz von produzierenden Produkten, so mit dieser Probensequenz wäre:

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

Es ist also falsch, weil die gesamte Setup-Zeit 35 Minuten beträgt.

Ergebnisse Gewünschte: Ich Algorithmus müssen die Products Tabelle so aktualisieren:

Product Rank 
A   3 
B   4 
C   1 
D   2 

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

Haben Sie Ideen, wie dies geschehen könnte?(Tatsächlich gibt es mehr als 140 Produkte)

Beispieldaten:

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); 

Was ich habe versucht: Ich kann niedrigste Rüstzeit jeder Gruppe erhalten in folgenden:

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 

Und ich bekam folgende Ausgabe:

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 

was falsch ist, weil ich in dieser Folge nicht produzieren kann:

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

Ich hoffe, ich erklärte es klar, wenn Sie irgendwelche Fragen oder missverstanden haben, fragen Sie mich einfach, ich werde weitere Informationen zur Verfügung stellen.

Answer 1

Wenn Sie vier Produkte Sie tun können:

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; 

Dies ist eine Brute-Force-Algorithmus in SQL implementieren. Im Allgemeinen ist dies das Beste, was Sie mit einer einzigen Abfrage tun können.

Die join s garantieren, dass die Reihenfolge möglich ist. Die not in garantiert, dass neue Links in der Kette nicht zu einem früheren Produkt zurückkehren.

Wenn Sie mehr Produkte haben, können Sie die Abfrage für die Anzahl der Produkte, die Sie haben, anpassen. Alternativ können Sie eine rekursive Unterabfrage einrichten. Ich wäre jedoch vorsichtig. Bis Sie 10 Produkte bekommen, wird dies wahrscheinlich unerschwinglich teuer.

Bei einem großen Problem könnten Sie sich andere Arten von Optimierungsalgorithmen (die wahrscheinlich ungefähr sind) mit einer Graphdatenbank oder einer erweiterten Analysesoftware ansehen.