I'm working on a (real life!) scenario that involves scheduling workers on an assembly line. Let's say it involves steps a -> b -> c -> d -> e
, and each step takes a different amount of time. There are a lot of orders coming through the assembly line, all with different due dates. So an order might come in on May 3rd and need to be finished by May 11th, and another could come in on May5th and need to be completed by May 9th. In this case, it's trivial to switch from one order to another that is higher priority.
Here's the challenge: some workers are responsible for multiple steps. So for example, steps b
and d
may involve the same 4 workers. Any configuration is possible and can change hour by hour. So there could be 4 workers on b
and 0 on d
at the start of the day. Then 3 and 1 around lunch, and then 0 and 4 at the end of the day.
The only limitation is that using a resource at either b
or d
reduces the capacity for the other step by 1.
I'm unclear how to handle this with the standard greedy approach. If the steps each had different workers, I would simply prioritize each task based on earliest due date.
With the constraint of shared resources, does it still make sense to consistently pick the task with the earliest overall due date? For the following jobs,
A: Start: May 3 Due: May 11
B: Start: May 5 Due: May 9
and the restriction that b
and d
each use the same workers, this approach would lead to all 4 workers working on (job A, task b) at first, then all switching to B->b
as soon as job B
is available, then B->d
, before all switching back to A->d
.
Is this approach correct? Does it matter how long the individual tasks take?
worker == resource
, and any of them will suffice. The same person doesn't need to do both stepb
andd
for a single item, I just mean that at any point in time, four people total can be working on both tasks combined. So if 3 people are working on step b from 2-3 pm, only 1 person is available for step d from 2-3. $\endgroup$ – James Timmins May 2 '19 at 0:43