6

I would like to ask for help coming up with a query, which can identify groups on non-overlapping records. Here is a sample scenario (admittedly contrived). Let's say I have employees who are assigned to work on various projects. While an employee can be assigned to multiple projects, he/she can only work on one project at any given time (don't you wish we all had this luxury :). I need to find out which projects can be scheduled to be worked on in parallel because they do not share any employees. Here is some code to setup sample tables and data.

--1. Create #Projects table
IF OBJECT_ID('tempdb..#Projects') IS NOT NULL 
    DROP TABLE #Projects

CREATE TABLE #Projects (
    ProjectId INT,
    ProjectName VARCHAR(16)
    )

INSERT INTO #Projects ( ProjectId, ProjectName )
VALUES  ( 1, 'Project 1'), ( 2, 'Project 2'), ( 3, 'Project 3'), ( 4, 'Project 4'), ( 5, 'Project 5'),
        ( 6, 'Project 6'), ( 7, 'Project 7')

--2. Create #Employees table
IF OBJECT_ID('tempdb..#Employees') IS NOT NULL 
    DROP TABLE #Employees

CREATE TABLE #Employees (
    EmployeeId INT,
    EmployeeName VARCHAR(16)
    )

INSERT INTO #Employees (EmployeeId, EmployeeName)
VALUES (101, 'Employee 101'), (102, 'Employee 102'), (103, 'Employee 103'), (104, 'Employee 104'), 
        (105, 'Employee 105'), (106, 'Employee 106'), (107, 'Employee 107')

--3. Create #Employee_Projects table
IF OBJECT_ID('tempdb..#Employee_Projects') IS NOT NULL 
    DROP TABLE #Employee_Projects

CREATE TABLE #Employee_Projects (
    ProjectId INT,
    EmployeeId INT
    )

INSERT INTO #Employee_Projects (ProjectId, EmployeeId)
VALUES (1, 101), (1, 105), (1, 107), (2, 102), (2, 103), (2, 107), (3, 104), (3, 105),  (3, 106), (4, 100), (4, 101), (4, 102), (5, 103), (5, 104), (6, 105), (6, 106), (7, 106), (7, 107), (8, 102), (8, 104), (8, 106)

And here is the query, which will show you the employees and projects we have created:

SELECT p.ProjectId, p.ProjectName, e.EmployeeId, e.EmployeeName
FROM #Projects p
JOIN #Employee_Projects ep ON ep.ProjectId = p.ProjectId
JOIN #Employees e ON e.EmployeeId = ep.EmployeeId
ORDER BY ep.ProjectId, e.EmployeeId

Our data looks like this:

ProjectId   ProjectName      EmployeeId  EmployeeName
----------- ---------------- ----------- ----------------
1           Project 1        101         Employee 101
1           Project 1        105         Employee 105
1           Project 1        107         Employee 107
2           Project 2        102         Employee 102
2           Project 2        103         Employee 103
2           Project 2        107         Employee 107
3           Project 3        104         Employee 104
3           Project 3        105         Employee 105
3           Project 3        106         Employee 106
4           Project 4        101         Employee 101
4           Project 4        102         Employee 102
5           Project 5        103         Employee 103
5           Project 5        104         Employee 104
6           Project 6        105         Employee 105
6           Project 6        106         Employee 106
7           Project 7        106         Employee 106
7           Project 7        107         Employee 107
8           Project 8        102         Employee 102
8           Project 8        104         Employee 104
8           Project 8        106         Employee 106

Visually we can tell that, for example, we can schedule projects 1, 2, 3 to run at the same time because they do not share any employees. Let's call this group of projects "Group 1". After that we could schedule projects 4, 5, 6. Let's call it "Group 2". Finally, in our example we have project 7 left and this would be our "Group 3". My question is, how can I write a T-SQL query to perform such grouping of projects?

Thank you!

4
  • Employee 107 of Project7 is not a sharing employee so it could be part of group1?
    – AA.SC
    Dec 22, 2014 at 6:55
  • You're right, Project7 can be part of Group1.
    – SQL_Guy
    Dec 22, 2014 at 7:45
  • Actually I take this back. Project 7 can't be part of Group 1 because of the Employee 106 who also participates in Project 3, which is a part of Group 1 already. Therefore these projects (7 and 3) cannot be concurrent.
    – SQL_Guy
    Dec 22, 2014 at 7:59
  • 1
    This question is for SQL Server 2014 (I also added a tag). For the purposes of this question, let's say that the goal is to optimize for the minimum number of groups (so that as many projects as possible are carried out at the same time). Thank you!
    – SQL_Guy
    Dec 22, 2014 at 17:22

2 Answers 2

6

This is a sort of bin-packing problem, so you'll most likely need to choose from one of the available approximate solutions, rather than attempting an exhaustive search.

One very straightforward idea is to pack projects into groups choosing the project with the largest number of employees each time. As soon as the current project no longer fits into the current group, we start a new group.

