Is there a non-NP-hard algorithm for solving the task assignment problem for workers

Question

input: A set of n n workers and a set of m m tasks. Each worker has: Available working time (in hours). A set of skills (at least one, possibly more). Each task has: Execution duration (in hours). Required skills. Possible dependencies on other tasks.

output: An assignment of tasks to workers, specifying which worker performs which task and when.

Notes: Each worker can perform multiple tasks. Each task must be performed by only one worker.

Does there exist a known polynomial-time algorithm for this problem, or is it inherently NP-hard?

I researched existing algorithms for task assignment and scheduling, including branch-and-bound and constraint programming approaches. However, many solutions I found either assume simplified constraints (e.g., ignoring worker skills or restricting each worker to a single task) or are known to be NP-hard.

I am aware that libraries such as Google OR-Tools can solve this problem, but I want to develop a solution from scratch. I was hoping to find a polynomial-time algorithm that efficiently handles task assignments while considering skills, time availability, and dependencies.

• chrslg: There is no such thing as "NP-hard algorithm". Problems may be NP-hard. Not algorithm. You meant algorithm that runs in polynomial time
• teapot418: NP(-hard, etc.) class is about decision problems - so yes/no questions. I don't think you are interested in yes/no version of your problem (if yes, that looks polynomial). Could be an optimization problem, but you have not specified what you are minimizing/maximizing.
• R T: I want to maximize the number of assigned tasks while ensuring all constraints are met and the workload is distributed fairly among workers.
• R T: I also tried the simplex method but struggled to properly formulate the constraints in a way that fits the method.

Answer 1

This problem is strongly NP-complete because the 3-partition problem with integers in the range T/4 to T/2 can be reduced to it. So not only not polynomial, you also don't get have pseudo-polynomial algorithms either.

For the reduction you need only one skill. No dependencies. Just a collection of workers which each have hours T, with tasks that take time between T/4 and T/2, such that the sum of the task times matches T times the number of workers.

The other options that you provide just make the problem even harder.