0
$\begingroup$

I have a list of recurring tasks (1k+ tasks) and I am trying to find a optimal scheduling given a shared constrained resource.

In other respects the tasks are independent of each other

Each task is configured to run recurrently at a given interval (i.e "cron" job). For instance a particular task could have been configured to run at 10 minute intervals while another task could be configured at 20 minutes etc.

The duration of tasks varies (disregarding the shared resource)

Tasks have priorities (importance).

The task interval is in respects to the completion time of the previous run.

Task interval is "soft" and can be offset to accommodate for higher priority jobs.

I can estimate based on historical evidence how many "shares" of the shared resource each task requires

+-----------+-------------+----------+--------------------+-------------------------+
| Task name |  Interval   | Priority | Estimated duration | Estimated resource      |
+-----------+-------------+----------+--------------------+-------------------------+
| task1     | 30 minutes  |        1 | 10 minutes         | 10                      |
| task2     | 10 minutes  |        3 | 25 minutes         | 90                      |
| task3     | 60 minutes  |        4 | 5 minutes          | 25                      |
| ...       |             |          |                    |                         |
| task 1000 | 180 minutes |        2 | 75 minutes         | 100                     |
+-----------+-------------+----------+--------------------+-------------------------+

conceptually the architecture should be:

                                                                              +------------+
  task list                                                                   |            |
+-------------+                                                               | Task x     |
|             |                       +-----------+                           |            |
|    Task1    |                       |           |      running  tasks------>+            +----------+      +-----------------+
|    Task2    |    choose tasks       |           |               |           |            |          |      |                 |
|    Task3    +----------------------->  Scheduler+---------------+           |            |          |      |                 |
|    ....     |                       |           |               |           +------------+          |      |                 |
|    Task_N   |                       |           |               |               .                   +----->+                 |
|             |                       |           |               |               .                          | constrained resource
|             |                       +-----------+               |               Many tasks                 |                 |
|             |                                                   |               .                   +------>                 |
+-------------+                                                   |               .                   |      |                 |
                                                                  |           +------------+          |      |                 |
                                                                  |           |            |          |      |                 |
                                                                  |           | Task z     |          |      +-----------------+
                                                                  +----------->            +----------+
                                                                              |            |
                                                                              |            |
                                                                              |            |
                                                                              +------------+
$\endgroup$
  • $\begingroup$ What are the constraints? Can you schedule more than one task to the resource at a time? Can I schedule all of them at the same time? What exactly is the criteria for which subsets of tasks can be assigned at the same time? What does the "shares" have to do with which tasks can be assigned at the same time? Also, if you can't meet all the scheduling goals, how do you want the priorities to relate to the solution? (Lower priority tasks get nothing; proportional use of resource; something else?) It seems like something is missing from the problem specification. $\endgroup$ – D.W. Mar 5 at 19:41
  • $\begingroup$ The shared resource is constrained. Of course more then one task can be scheduled at the same time (as many as you want could run). Many viable solutions exists (known empirically through evidence. In some cases it fails currently hence the question here $\endgroup$ – Avner Barr Mar 8 at 8:37
  • $\begingroup$ Yes, you already mentioned that it is constrained, but that isn't what I was asking. Please edit the question to clarify the answers to my questions. (We want questions to be self-contained, so people don't have to read the comments to understand what you're asking.) $\endgroup$ – D.W. Mar 8 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.