I have the following question. I have a classical scheduling model with the following constraints:

  1. Demand coverage
  2. One shift per day
  3. Minimum and maximum number of consecutive working days
  4. Forward rotation
  5. Constraints for the calculation of preference violations.
  6. Other (less important) constraints

My objective function minimizes the weighted sum of under- and overstaffing as well as the sum of all preference violations.

Since my model is very difficult to solve with large model instances, my professor suggested a column generation heuristic. But now I have problems with the decomposition. I would have suggested to decompose the model along the workers. So for each worker there is a sperate subproblem and a master problem which merges the subproblems. So it contains the demand constraint and the $\lambda = 1$ constraint. But now I have the question of how the target functions are structured in each case. My suggestion would be as follows:

  1. Master problem: sum of under-+ overstaffing plus sum over cost of $\sum_{i,r} c_{ir}\dot\lambda_{ir}$, where $c_{ir}$ is the cost of the roster.
  2. Subproblem: Sum of the preference allocation (per worker) - duals of the demand constraint * shift allocation - duals of the $\lambda$ constraint.

Would that be correct or should it look different?

  • 1
    $\begingroup$ Could you write down a bit more? Like, what are the vars? And constraints (precisely)? $\endgroup$ Commented Jun 14 at 15:28


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.