This is relatively easy to express iteratively, though it may not perform well, depending on the characteristics of the real data set. It might be quite challenging to express the same logic in a single T-SQL statement. Anyway, as an example, here is an iterative T-SQL solution using the simple greedy algorithm outlined above:

SET NOCOUNT ON;
CREATE TABLE #Groups 
(
    GroupID integer NOT NULL, 
    ProjectID integer NOT NULL, 

    CONSTRAINT PK_Groups
    PRIMARY KEY (GroupID, ProjectID)
);

-- First group
DECLARE @GroupID integer = 1;

-- Choose the largest project to start with
-- and assign to group 1
INSERT #Groups
SELECT TOP (1) 
    @GroupID AS GroupID,
    P.ProjectId
FROM #Projects AS P
GROUP BY 
    P.ProjectId
ORDER BY 
    COUNT_BIG(*) DESC,
    NEWID(); -- Random order tie-breaker

WHILE 1 = 1
BEGIN
    -- Add the next largest project to the current group
    INSERT #Groups
    SELECT TOP (1) 
        @GroupID AS GroupID,
        P.ProjectId
    FROM #Projects AS P
    WHERE NOT EXISTS
    (
        -- Project not already allocated to a group
        SELECT * 
        FROM #Groups AS G
        WHERE G.ProjectID = P.ProjectId
    )
    AND NOT EXISTS
    (
        -- Employees for this project
        SELECT EP2.EmployeeId
        FROM #Employee_Projects AS EP2
        WHERE EP2.ProjectId = P.ProjectId

        INTERSECT

        -- Employees already in the current group of projects
        SELECT EP.EmployeeId
        FROM #Groups AS G2
        JOIN #Employee_Projects AS EP
            ON EP.ProjectId = G2.ProjectID
        WHERE G2.GroupID = @GroupID
    )
    GROUP BY P.ProjectId
    ORDER BY 
        COUNT_BIG(*) DESC,
        NEWID(); -- Random order tie-breaker

    -- No project found for this group
    IF @@ROWCOUNT = 0
    BEGIN
        -- Finished when no more projects left to process
        IF NOT EXISTS
        (
            SELECT P.ProjectId FROM #Projects AS P
            EXCEPT
            SELECT G.ProjectID FROM #Groups AS G
        )
        BEGIN
            BREAK;
        END;

        -- Next group number
        SET @GroupID += 1;
    END;
END;

SELECT 
    G.GroupID,
    G.ProjectID
FROM #Groups AS G;

This code is non-deterministic because any ties encountered (when sorting by the number of employees per project descending) are broken randomly using NEWID. Nevertheless, a typical output is:

╔═════════╦═══════════╗
║ GroupID ║ ProjectID ║
╠═════════╬═══════════╣
║       1 ║         3 ║
║       1 ║         4 ║
║       2 ║         2 ║
║       2 ║         6 ║
║       3 ║         5 ║
║       3 ║         7 ║
║       4 ║         1 ║
╚═════════╩═══════════╝
0
2

May this help you.

SELECT GroupNumber ,p.ProjectId, p.ProjectName, e.EmployeeId, e.EmployeeName
FROM #Projects p
INNER JOIN #Employee_Projects ep 
    ON ep.ProjectId = p.ProjectId
INNER JOIN #Employees e 
    ON e.EmployeeId = ep.EmployeeId
INNER JOIN (
    SELECT MAX(RowNumber) GroupNumber, ProjectId
    FROM (
        SELECT ROW_NUMBER() OVER (PARTITION BY ep.EmployeeId 
                                  ORDER BY ep.ProjectId) RowNumber 
             ,ProjectId
        FROM #Employee_Projects ep 
    ) emp
    GROUP BY ProjectId
) projectGrouping 
    ON projectGrouping.ProjectId=ep.ProjectId
7
  • What is the purpose of dense_rank() in the cte? Dec 22, 2014 at 7:58
  • Thank you for the suggestion! I think it might be a step in the right direction, but it doesn't seem to fully work. For example if add one more project (Project 8) and assign to it Employees 102, 104, 106 then things get really out of whack when using your suggested query. I suppose my original sample data was too oversimplified with each employee assigned to a maximum of two projects. With this additional change you can see how it gets more complex.
    – SQL_Guy
    Dec 22, 2014 at 8:18
  • It was not a suggestion, I was just wondering what the purpose of it was. AFAIK row_number() OVER(PARTITION BY EmployeeId ORDER BY EmployeeId) will do he same as row_number() OVER(PARTITION BY drank ORDER BY drank) Dec 22, 2014 at 8:22
  • @Lennart, you are right about the logic. I just made modification to my answer
    – AA.SC
    Dec 22, 2014 at 9:47
  • @Misha_SQL, did you tried solution after modifications?
    – AA.SC
    Dec 22, 2014 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.