VBA Task Order Permutations with constraints and compatibility

[Phteven]

Good Evening,

I am trying to create a list of logical schedule permutations.

I have a list of 50 tasks, some can be done in parallel some may require other tasks to finish before they can begin. I am trying to write a VBA macro which goes generates a list of LOGICAL/FEASIBLE task order permutations.
A visual explanation for a subset of 5 notional tasks:

[TABLE="class: grid, width: 500"]
<tbody>[TR]
[TD]Task ID[/TD]
[TD]Precedent Task Number[/TD]
[/TR]
[TR]
[TD]1[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]2[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]3[/TD]
[TD]1[/TD]
[/TR]
[TR]
[TD]4[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]5[/TD]
[TD]3[/TD]
[/TR]
</tbody>[/TABLE]
So task 3 cannot start until task 1 has been completed, and task 5 cannot start until task 3 has been completed.
The compatibility matrix shows which tasks can be performed in parallel

[TABLE="class: grid, width: 500"]
<tbody>[TR]
[TD][/TD]
[TD]Task 1[/TD]
[TD]Task 2[/TD]
[TD]Task 3[/TD]
[TD]Task 4[/TD]
[TD]Task 5[/TD]
[/TR]
[TR]
[TD]Task 1[/TD]
[TD="align: center"]1[/TD]
[TD="align: center"][/TD]
[TD="align: center"][/TD]
[TD="align: center"][/TD]
[TD="align: center"][/TD]
[/TR]
[TR]
[TD]Task 2[/TD]
[TD="align: center"]1[/TD]
[TD="align: center"]1[/TD]
[TD="align: center"][/TD]
[TD="align: center"][/TD]
[TD="align: center"][/TD]
[/TR]
[TR]
[TD]Task 3[/TD]
[TD="align: center"]0[/TD]
[TD="align: center"]0[/TD]
[TD="align: center"]1[/TD]
[TD="align: center"][/TD]
[TD="align: center"][/TD]
[/TR]
[TR]
[TD]Task 4[/TD]
[TD="align: center"]0[/TD]
[TD="align: center"]0[/TD]
[TD="align: center"]1[/TD]
[TD="align: center"]1[/TD]
[TD="align: center"][/TD]
[/TR]
[TR]
[TD]Task 5[/TD]
[TD="align: center"]0[/TD]
[TD="align: center"]0[/TD]
[TD="align: center"]0[/TD]
[TD="align: center"]1[/TD]
[TD="align: center"]1[/TD]
[/TR]
</tbody>[/TABLE]

This is a symmetric matrix, and reads as follows:
Task 1 and 2 can be performed in parallel
Task 3 and 4 can be done in parallel
Task 4 and 5 can be done n parallel

The application of these constraints result in permutations of task order

[TABLE="class: grid, width: 800"]
<tbody>[TR]
[TD]Task Order[/TD]
[TD]Task 1[/TD]
[TD]Task 2[/TD]
[TD]Task 3[/TD]
[TD]Task 4[/TD]
[TD]Task 5[/TD]
[/TR]
[TR]
[TD]Permutation 1 (all tasks done in series)[/TD]
[TD="align: center"]1[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]4[/TD]
[TD="align: center"]5[/TD]
[/TR]
[TR]
[TD]Permutation 2[/TD]
[TD="align: center"]1[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]4[/TD]
[/TR]
[TR]
[TD]Permutation 3[/TD]
[TD="align: center"]1[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]3[/TD]
[/TR]
[TR]
[TD]...[/TD]
[TD="align: center"][/TD]
[TD="align: center"][/TD]
[TD="align: center"][/TD]
[TD="align: center"][/TD]
[TD="align: center"][/TD]
[/TR]
[TR]
[TD]Permutation n (Tasks done in parallel constraints included)[/TD]
[TD="align: center"]1[/TD]
[TD="align: center"]1[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]3[/TD]
[/TR]
</tbody>[/TABLE]

To clarify how one would read this table: each row entry is the order in which tasks are performed, so Permutation would read:
Task 1 is performed first, then task 2, second...and so on


The first thought I had was to generate every permutation, and then check to see whether that permutation meets the constraints...
However, with 50 tasks, the total number of permutations is 50! which exceeds the total number of cells that any one workbook could hold if every cell on every sheet had one unique permutation...not to mention that this would take many years to go through.

The code I have for generating all permutations is below, adapted from http://www.mrexcel.com/forum/excel-questions/695593-permutation-macro-help-please.html, this method takes a text string (inserted into cell A1),splits it, and performs a full factorial permutation of the letters, pasting each new option in the subsequent cell. I modified it to move onto the next column once the maximum number of rows that a sheet can contain (1,048,576) has been reached.

Sub DoString()
On Error Resume Next
    Dim Instring As String
    Dim i As Integer, j As Integer
    Dim StartTime As Double
Dim SecondsElapsed As Double
'Turn off screen updating and auto-calc to speed up
Application.ScreenUpdating = False
Application.Calculation = xlManual
   
'Remember time when macro starts
  StartTime = Timer
  
    Instring = Range("A1").Value
        Range("A1").Select
        CurrentRow = 1
    Call GetPermutation("", Instring)
 
  SecondsElapsed = Round(Timer - StartTime, 2)
  Worksheets(2).Cells(Len(Instring), 17).Value = SecondsElapsed
  Application.ScreenUpdating = True
  Application.Calculation = xlAutomatic
End Sub

Sub GetPermutation(X As String, y As String)
On Error Resume Next
Dim j, i
Dim columncounter As Double
j = Len(y)
columncounter = Application.WorksheetFunction.RoundDown(CurrentRow / 1048576, 0)
    If j < 2 Then
            
            'This moves from one column to the other when the maximum number of rows are exceeded
            If columncounter > 1 Then
                Cells(CurrentRow - (columncounter * 1048576), 2) = X & y
                CurrentRow = CurrentRow + 1
                
                Else
                
                Cells(CurrentRow, 1) = X & y
                CurrentRow = CurrentRow + 1
                
            End If             
                
            
      Else
        For i = 1 To j
            Call GetPermutation(X + Mid(y, i, 1), _
            Left(y, i - 1) + Right(y, j - i))
        Next
    End If
End Sub

Does anyone have a suggestion for performing such a computation without assessing every permutation?