I was thinking about developing a daily production work plan algorithm for an enterprise. The problem is as following:

There are various tasks that needs to be completed, each has a deadline, a duration and a set of requirements for resources. It is mandatory that no task is expired, but if that's not possible, we will settle for a plan with earliest completion time.

From there, these tasks will be divided into daily work plan which allows maximum 8 hours of task execution.

I think I'll start from looking at job-shop scheduling algorithms and bin packing algorithm but it that correct? You guys have any idea about how this could be done?

  • $\begingroup$ it's a constraint problem, which is np complete, That means there will be no fast general solver. However that doesn't discount being able to take advantage from certain constraints. $\endgroup$ – ratchet freak Jul 4 '17 at 8:47
  • $\begingroup$ @ratchetfreak The instance size is effectively fixed because there are only eight working hours in a day, there's presumably an implicit minimum task length and one assumes that the company only takes on work that's approximately possible, so we're probably in a system that isn't massively over-constrained. Given all that (especially the bounded input size), NP-completeness probably isn't much of a hindrance. $\endgroup$ – David Richerby Jul 4 '17 at 9:55

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.