经典的任务调度分配
我正在开发一个航班调度应用程序（免责声明：这是一个大学项目，所以没有代码答案，请）。请在回答之前仔细阅读这个问题，因为它有很多特点:(
首先，一些术语问题：
你有飞机和航班，你必须将它们配对。为简单起见，我们假设飞机在使用该飞机的航班降落后就处于空闲状态。
航班被视为任务：
- 它们有持续时间
- 它们有依赖性
- 它们有预计的日期/时间 飞机
可以被视为任务（或我们的术语中的航班）使用的资源。
航班需要特定类型的飞机。例如，200 航班需要一架 B 型飞机。 飞机显然属于一种且仅有一种特定类型，例如，空军一号飞机属于C 型。
“项目”是航空公司在给定时间段内的所有航班的集合。
所需的功能是：
找到尽可能短的 上述项目的持续时间
最早和最晚的可能 开始任务（航班）
关键任务，基于 提供的数据，完整的 先前任务的标识符。
自动配对航班并 飞机，以便获得所有航班 与飞机配对。 （注： 航班持续时间固定）
获取项目的甘特图 调度，其中所有航班 尽早开始，表明 所有先前引用的数据 以图形方式（依赖性、时间信息、 等）
所以问题是：我到底如何实现这一目标？特别是：
- 我们需要使用图表。
- 图的边和节点有什么作用 分别象征什么？
- 我们是否需要放弃任务 完成设定的关键任务？
如果您还可以推荐一些算法供我们查找，那就太好了。
I am working on a flight scheduling app (disclaimer: it's for a college project, so no code answers, please). Please read this question w/ a quantum of attention before answering as it has a lot of peculiarities :(
First, some terminology issues:
You have planes and flights, and you have to pair them up. For simplicity's sake, we'll assume that a plane is free as soon as the flight using it prior lands.
Flights are seen as tasks:
- They have a duration
- They have dependencies
- They have an expected date/time for
beginning
Planes can be seen as resources to be used by tasks (or flights, in our terminology).
Flights have a specific type of plane needed. e.g. flight 200 needs a plane of type B.
Planes obviously are of one and only one specific type, e.g., Plane Airforce One is of type C.
A "project" is the set of all the flights by an airline in a given time period.
The functionality required is:
Finding the shortest possible
duration for a said projectThe earliest and latest possible
start for a task (flight)The critical tasks, with basis on
provided data, complete with
identifiers of preceding tasks.Automatically pair up flights and
planes, so as to get all flights
paired up with a plane. (Note: the
duration of flights is fixed)Get a Gantt diagram with the projects
scheduling, in which all flights
begin as early as possible, showing
all previously referred data
graphically (dependencies, time info,
etc.)
So the questions is: How in the world do I achieve this? Particularly:
- We are required to use a graph.
- What do the graph's edges and nodes
respectively symbolise?
- What do the graph's edges and nodes
- Are we required to discard tasks to
achieve the critical tasks set?
If you could also recommend some algorithms for us to look up, that'd be great.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这里有一些建议。
原则上，您可以有一个图，其中每个节点都是一个航班，如果 B 依赖于 A，则从航班 A 到航班 B 之间存在一条边，即 B 无法在 A 着陆之前起飞。您可以使用此依赖关系图来计算项目的最短可能持续时间——当您将路径上所有航班的持续时间加在一起时，通过图表找到具有最大持续时间的路径。这是您的项目的“关键路径”。
然而，您需要与飞机配对的事实使其变得更加困难，尤其是。因为我猜假设飞机不允许在没有乘客的情况下飞行，即飞机必须从最后降落的同一城市起飞。
如果您有过多的飞机，则可以使用模拟退火等组合优化算法轻松地将它们分配给航班。如果计划非常紧张，即没有多余的飞机，这可能是一个难题。
要设置航班的实际起飞时间，您可以将允许的时刻表制定为线性规划问题或半定/二次规划问题。
这里有一些参考：
Here some suggestions.
In principle you can have a graph where every node is a flight and there is an edge from flight A to flight B if B depends on A, i.e. B can't take off before A has landed. You can use this dependency graph to calculate the shortest possible duration for the project --- find the path through the graph that has maximum duration when you add the durations of all the flights on the path together. This is the "critical path" of your project.
However, the fact that you need to pair with planes makes it more difficult, esp. as I guess it is assumed that the planes are not allowed to fly without passengers, i.e. a plane must take off from the same city where it landed last.
If you have an excessive number of planes, allocating them to the flights can be most likely easily with a combinatorial optimization algorithm like simulated annealing. If the plan is very tight, i.e. you don't have excess planes, it could be a hard problem.
To set the actual take-off times for your flights, you can for example formulate the allowed schedules as a linear programming problem, or as a semi-definite / quadratic programming problem.
Here some references:
首先绘制域模型（类图），并在头脑中明确区分：
PlaneType、Plane,Flight,FlightBeforeFlightConstraint, ...PlaneToFlightAssignment将所有这些实例包装在该变量中
Project类（= 解决方案）。然后在这样的解决方案上定义一个得分函数（又名适应度函数）。例如，如果有 2 个
PlaneToFlightAssignments不适用于FlightBeforeFlightConstraint（= 航班依赖性），则降低分数。然后，只需通过更改
PlaneToFlightAssignment实例来找到得分最高的解决方案即可。有几种算法 您可以用来找到最佳解决方案。如果您的数据集真的很小（比如 10 个飞机），您可能可以使用强力。Start with drawing out a domain model (class diagram) and make a clear separation in your mind between:
PlaneType,Plane,Flight,FlightBeforeFlightConstraint, ...PlaneToFlightAssignmentWrap all those instances in that
Projectclass (= a Solution).Then define a score function (AKA fitness function) on such a Solution. For example, if there are 2
PlaneToFlightAssignmentswhich are not ok with aFlightBeforeFlightConstraint(= flight dependency), then lower the score.Then it's just a matter for finding the Solution with the best score, by changing the
PlaneToFlightAssignmentinstances. There are several algorithms you can use to find that best solution. If your data set is really really small (say 10 planes), you might be able to use brute force.