2
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ What you called the "wait to start" is usually called "flow time". Note that minimizing $\sum_i (t_i - s_i)$ is equivalent to minimizing $\sum_i t_i$ since $s_i$ are constants $\endgroup$
    – fontanf
    Commented Jul 3, 2023 at 19:58
  • $\begingroup$ What are the orders of magnitude of $n$ and $p$? $\endgroup$
    – fontanf
    Commented Jul 3, 2023 at 20:09
  • $\begingroup$ $n$ is around 200, $p$ is around 20 $\endgroup$
    – Ike348
    Commented Jul 3, 2023 at 21:40

2 Answers 2

4
$\begingroup$

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$.

$\endgroup$
10
  • $\begingroup$ Thanks! Given the notation I gave in the question, am I correct to assume that $s_i$ (scheduled start for task, fixed) should really be $t_i$ (actual start time, decision) in your answer? $\endgroup$
    – Ike348
    Commented Jul 3, 2023 at 19:11
  • $\begingroup$ Yes, corrected. $\endgroup$
    – RobPratt
    Commented Jul 3, 2023 at 19:44
  • $\begingroup$ I was able to implement this solution and the results are promising, but I still have to verify everything. I will accept this answer once I get back to this in the next couple days. $\endgroup$
    – Ike348
    Commented Jul 3, 2023 at 21:56
  • 1
    $\begingroup$ Dear @RobPratt, I think for the second we need to imply $i \lt j$. otherwise, it causes an infeasible search space. $\endgroup$
    – A.Omidi
    Commented Jul 4, 2023 at 13:42
  • $\begingroup$ And it needs still to add the no-overlap constraints to prevent overlapping tasks for the same worker? Correct? $\endgroup$
    – A.Omidi
    Commented Jul 4, 2023 at 13:45
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks for your answer! In my problem, there are effectively no precedence relations. (There are a couple cases where Job i must happen before Job j, but in those cases i and j are so far apart that no optimal schedule would ever violate precedence). The choice of the objective function is driven by the client--I am not worried about losing a feasible schedule as I can extend the horizon as far out as I need to. $\endgroup$
    – Ike348
    Commented Jul 5, 2023 at 19:27
  • $\begingroup$ @Ike348, you're welcome. I think the only reason to use a mathematical model, in this case MIP, is making an optimal solution and in your case actually an active schedule. I am not sure what you mean by an infeasible schedule? But if it is something like to violate some overlaping or unnecessary waiting over resources you definitely lose utilization of your resources. $\endgroup$
    – A.Omidi
    Commented Jul 5, 2023 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.