0
$\begingroup$

This is an extention to the workforce scheduling problem discussed in this thread Workforce scheduling problem. Adding a new post to discuss an important new requirement in this model. So the new constraint is as follows: for a given worker, they can work multiple consecutive shifts (with min and max daily hours limits) where each shift has a different role (for example a worker can work 10am-12pm as cashier, then noon to 3 as a manager, 3pm to 5pm as a barista, and so on). After getting an excellent advice from @RobPratt, I tried to formulate oneshiftperday as a network formulation problem. I am trying to extend this to the new requirement of multiple shifts per day and I could model the consecutive and K shift per day requirement but am struggling with all distinct roles.

Is there a way to model this without adding too many mutual exclusivity side constraints?

Improve this question
$\endgroup$
5
  • $\begingroup$ In the network formulation, introduce for each node an additional index that specifies the role. The presence or absence of an arc in the network definition can depend on the roles of the two endpoint nodes. For example, if consecutive shifts must have different roles, omit any arc where the nodes have the same role. $\endgroup$
    – RobPratt
    Commented Mar 14 at 13:02
  • $\begingroup$ But how do you accommodate something like this: there are two shifts s1: 10am to 12pm for a cashier and another s2: 10am to 12pm for a manager and they both have a valid next shift and hence an arc to a shift s3: noon to 3pm for a barista. Now let's assume there are two next shifts s4: 3pm to 5pm for a cashier and s5: 3pm to 5pm for a manager. The sequence s1->s3->s5 is valid but not s1->s3->s4 as it repeats the role of cashier in the latter and it is not allowed. Similarly, the sequence s2->s3->s4 is valid but not the sequence s2->s3->s5. $\endgroup$
    – SDC
    Commented Mar 14 at 15:10
  • 2
    $\begingroup$ OK, so there is a requirement that the three roles must be distinct. Here are two alternative approaches. One way is to augment the node definitions to include all roles that have been active so far that day. So in your example you would also have s3c and s3m nodes to indicate that the previous role was cashier or manager. Another way is to have a node for each possible shift combination in a day, so your s1->s3->s5 sequence would be a single node, and s2->s3->s4 would be another node. $\endgroup$
    – RobPratt
    Commented Mar 14 at 15:43
  • $\begingroup$ So for the second approach that you suggested where each node will have a distict combination of sequential shifts for a day -- I will have to add constraints to link the individual shifts in that sequence back to the originial shift-worker assignment variables -- something like when the variable corresponding to the sequence s2->s3->s4 is 1 then all the shift-worker variables for s2, s3, and s4 must be 1, is that correct? $\endgroup$
    – SDC
    Commented Mar 14 at 16:51
  • 1
    $\begingroup$ The network-based formulation has a variable for each arc and optionally a variable for each node. You can express any side constraints in terms of arc variables, node variables, or both. $\endgroup$
    – RobPratt
    Commented Mar 14 at 18:30

1 Answer 1

Reset to default
2
$\begingroup$

For the requirement that the roles performed by a single worker in a day must be distinct, here are two alternative approaches. One way is to augment the node definitions to include all roles that have been active so far that day. So in your example you would also have s3c and s3m nodes to indicate that the previous role was cashier or manager. Another way is to have a node for each possible shift combination in a day, so your s1->s3->s5 sequence would be a single node, and s2->s3->s4 would be another node.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.