1
$\begingroup$

I'm working on task scheduling for satellite constellations, and I'm trying to determine if there are any keywords related to a certain distinction in task allocation problem that I'm seeing.

In many papers, the required tasks are "one-off": for example, a task could be "take a picture of Paris." Once the picture is taken, the task is completed and no other satellite needs to complete it.

By contrast, you could also imagine more "continuous" tasks, i.e. "Provide internet to Paris." In this setting, you want a satellite to be completing this task at every timestep indefinitely.

The former problems are characterized by task lengths, start and stop times, etc., while the latter problem has no concept of how long it takes to complete a task. Of course, you could formulate a "continuous" task as an uninterrupted sequence of "one-off" tasks, but many algorithms for "one-off" tasks are much less suited for the "continuous" setting.

Is this an established distinction in the literature anywhere? If so, what are the correct keywords for it? (Or are there algorithms that you think would be equally suited for both settings?)

$\endgroup$
7
  • $\begingroup$ You should probably take a look at the AEOS scheduling literature, there are already many publications on this topic scholar.google.com/scholar?q=AEOS+scheduling $\endgroup$
    – fontanf
    Commented Apr 5 at 21:04
  • $\begingroup$ I haven't found anything about this specific distinction I'm referencing, though. $\endgroup$
    – jgholder
    Commented Apr 5 at 21:13
  • $\begingroup$ @jgholder, is the time to take a photo predetermined or unknown? $\endgroup$
    – A.Omidi
    Commented Apr 6 at 7:59
  • $\begingroup$ Indeed, I misunderstood your problem. It looks a bit like the "no-idle" characteristics, but I'm not sure that will help you for your problem $\endgroup$
    – fontanf
    Commented Apr 6 at 11:26
  • $\begingroup$ @A.Omidi in most of the "one-off" literature, the time to take a photo is taken as known. I'm generally more interested in the "continuous" problem though $\endgroup$
    – jgholder
    Commented Apr 7 at 2:39

1 Answer 1

1
$\begingroup$

For the "continuous" settings you describe, perhaps you are looking for the term, online algorithms, used for algorithms that do not assume finiteness of the timeline nor the set of tasks to be completed.

I know the term from Queueing theory in which the performance of online algorithms are regularly compared to the offline counterparts. That is, for some selected finite timespan where all events were recorded, what is the performance gap between having to respond in real-time and with limited knowledge of the future (the online setting), compared to the optimal behavior possible if you look back (the offline setting). This can provide insights as to how the system can be improved.

$\endgroup$

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.