Search code examples
pythonoptimizationlinear-programminggekko

Schedule Optimization Problem don't know a better way to present the solution - Python / Gekko


So my music school runs a festival for all student bands to play together. Since there are some family members across diferent bands, I'm trying to create a solution to optimize the schedule of the bands - trying to minimize sum of time between bands that have relatives. Now I think I've found a solution. Don't know if it's the best but it looks like it's working. Now I'm trying to find a better way to present the solution. This "x" matrix is huge and maybe it would be better to extract only the "1"s and make a schedule table with the slots and what band is in a cronological order. But I don't know where to start. Hoping someone can point the direction.

Relevant infos:

  1. English is not my first language;
  2. I'm not a programmer, and everything I did at the code bellow was what I was able to learn about python last 2 days.

I'm using the code bellow. Feel free to criticize and make any suggestions. Thanks!

from gekko import GEKKO
import numpy as np
m = GEKKO()

#variables and constrains
n = 20 #n of bands
s = 37 #n of slots to play
t = 25 #time in minutes one band spend on the stage

x = m.Array(m.Var,(n,s),value=0,lb=0,ub=1,integer=True) #matrix of all bands(rows) x slots (columns)
for j in range(s):
        m.Equation(m.sum([x[i,j] for i in range(n)])<=1) #since this is the decision i made it binary and sum=1 to 1 band only ocuppie one slot
for i in range(n):
        m.Equation(m.sum([x[i,j] for j in range(s)])==1) #since this is the decision i made it binary and sum=1 to 1 band only ocuppie one slot
       
z = [k for k in range(1,s+1)] #array with slot index to use to calc time 
w = z*x*t #time the band will perform ;; used in objetive function


#objective
#in this exemple the band (1,4) and the band (1,5) have a relationship, and so do (3,2) and (1,15), so the objetive function bellow will try to minimize the sum of the time between bands that have relationship 
y = m.abs2(w.item(1, 4)-w.item(1, 5))+ m.abs2(w.item(3, 2)-w.item(1, 15)) 
m.Minimize(y)


#solver
m.options.SOLVER = 1
m.solve()



#print(w.item((1, 4)))
print('y')
print(y)
print('x')
print(x)


Solution

  • You need to extract the band and slot numbers for each 1 in the matrix and sort the schedule by slot number:

    schedule = [(i+1, j+1) for i in range(n) for j in range(s) if x[i,j][0] == 1]
    schedule.sort(key=lambda x: x[1])
    for band, slot in schedule:
        print(f"Band {band} is scheduled to play in slot {slot}")