Preferred Sequence Algorithm in T-SQL

Question

EXPLANATION

I'm using SQL Server 2012. I need to write algorithm to decide sequence of producing products depending on their setup times.

What I mean: for example we need to produce 4 products: A B C D

I have a matrix (table Changeover) filled with setup times of each product like that:

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

Rules:

• If first we produce product A, and after we'll produce product B, there will be a 10 minute setup time...

• If first we produce product A, and after we'll produce product C, there will be a 15 minute setup time...

• If first we produce product B, and after we'll produce product A, there will be a 5 minute setup time...

and so on....

Desired output:

Goal is to make sequence of producing products with shortest time. So with this sample data It would be:

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

This output is incorrect:

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

I have another table Products with data like that:

Product    Rank
A          1
B          2
C          3
D          4

Rank value in table Products tells sequence of producing products, so with this sample sequence would be:

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

So it's incorrect, because total setup time is 35 minutes.

Desired results: I need algorithm to update the Products table like that:

Product    Rank
A          3
B          4
C          1
D          2

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

Do you have any ideas how this could be done? (for real there are over 140 products)

Sample data:

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

What I've tried: I can get lowest setup time of each group in following:

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

And I got following output:

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

Which is incorrect that because I can't produce in that sequence:

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

Hope I explained It clear, If you have any questions or misunderstood me, just ask me I'll provide more information.

Answer 1

If you have four products you can do:

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;

This is implementing a brute force algorithm in SQL. In general, this is the best you can do with a single query.

The joins are guaranteeing that the sequence is possible. The not in guarantee that new links in the chain do not return to a previous product.

If you have more products, you can either customize the query for the number of products that you have. Alternatively, you can set up a recursive subquery. However, I would be careful. By the time you get around 10 products, this will probably become prohibitively expensive.

For a large problem, you might want to look at other types of optimization algorithms (which would probably be approximate), using a graph database or advanced analytic software.