I have a scheduling problem I am trying to work through. As I was outlining the problem, I realized it is probably of a known problem type, but I am unsure of what keywords to search for or what software to use.
I have $n$ tasks and $p$ workers. For each task, I must determine when the task is completed, and by which worker. Each worker can only work on one task at a time, and each task must be completed. Each worker is only qualified to perform a specific set of tasks, so each task can only be completed by a specific set of workers.
Each task $i$ has a scheduled start time $s_i$ and scheduled duration $d_i$. Tasks may start later than their scheduled start time, but may not start earlier. Some tasks must start exactly on time. Tasks will always take exactly $d_i$ time to complete. There is no deadline to complete any task, and tasks can be completed in any order (as long as they do not start before their start date).
Define the actual start time for each task as $t_i$, and the "wait to start time" for task $i$ as $t_i - s_i$.
The goal is to schedule the tasks by assigning them to workers and determining their start times such that the total "wait to start" time for each task is minimized. That is, my objective is to minimize $\sum_i \left(t_i - s_i \right)$, subject to the above constraints.
I can easily frame this as a integer linear program by creating $n \cdot p \cdot k$ binary decision variables, where $k$ is the maximum number of "wait to start" days that I allow. The problem here is that this can be a very large number of decision variables for integer programming, as $n \approx 200$, $p \approx 20$ and $k$ is on the order of hundreds. Additionally, I would not like to set a global maximum on "wait to start" days.
An alternative formulation requires only $n \cdot p$ decision variables for the assignments, plus $n$ decision variables for the start times, but in this case, the constraint that each worker can only work on one task at once becomes very non-linear.
What type(s) of problem is this and what software exists to solve it? I am open to both exact solvers and heuristics. Our current workflow to solve this problem is a homemade greedy algorithm that assigns workers to tasks via iterating over time, so I imagine an integer/constraint programming approach will lead to a much better solution.