メインコンテンツへスキップ

Solve scheduling model using a greedy heurisitc

回答済み

コメント

4件のコメント

  • Ronald van der Velden
    Gurobi Staff Gurobi Staff

    Hi Lorenz,

    You mentioned "Since my whole model is very complex for large model". Does this mean the model formulation is as above, but runtime increases as you add workers/shifts/days? Can you give an indication of the model dimensions, and the runtime you observe? Are there other complexities that are not shown above (e.g. labor rules related to consecutive shifts for the same worker) which could have an impact?

    If you're willing to sacrifice global optimality, you could consider solving a series of subproblems where each subproblem contains a subset of workers, days and/or shifts. One common approach is rolling horizon. You'd first solve the problem for days 1-7. Then you fix the assignments for day 1, and solve the model for days 2-8 (but include fixed variables for day 1), then for days 3-9 after fixing days 1-2 etcetera. Other alternatives exist, e.g. repeatedly solve for different subsets of employees. You could even start with rolling horizon, then iteratively reoptimize for subsets of days and/or employees. There's many options out there - but ideally you'd first try to solve the full MIP.

    Kind regards,
    Ronald

    0
  • JohnPaul Adimonyemma
    First Comment

    Hi Ronald,

    If you're willing to sacrifice global optimality, you could consider solving a series of subproblems where each subproblem contains a subset of workers, days and/or shifts. One common approach is rolling horizon. You'd first solve the problem for days 1-7. Then you fix the assignments for day 1, and solve the model for days 2-8 (but include fixed variables for day 1), then for days 3-9 after fixing days 1-2 etcetera. Other alternatives exist, e.g. repeatedly solve for different subsets of employees. You could even start with rolling horizon, then iteratively reoptimize for subsets of days and/or employees

    Base on the above, please is there a Gurobi implementation rolling horizon? That involves  the fixing of  the decision from the  non-overlapping horizon and then reoptimizing the decision of the overlapping horizon in the next horizon. If you can help with some examples on this, I will appreciate it. 

     

    Thanks

    0
  • Ronald van der Velden
    Gurobi Staff Gurobi Staff

    Hi Johnpaul,

    We don't have a full example available. However, once you have the code for constructing and solving the full model, the changes are relatively small. Here are the tricks you need:

    • After your first call to model.optimize(), you can make any changes needed. In your case, you would extend the planning horizon and therefore add a set of variables for the newly added day, plus constraints that involve these variables.
    • To fix the variables for the first day in your horizon, you simply set the LB and UB attributes of the corresponding variables to their optimal solution from the previous iteration, e.g. var.LB = var.X; var.UB = var.X.
    • Finally, to reoptimize, you simply call model.optimize() again. Gurobi will try to restart from its previous solution.

    Kind regards,
    Ronald

    0
  • JohnPaul Adimonyemma
    First Comment

    Thanks so much for your quick response, Roland 

    0

サインインしてコメントを残してください。