I am relatively new to linear programming, and I'm particularly interested in applying it to scheduling problems (transportation, staffing, etc).
I've Googled for several hours looking at articles on this category of problem, but the documented problems are much more complicated than the one I am currently pondering, which I've contrived on my own as an exercise.
Here is the problem:
SCENARIO: You have three drivers to make deliveries.
Driver 1 costs $10 / hr
Driver 2 costs $12 / hr
Driver 3 costs $14 / hr
Each driver can only work 3-6 hours a day. Only one shift can be worked by a worker a day. Only one worker can be working at a given time. Operating day is 6:00 to 22:00, which must be fully covered.
Driver 2 cannot work after 11:00.
Create a schedule that minimizes the cost.
Here is the work I have written out so far.
Tsx = shift start for Driver X
Tex = shift end for Driver X
Minimize: 10(Te1 - Ts1) + 12(Te2 - Ts2) + 14(Te3 - Ts3)
4.0 <= Te - Ts <= 6.0
6.0 <= Ts, Te <= 22.0
(Te1 - Ts1) + (Te2 - Ts2) + (Te3 - Ts3) = (22.0 - 6.0)
Te2 <= 11
When I express these equations in my Kotlin code (which I can share if desired), I am getting shift overlaps. Here is the output:
OPTIMAL 624.0 @ [6.0, 11.0, 6.0, 12.0, 6.0, 11.0]
It minimized the cost to $624, and it did correctly constrain to 16 hours worth of shifts. It also respected the max shift time allowed for each driver, and prevented Driver 2 from being scheduled beyond 11:00.
However, it scheduled the shifts to Driver 1 6:00-11:00, Driver 2 6:00-12:00, and Driver 3 6:00-11:00.
I've tried to research the solution to this problem, but I really cannot find a simple answer to my question. Can someone please share what mysterious linear functions I need to constrain to in order for my shifts to not overlap? I keep reading about binary constraints and I'm not sure how to use those to show a shift being "occupied".