VBA Task Order Permutations with constraints and compatibility

Phteven

New Member
Joined
Oct 6, 2015
Messages
1
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:

Task IDPrecedent Task Number
1
2
31
4
53

<tbody>
</tbody>
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

Task 1Task 2Task 3Task 4Task 5
Task 11
Task 211
Task 3001
Task 40011
Task 500011

<tbody>
</tbody>

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

Task OrderTask 1Task 2Task 3Task 4Task 5
Permutation 1 (all tasks done in series)12345
Permutation 212334
Permutation 312233
...
Permutation n (Tasks done in parallel constraints included)11223

<tbody>
</tbody>

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.



Code:
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?
 

Excel Facts

When did Power Query debut in Excel?
Although it was an add-in in Excel 2010 & Excel 2013, Power Query became a part of Excel in 2016, in Data, Get & Transform Data.

Forum statistics

Threads
1,143,673
Messages
5,720,222
Members
422,270
Latest member
CaptainMurray

We've detected that you are using an adblocker.

We have a great community of people providing Excel help here, but the hosting costs are enormous. You can help keep this site running by allowing ads on MrExcel.com.
Allow Ads at MrExcel

Which adblocker are you using?

Disable AdBlock

Follow these easy steps to disable AdBlock

1)Click on the icon in the browser’s toolbar.
2)Click on the icon in the browser’s toolbar.
2)Click on the "Pause on this site" option.
Go back

Disable AdBlock Plus

Follow these easy steps to disable AdBlock Plus

1)Click on the icon in the browser’s toolbar.
2)Click on the toggle to disable it for "mrexcel.com".
Go back

Disable uBlock Origin

Follow these easy steps to disable uBlock Origin

1)Click on the icon in the browser’s toolbar.
2)Click on the "Power" button.
3)Click on the "Refresh" button.
Go back

Disable uBlock

Follow these easy steps to disable uBlock

1)Click on the icon in the browser’s toolbar.
2)Click on the "Power" button.
3)Click on the "Refresh" button.
Go back
Top