6
$\begingroup$

I've got a System, which is defined as follows:

  • A limited number of stations is given (n), which can offer different services (for now there are two services). A station can either offer one of the services or both (maybe it will be extended one day, then it should work with x different services and a station can offer 1..x of these services).
  • The throughput for a service can differ from station to station.
  • Each service in the system can have a fixed priority assigned by the developer. If multiple services have to be scheduled and the scheduler isn't able to assign each service at once to a single station, it can split up the services and chose the service with the highest priority to run first and run the other service/s later on. (also see next point)
  • If a task requests multiple services, it is okay to split them up. For example, there are two services requested (a and b): requested service a is running on station c for 10 minutes, afterwords it is moving to station d to receive service b. However, you could also think of this as two separate tasks, each of which requests a single service, if you prefer.
  • A task can arrive at any time, for example the incoming of a new request.
  • Each task has an arrival time, an execution time (computed by the requested amount of the service and the amount a station can offer. in other words: this is the time, a particular station will need to complete a task) and a deadline
  • Different tasks have different execution times.
  • Arrival time: there are "reservations", then the arrival time is known before the task arrives. but there are other cases, in which the arrival time is not known, so the arrival time equals "now".
  • A station can serve one task at a time, but a task can request multiple services at once (there are stations which offer these services at the same time, the different services doesn't influence each other).
  • Tasks can be preempted and moved between stations during execution, meaning that if one task is running on a station the task can be assigned to a different station which offers the same service (this station-change can cause costs, based on the distance between different stations). This could be caused by another task which needs the station the first task was running on until now.
  • The algorithm has to work in real time.

The System is given and works already with one service, I have to adapt it to work with multiple services. For this, I have to look for and implement a new scheduling algorithm, but I have no idea for what I have to look for. Another possibility is to design my own algorithm, but due to the lack of knowledge in this sector I think it would be a bad idea.

Any hints for what kind of scheduling algorithms I have to look for?

Improve this question
$\endgroup$
1
  • $\begingroup$ try wikipedia scheduling optimization problems, the basic categories are "open shop, job shop, and flow shop". yours seems to mix some of the categories... $\endgroup$
    – vzn
    Commented Sep 17, 2014 at 15:12

1 Answer 1

Reset to default
1
$\begingroup$

One technical term that might help you focus a literature search is "load balancing". See, e.g.,

Improve this answer
$\endgroup$
1
  • $\begingroup$ thank you. but i think this isn't really what i'm searching for. I've read multiple papers about load balancing for now, but there is no work that deals with different stations/cores and/or multiple services... $\endgroup$
    – auwieha
    Commented Sep 17, 2014 at 9: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.