9
$\begingroup$

I am solving a scheduling problem-to find shifts and task schedules- using column generation. In essence, it is a set covering problem with additional constraints. The problem seems to be that the duals used to find task schedule columns do not provide much information regarding shifts schedules, e.g., tasks are scheduled in periods where shifts coverage is not allowed.

Is it possible to heuristically adjust the duals in such a way that information such as shifts coverage is incorporated in the reduced cost and thus used when finding new task schedule columns? How can we find "better" duals?

Improve this question
$\endgroup$
6
  • $\begingroup$ this appears to be a clear sign that you are missing constraints. "where coverage is not allowed" is not (only) a problem of the dual, but of lacking constraints. The duals corresponding to them will give you the information you need. Heuristically tweaking the duals may help but this would not be my first choice, first make a correct problem statement. Would you mind to elaborate on your problem and model? $\endgroup$
    – Marco Lübbecke
    Jan 2, 2020 at 20:33
  • $\begingroup$ The problem is to find shifts and task schedules. Shift columns are found by solving a subproblem which has all the shift constraints, e.g., min/max duration, min/max start time, etc. Tasks schedules are found by solving another subproblem. Task schedule subproblem has no constraint apart from the constraint that ensures that tasks are scheduled after their release date. Both subproblems are solved at every iteration. The master problem is a set covering problem that minimizes shift cost, tardiness cost and the amount of tasks that are not "covered" by shifts. $\endgroup$
    – German Velasquez Diaz
    Jan 2, 2020 at 20:46
  • $\begingroup$ would a synchronization constraint help then? or maybe even a "nested" approach where tasks schedules are generated that "fit" the shift schedules? $\endgroup$
    – Marco Lübbecke
    Jan 2, 2020 at 20:48
  • $\begingroup$ What do you think it would be the reason for this issue? degeneracy? the fact that I am using two separate subproblems? Could you explain a little bit more about the synchronization constraint approach? would these constraints be added to the task subproblems? $\endgroup$
    – German Velasquez Diaz
    Jan 2, 2020 at 21:02
  • $\begingroup$ Does each task have to fit within one shift, or can tasks straddle more than one shift? If each task must fit into a single shift, why have the task scheduling subproblem? Instead, you could assign tasks to shifts in the master problem. $\endgroup$
    – prubin ♦
    Jan 2, 2020 at 22:47

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.