航空货运码头裝卸平台预定问题及算法研究

【类型】学位论文

【作者】朱建新 

【关键词】 航空货运 在线预订 排序 算法 流水作业 开放作业

【摘要】本文研究了以现代服务业预订系统中的实际问题——航空货运码头装卸平台预定问题为背景的具有预约到达时间的在线排序问题,不仅考虑了单一任务装卸平台的在线预定问题(1|on-line,Oj,rj,pj|Cmax),特别地,考虑了其中的特殊情形(1|on-line,Oj,rj,Pj=p|Cmax),还考虑了多任务装卸平台在线预定问题中流水作业任务的在线预定问题(F2| on-line,Oj,rj,Pj|Cmax)和开放作业任务的在线预定问题(O2| on-line,Oj,rj,Pj|Cmax).对这些问题,提出了在线贪婪算法：包含任务信息的订单到达系统后,马上对任务的加工作出安排,然后再接收下一个订单。然后分析了在线贪婪算法对各个问题的竞争比,得到了下面的结论：(1)在线贪婪算法对单一任务装卸平台的在线预定问题模型化为的1|on-line, Oj,rj,Pj|Cmax问题的竞争比为2,特别地,当限制条件pj=p时,即对问题1| on-line,Oj,rj,Pj|Cmax,算法的竞争比达到了3/2;(2)在线贪婪算法对流水作业任务的在线预定问题模型化为的F2|on-line, Oj,rj,Pj|Cmax问题的竞争比为2;(3)通过分析任务在机器1,机器2上面的加工情况,得到了机器1和机器2上面空闲加工区间的一些性质。然后,以此为切入点,分3类情形证明了在线贪婪算法对开放作业任务的在线预定问题模型化为的O2|on-line,Oj,rj, Pj|Cmax问题的竞争比为2。最后,通过两个算例,分析了在线贪婪算法的实际应用。本文所提出的算法能够得到每个货运代理商的实际收发货时间,从而减少了货运代理商的排队等候时间,有效地调节了航空货运站的闲忙程度。

【学位名称】硕士

【学位授予单位】复旦大学

【学位授予年度】2016

【导师姓名】张显东

【读秀链接】读秀链接