1

The setup is the following: I have to run a certain amount of tasks. Each task takes a different amount of time to complete and has a separate deadline to make. I can run at most N tasks in parallel (N is about 10-20, but I ignore if it being big or small has any consequence on the solution). Also, there are fixed periodic time windows in which tasks cannot begin, and they occur simultaneously for every parallel thread. This means that if a task ends just after the forbidden window starts, I might miss out on considerable working time, which is undesirable. This might also happen if the forbidden window is about to begin and I start a short task. So it is perhaps more efficient to start a long task which is due for later and only after start a task which is due for earlier, as long as both of them are completed before their respective deadlines.

The question is: is there a sorting algorith that will help me solve this problem efficiently? In short, given a certain number of tasks to run, each with a certain time and deadline, is ther an efficient algorithm that will solve the problem of where to start each task (thread and position in thread)? For now, having it solve for 100 tasks and 10 threads is good, but ideally it would need to be scalable, up to say 5k tasks and ~100 threads.

I am a physics major so I have no clue about sorting algorithms, hope you can help. Thanks in advance!

popeye
  • 81
  • 2
  • 5
  • [Scheduling is hard.](https://stackoverflow.com/questions/2162397/are-all-scheduling-problems-np-hard). In a non-trivial amount of cases (perhaps the majority of them), it's going to be faster to just start the jobs whenever you can instead of expending processor time trying to figure out when to start them. If the run time is inordinately long, try to find some simple rules for starting them that provide reasonable optimizations. – Robert Harvey Feb 19 '19 at 02:06
  • A few clarifying questions. Is the runtime of all task always given and fixed, or could these be some considerable variance? (Perhaps possible branches that make a large runtime difference) Are the dependencies between the different tasks, i.e. TaskA cannot start before TaskB is completed? Without going into too much detail, what are the reasons for the forbidden window? – Thomas Leyk Feb 19 '19 at 02:14
  • @RobertHarvey thanks for your comment! – popeye Feb 19 '19 at 02:28
  • @ThomasLeyk thanks for answering! Answering your questions: 1) The runtime of the tasks vary. This is why it might be more efficient to swap tasks. Maybe average and std deviation would help? 2) There are no conditions on tasks. The only condition is that the final solution makes all the tasks finish on time or at least minimize the time past the deadline. There is a small extra condition that I haven't mentioned but it would complicate matters unnecesarily for now. 3) The forbidden windows arise from a logistical issue. They are, for now, impossible to eliminate. – popeye Feb 19 '19 at 02:36
  • 1
    I think what ThomasLeyk was asking was "How do you know the time a task will take? Does it always take a fixed time or can it vary depending on what the task decides? " I think the reason he asked that is because if a particular task is X and you find a sort that makes it work the way you want and then it takes X+1 sometimes that throws off everything after it and from that point onward your sort doesn't work. However if you know that a task always takes X time a sort might be possible. – Jerry Jeremiah Feb 19 '19 at 02:43
  • @JerryJeremiah oh, I understand. The time required for a certain task to complete is known in advance. Technically, tasks also have associated a certain success probability, but for now taking the success probability as 1 sufices. – popeye Feb 19 '19 at 03:00
  • @GastonMaffei Perhaps I miss-phrased my first question, but JerryJeremiah already clarified what I meant. With regard to question 3, can we assume that any thread that finishes a task during the forbidden window will just wait until that window is over before starting a new task? Meaning, it doesn't break the system if it happens. – Thomas Leyk Feb 19 '19 at 03:08
  • @ThomasLeyk Of course! Forbidden might have been the wrong word to use. It is forbidden in the sense that it is forbidden to start a new task (in any thread) during that window. But nothing bad happens in it if a task is ongoing or finishes in it. It is only bad in the sense that the time between the end of a certain task in the forbidden zone and the start of the next task is dead time. – popeye Feb 19 '19 at 03:11

0 Answers0