I was given the task to model the following problem and find a solution for it, but as I do not have any experience in this field, I already have trouble classifying it.
There are a number of vehicles and a (possibly much greater) number of transportation-tasks that should be assigned to the vehicles.
One task consists of fetching a good from one station and bringing it to another station, while there are multiple stations, each of which can act as both a start- or an endpoint.
There are different kinds of transportation tasks and not every vehicle can do every kind of task.
Also, the arcs/edges between the stations have a capacity of 1, meaning that one vehicle occupies it for a specific amount of time.
At the stations, there also is a waiting time, meaning that maybe a queue of waiting vehicles arises (let's assume the queue can have infinite length).
One vehicle can only do one task at a time, but can put succeeding tasks in a queue.
And, last but not least, new tasks are being generated continuously, so the algorithm has to work "on-line".
The objective is to minimize the time it takes to complete all tasks.
From what I have read so far, this could be a job shop scheduling problem with sequence-dependent setup time, as there are multiple "machines" (the stations doing the on- and offloading "job") and what is actually the task in real life (the transportation of the goods), could be modeled as a setup time for the job, which is dependent from the preceding task, because the end-position of the preceding task determines the time the vehicle needs to get to the new start-position.
- Is that correct?
- How do I model such a system to find a good enough solution?
- For the future, are there ways how I can differentiate between different problem-classes? I have the feeling that Linear Optimization, Assignment, Scheduling, Network Flows, Routing, etc. are quite similar and with some adjustments could all somehow fit the problem...