1
$\begingroup$

I'm trying to solve the project planning problem using DLX and exact cover matrix, but I'm struggling to find the set of constraints (columns) and the set of options (rows) to achieve this. Here is a sample that represents the main constraints of the problem.

  • Each project have a set of tasks $\{T_1, T_2, T_3\}$
  • Each project have a set of resources $\{R_1, R_2\}$
  • Each task has a duration ($T_1$ has $2$ days, $T_2$ has $3$ days, $T_3$ has $4$ days)
  • Tasks can block each other, and tasks can be blocked by $0$ or many other tasks ($T_1$ is not blocked, $T_2$ is blocked by $T_1$, $T_3$ is blocked by $T_1$ and $T_2$)
  • Only one resource can work on task at a time
  • Resource can only work on one task at a time

I tried several combinations but none of them worked for me. I'm using this npm package to test the matrix.

Can anyone help me find the right set of constraints and options to feed the matrix. Thanks in advance

Improve this question
$\endgroup$
4
  • $\begingroup$ Does each task require both the resources to completes its execution? or any one of the resources? Are the resources identical in the time they finish executing a task? What is the objective? Do you want a feasible assignment of tasks to resources? or you also want to complete all the tasks in minimum duration? $\endgroup$
    – Inuyasha Yagami
    Commented Jul 9, 2023 at 12:33
  • $\begingroup$ @InuyashaYagami thank you for your comment. Here are some more details. Each task should be executed by only one ressource (any of the ressource). For my first iteration, it is ok to consider that all ressources are identical. The goal is to find all scenarios that complete all the tasks $\endgroup$
    – Mohamed Challouf
    Commented Jul 9, 2023 at 13:16
  • 1
    $\begingroup$ Since there are only $3$ tasks why not do this by enumerating all possibilities? $\endgroup$
    – Inuyasha Yagami
    Commented Jul 9, 2023 at 20:24
  • $\begingroup$ The project in the description is just a sample. Real world scenario will involves more tasks and more ressources $\endgroup$
    – Mohamed Challouf
    Commented Jul 10, 2023 at 5:37

1 Answer 1

Reset to default
0
$\begingroup$

Your problem fall under deadlock avoidance and can be solved easily by Bankers algorithm.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for your answer, i’ll have a look, but I’m looking for a solution using DLX. If you think that this not feasible, please let me know $\endgroup$
    – Mohamed Challouf
    Commented Jul 9, 2023 at 13:49

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.