Bru*_*uno 8 algorithm scheduling graph gantt-chart
我正在开发一个航班调度应用程序(免责声明:这是一个大学项目,所以没有代码答案,请).请在回答之前阅读这个问题,因为它有很多特点:(
首先,一些术语问题:
你有飞机和飞机,你必须配对它们.为简单起见,我们假设一旦飞机使用它之前飞机就会自由飞行.
航班被视为任务:
飞机可被视为任务(或航班,在我们的术语中)使用的资源.
航班需要特定类型的飞机.例如,飞行200需要B型飞机.飞机显然是一种且只有一种特定类型,例如,Plane Airforce One属于C型.
"项目"是航空公司在给定时间段内的所有航班的集合.
所需的功能是:
找到所述项目的最短持续时间
任务的最早和最新可能开始(飞行)
基于提供的数据的关键任务包括先前任务的标识符.
自动配对航班和飞机,以便让所有航班与飞机配对.(注意:航班的持续时间是固定的)
获取项目计划的甘特图,其中所有航班尽早开始,以图形方式显示所有先前引用的数据(依赖关系,时间信息等)
所以问题是:我如何在世界上实现这一目标？尤其:
如果您还可以推荐一些算法供我们查找,那就太好了.
这里有一些建议.
原则上你可以有一个图表,其中每个节点都是一个航班,如果B依赖于A,那么从航班A到航班B有一个边缘,即B在A着陆之前无法起飞.您可以使用此依赖关系图来计算项目的最短持续时间 - 当您将路径上的所有航班的持续时间加在一起时,查找具有最长持续时间的图表中的路径.这是您项目的"关键路径".
然而,你需要与飞机配对的事实使得它更加困难,尤其是.因为我猜这架飞机不允许在没有乘客的情况下飞行,即飞机必须从最后降落的同一个城市起飞.
如果您的飞机数量过多,使用模拟退火等组合优化算法很可能很容易将它们分配给飞行.如果计划非常紧张,即你没有多余的飞机,这可能是一个难题.
要设置航班的实际起飞时间,您可以将允许的航班时刻表定为线性规划问题,或者作为半定/二次规划问题.
这里有一些参考: