Search code examples
pythonlistoptimization

Python list won't correctly randomise inside of a conditional while loop

I am working on an optimisation problem using python, whereby I have to optimise a timetable for a theoretical hospital. This timetable has 3 columns for the different theatres, and 9 slots in each row to represent the number of time slots per day.

Each of the time slots is taken up by a surgery, and one of the values that describes each surgery is whether it requires an anaethetist or not, and one of the constraints of the problem is that you cannot have more than two required in any given time slot across all of the operating theatres.

Since my timetable is represented like this:

Theatre 1 Theatre 2 Theatre 2
Slot 1 Slot 1 Slot 1
Slot 2 Slot 2 Slot 2
Slot 3 Slot 3 Slot 3
Slot 4 Slot 4 Slot 4
Slot 5 Slot 5 Slot 5
Slot 6 Slot 6 Slot 6
Slot 7 Slot 7 Slot 7
Slot 8 Slot 8 Slot 8
Slot 9 Slot 9 Slot 9

I have created this function to check the surgeries in one slot across the 3 theatres, returning false if the number required exceeds the limit of 2, and true if the required amount is within the limit.

def AnaesthetistsWithinLimit(timetable, anaesthetistLimit):
   # Index of column, theatre, max 3
   for i in range(len(timetable)):
    
      # Index of row, slot, max 9
      for j in range(len(timetable[0])):            
        
        comparisonArray = [timetable[0][j], timetable[1][j], timetable[2][j]]            
        
        anaesthetistCount = 0
        for y in comparisonArray:  
            if y["requires_anaesthetist"] == "Yes":                    
                anaesthetistCount += 1
            if anaesthetistCount > anaesthetistLimit:
                print("Constraint breached:")
                print("    " + str(anaesthetistCount) + " anaesthetists were required")
                print("    limit is " + str(anaesthetistLimit) + " anaesthetists.")
                return False
        
   return True

To generate a solution, I use a method to create a random assortment of slots, taking from a csv file containing all the possible surgeries and their details, contained within surgeryData.

def RandomiseTimetable(timetable, surgeryData):
   
   for x in range(3):
       column = []
       for y in range(9):
           randomIndex = random.randint(0, len(surgeryData) - 1)
           randomRow = surgeryData.iloc[randomIndex]

    
           column.append({
               "surgery": randomRow["surgery"],
               "name": randomRow["name"],
               "requires_anaesthetist": randomRow["requires_anaesthetist"],
           })        
       timetable.append(column)   
   return timetable

Randomising the timetable works, as I can see within the editor that the table changes with each run, but when I tried to test for this constraint, and generate a new solution until it is satisfied, it either doesn't generate a new solution at all or keeps on generating, forcing me to manually stop it.

Here I want to check whether the current required amount is within the limit, and if it is not true, generate a new solution. Then it should escape the while loop once true and continue by performing the fitness function.

while AnaesthetistsWithinLimit(timetable, 2) != True:
    timetable = RandomiseTimetable(timetable, surgeryData)
FitnessFunction(timetable, True)

However, as seen here it just keeps running the limit checker, and never actually generates a new solution.

Constraint breached:
3 anaesthetists were required
limit is 2 anaesthetists.
Constraint breached:
3 anaesthetists were required
limit is 2 anaesthetists.
Constraint breached:
3 anaesthetists were required
limit is 2 anaesthetists.
Constraint breached:
3 anaesthetists were required
limit is 2 anaesthetists.
Constraint breached:
3 anaesthetists were required
limit is 2 anaesthetists.
Constraint breached:
3 anaesthetists were required
limit is 2 anaesthetists.
...

I can't see what it is I've missed. The anaethetist checker returns false if a breach is detected, and true if not. So while this test returns false, generate a new solution. As I understand it, python passes lists by reference, so the function should be using the timetable generated in the line below it.

What might I be misunderstanding?

Solution

  • I think the problem is that you keep appending more columns to your timetable within RandomiseTimetable(), but you're only looking at the first three columns in your comparisonArray in AnaesthetistsWithinLimit(). So your timetable does change, but you're only looking at the unchanged columns that you already had on the first iteration.

    I would try to initialize a new empty timetable in RandomiseTimetable() to which you can then append your new columns:

    def RandomiseTimetable(surgeryData):
    timetable = []
    for x in range(3):
        ...
        timetable.append(column)   
    return timetable