0
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ I don't fully understand the problem statement. What's a resource? Is a resource the same thing as a worker? When you say things like "step b involves 4 workers", do you mean that there are 4 workers who are qualified to work on step b and any one of them suffices? that you need to assign a team of any 4 workers qualified to work on step b? that it's not a matter of qualification, but whoever is assigned to step b must also be assigned to step d? $\endgroup$ – D.W.♦ May 1 at 22:20
  • $\begingroup$ Why don't you try working through some examples to see if this is optimal in all of them? Then you can report on what you find, or show us a minimal specific example where it is not. $\endgroup$ – D.W.♦ May 1 at 22:21
  • $\begingroup$ @D.W. Apologies for the ambiguity. Yes, a worker == resource, and any of them will suffice. The same person doesn't need to do both step b and d 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 at 0:43
  • $\begingroup$ Can you edit the question so it's clearer? Thank you! $\endgroup$ – D.W.♦ May 2 at 4:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.