Scheduling to minimize total "wait to start" time

Question

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.

Answer 1

I recommend using your second formulation with $np$ binary assignment variables and $n$ continuous start variables. To prevent overlapping tasks for the same worker, impose a linear disjunction for each pair of tasks that can be assigned to the same worker, as in this question: Modelling precedence relations

Explicitly, let $x_{iw}$ indicate whether task $i$ is assigned to worker $w$, let $y_{ij}$ indicate whether task $i$ precedes task $j$, and impose linear constraints \begin{align} \sum_w x_{iw} &= 1 &&\text{for all $i$} \tag1\label1\\ x_{iw} + x_{jw} - 1 &\le y_{ij} + y_{ji} &&\text{for all $i,j,w$} \tag2\label2\\ t_i + d_i - t_j &\le M_{ij}(1-y_{ij}) &&\text{for all $i,j$} \tag3\label3 \end{align} Constraint \eqref{1} assigns each task to exactly one worker. Constraint \eqref{2} enforces $(x_{iw} \land x_{jw}) \implies (y_{ij} \lor y_{ji})$. Constraint \eqref{3} enforces $y_{ij} = 1 \implies t_i + d_i \le t_j$.

Answer 2

Based on what you mentioned, something should be considered. First, your problem falls in the class of parallel machine scheduling problems. There are $n$ tasks that should be processed by $p$ resources. Second, you already have released time, $r_{j}$, and resource eligibility, $M_{j}$, constraints. I am not sure if you have a precedence relation that is very common in such kinds of problems. If there exists, the problem can be solved very effectively, say optimal, by the $\text{CPM}$ algorithm.

B.T.W, the problem can be represented as $ P_{k} | r_{j}, M_{j} | C_{max}/\sum C_{j}$. Where $\sum C_{j}$ would be the total flow of tasks. Also, you can use other uncommon objective functions like what you proposed as $\sum_i \left(t_i - s_i \right) $, but in many cases, you might lose an active schedule. One of the best algorithms to tackle such a problem would be the $\text{LSF}$, the least flexible job first, algorithm. Also in the case that all of the tasks have a duration equal to one and also without given released time, this achieves an optimal schedule.

The $\text{LSF}$ rule selects, every time a machine is freed, among the available jobs the job that can be processed on the smallest number of machines, i.e., the least flexible job. Ties may be broken arbitrarily.

Please be aware that, as many of the problems in this class of scheduling are strongly NP-hard, developing an appropriate mathematical model without having a solution procedure, like decomposition methods, etc, would be challenging work. I recommend you to look at LEKIN software which is one of the excellent to test and benchmark such problems.