[PYTHON] Optimization learned with OR-Tools [Linear programming: project management]

This blog is what

We will learn mathematical optimization using OR-Tools developed by Google. Most of the content is based on this book. Practical Python AI Projects: Mathematical Models of Optimization Problems with Google OR-Tools (English Edition)

Click here for a list of codes by author The code described in this blog is almost the same as the original one of the author, and it is only partially corrected to Japanese.

Mathematical rigor and theoretical commentary are of low priority. Please forgive me.

This time: Linear programming-project management-

When there are multiple tasks, each with a required time and a preceding task, we want a way to finish it in the shortest time.

Scene setting

Takashi decided to try cooking because he was free during the self-restraint period. By the way, I'm a bad cook, so I may have written something appropriate. Takashi, who decided to make curry rice like a boy's elementary school student, wanted to be able to make it faster than a skilled mother. Curry rice has several processes, but which process should be started and when should the cooking time be the shortest?

point

The key point in project management issues is big ・ Time required for each task ・ Predecessor task of each task There are two. Predecessor tasks are tasks that must be completed before you can start the task. In the curry rice example, the predecessor tasks for "stir-fry meat and vegetables" are "cut meat and vegetables" and "sprinkle salad oil in a frying pan." That's the case with the curry rice I know.

For the rest of the discussion, let me generalize the story a bit. There is a set of tasks $ T $, each element ・ Time required -Predecessor task that is a subset of $ T $ (empty set is also possible) there is. An example is shown in the table below.

The task seems to be numerical and inorganic, so please apply it appropriately. There may be too many processes for curry rice. Probably Indian curry.

Formulation

Let's express it with a mathematical formula. In this example, the coefficient of determination is "which task to start when". By deciding this variable well while adhering to the constraints of the predecessor task, you can minimize the time to complete the last task.

Let the set of tasks be $ T $ and define the start time of each task as follows.

0 \leq t_i \quad \forall i \in T

In the example in the table above, $ t_0 = 3 $, $ t_5 = 7 $. To take into account the constraints of the predecessor task, the time required for task $ i $ (corresponding to the second column of the table) and the subset $ T_i \ subset T $ (table) representing the predecessor task of task $ i $. Let's prepare (corresponding to the third row of). Using these, the lower limit constraint of the start time of task $ i $ is expressed by the following formula.

t_j + D_j \leq t_i \quad \forall j \in T_i ; \forall i \in T

For example, the predecessor task of task 7 is 6, so $ t_6 + D_6 (= 7) \ leq t_7 $ must hold.

It seems to be persistent, but the purpose of this time is to minimize the time to complete the project (here curry making). If each task is performed in turn, (last task start time + time required) is applicable. In reality this is not the case and some tasks should be processed in parallel. I don't know that cooking is different from veteran housewives because of this parallel processing skill. What if I don't know which task is the last, or if there isn't one last task?

Therefore, we will introduce a new variable $ t $. The constraint "greater than the start time of any task + the required time" is placed on this variable.

t_i + D_i \leq t \quad \forall i \in T

And if you want to minimize $ t $, $ t $ will be the project completion time.

Implementation

Here is the code to solve this example. my_or_tools.py and tableutils.py Please see Author GitHub for the contents.

my_project_management.py

from my_or_tools import ObjVal, SolVal, newSolver

def solve_model(D):
  s = newSolver('Project management')                       #Declare solver
  n = 12                                                    #Number of tasks
  max = sum(D[i][1] for i in range(n))                      #Calculate the upper limit of the decision variable
  t = [s.NumVar(0,max,'t[%i]' % i) for i in range(n)]       #Determinant variable. Start time of task i
  Total = s.NumVar(0,max,'Total')                           #End time. I want to minimize this time.
  for i in range(n):  
    s.Add(t[i]+D[i][1] <= Total)                            #Constraints that the objective function must meet
    for j in D[i][2]:
      s.Add(t[j]+D[j][1] <= t[i])                           #Constraints on predecessor tasks
  s.Minimize(Total)
  rc = s.Solve()
  return rc, SolVal(Total),SolVal(t)

Data = [    [0, 3, []],                                     #Example data
            [1, 6, [0]],
            [2, 3, []],
            [3, 2, [2]],
            [4, 2, [1,2,3]],
            [5, 7, []],
            [6, 7, [0,1]],
            [7, 5, [6]],    
            [8, 2, [1,3,7]],
            [9, 7, [1,7]],
            [10, 4, [7]],
            [11, 5, [0]]    ]                                                    


def main():
    import sys
    import tableutils
    n = len(Data)
    C = Data
    if sys.argv[1]=='data':                                 #Display data if the argument is data
        T=[]
        for i in range(n):
            TT=[C[i][0],C[i][1]]
            s='{'
            for j in C[i][2]:
                s = s+' '+str(j)
            s=s+' }'
            TT.append(s)
            T.append(TT)
        T.insert(0,['Task', 'Duration','Preceding tasks'])
        tableutils.printmat(T,True)
    elif sys.argv[1]=='run':                                #If the argument is run, the execution result is displayed.
        rc,V,G=solve_model(C)
        T=[]
        TT=['Task']+[C[i][0] for i in range(n)]
        T.append(TT)
        TT=['Start']+[int(G[i]) for i in range(n)]
        T.append(TT)
        TT=['End']+[int(G[i]+C[i][1]) for i in range(n)]
        T.append(TT)
        tableutils.printmat(T,True)

main()

result

The above code gives the following optimal solution.

As you can see from the table, the shortest end time is 28. If you make a schedule table, it will be as follows.

One thing to keep in mind here is that some tasks will not affect your overall work time anytime you start, as long as they are after the predecessor task. Task 11 is supposed to start at the last minute even though task 0 of the preceding task ends at time 3. In fact, in this formulation, the optimal solution changes depending on the solver. (The optimum value of working time does not change)

Another solution and schedule are shown below.

The task at the bottom has shifted a little to the left. As long as the predecessor task is finished, it is practical to start the task as soon as possible. Projects rarely go as planned, and the latter is less likely to increase overall work time if something goes wrong.

The darkened tasks (0,2,1,6,7,9) in the table are critical paths. Simply put, delaying any one of these will increase the overall work time. In this example, it is obvious if you make a table, but it is not so for a large project with many processes. I will also deal with how to calculate the critical path in the future.

To get a solution to start the task as soon as possible

You can rewrite the line that says s.Minimize (Total) to s.Minimize (sum (t [i] for i in range (n))).

Summary

Takashi succeeded in finding the procedure to make curry rice in the shortest time, but the mother, who has been a housewife for 15 years, lost the time because the time required for each task was shorter than Takashi.