4-1排班问题1.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,规划篇,线性规划在民航排班中的应用,池宏、杨文国,2012,年,11,月,4,日,飞机地面作业系统应用研究的目标,拟通过深入分析在各种情况下，各种作业需求和各种资源的供需关系和相应的需求量；研究在不同情况下，如何合理地安排地面作业的工作、有效地利用各种资源的方法；为飞行安全和正点率提供有力地保障，同时使作业成本尽可能地小任务需求分析,采用项目管理中的网络计划方法描述飞机过站时，,地面作业工序间的逻辑关系；,每道工序的平均完成时间；,整个过程的完成时间；,关键路线（主要矛盾线），即：影响整个地面作业时间的工序任务需求分析,飞机到位，机务放轮档（若飞机未能停靠到位，还需拖车牵引）,廊桥或客梯车靠客舱门,边防、卫生检疫、海关接机人员在飞机外与乘务长交接旅客、机组名单等,服务人员到机舱口引导旅客下机，下客,(,若旅客需要轮椅、担架，需特服或者平台车到位,),商务人员接舱单,清洁队清洁客舱,食品公司上机回收餐车并装食品,机务人员上机询问了解飞机状况，检查舱内设备完好情况,平台车或传送带靠货舱门，卸行李,卸货,装货,装行李,通知并组织上客,油料公司油车到位加油,电源车靠机作业,污水车、垃圾车、加水车靠机作业,值机人员送舱单等文件,关舱门,拖车拖出飞机,任务需求分析,各项作业的顺序及逻辑关系,作业,紧前作业,作业,紧前作业,A,B,C,D,E,F,G,H,I,J,A,B,B,B,C D E,C D E,B,A,I,K,L,M,N,O,P,Q,R,S,J,K,G F,A,A,A,N L,Q H M P,R,任务需求分析,单机过站地面作业网络图,A,S,O,B,C(5),D,H,E(5),F,G,Q,R,N,M,I,P(15),7,2,3,17,4,12,11,5,16,15,9,8,6,J,K,L(15),18,1,多机作业的资源需求,多机作业计划分析,在多机的情况下，尤其是在航班进出港的高峰时段，就有可能发生按照现在的计划安排出现某种资源紧缺的情况，从而造成航班的延误。

因此，我们必须根据现有的资源情况，针对不同时段的资源需求，设计合理安排和配置各种资源的科学方法，以制定相应的实际作业计划多机作业计划分析,考虑的因素：时间、所需资源量、机型、到站旅客数、离站旅客数,飞机号,时间,1,号机,2,号机,3,号机,4,号机,研究的基本方法,本研究将以项目管理和统计分析为基本方法，研究一套适合民航地面作业中资源优化配置的启发式原则和算法；,研究将从单机起降前后的地面作业分析入手，分析这些作业的逻辑关系和完成时间，分析每一个时段中，不同飞机起降的时间和停机位的相关关系，进而得出不同时段对各种资源的需求；,分析现有资源的状况；针对不同时段的资源需求以及满足这些需求的时间区间，研究飞机地面作业系统资源优化配置的对策、措施、方法，特别是对资源需求大的时段，提出相应的地面作业的预案，来保证飞机运行的安全性和正点率生产运行系统,数据库,地面作业系统,数据库,每一个作业的,作业时间分析,客梯、摆渡车的优化调度,清洁飞机的,作业优化,行李、货物的装卸作业优化,拖车、拖把的调度优化,地面作业的,实施方案,地面作业的,监控、调整,基础层,分析层,模块层,综合层,民航地面实时调度系统的概念框架,航班信息子系统,FOIS,地面服务动态信息,子系统,机务,商务,燃料,清洁,上客,资源,资源,资源,资源,1,2,3,n,现场调度站,现场指挥中心,现场调度站,现场通信子系统,对于调度中心、现场调度站都是可见的，通过大屏幕显示,进入滑行,进入机位,Time,资源位置,航班预报、实时变更,机位信息,实时调度优化计算机辅助系统,各项作业服务的实时,状态信息，如进入、,完成、车,/,组号、作业,负责人，问题等,一个简单的问题？,对于有限的清洁队人力资源，如何安排工人的上班时间（假设按现在的六小时工作制），能够最佳地保证航班（进港、过站、离港）清洁作业的需要，同时使得劳动力资源能够,“,均衡地,”,安排在所需要的时间段内（航班繁忙时候有比较多的人在上班，相对空闲时候在班的人数相对地少），以最高效利用的人力资源，满足航班生产对机舱清洁的要求。

影向问题的因素,航班作业的需求,清洁工上班的方式,高峰,/,低谷时段的剩余资源的要求,不同时段工作的强度和工资标准：如每个工人每一小时可完成的作业数,假设机舱清洁队可以分成若干作业小组（如,5,人一组，这里我们考虑人数，即每个人视为一组）设机舱清洁工人可能的上班方式有,n,种：例如,方式 工作时间段 工作小时数,1 6AM12AM 6,2 7AM1PM 6,3 8AM2PM 6,4 10AM4PM 6,5 12AM6PM 6,6 4PM10PM 6,n 8PM12PM 4,接下来，我们可以通过统计分析，得到给定每小时所需要的机舱清洁工人人数，可以按照每个小时起降航班数和飞机类型，估计出为满足这些航班清洁作业所需要的定额数：例如,小时单位 所需要的作业人数,6AM7AM 46,7AM8AM 38,8AM9AM 116,9AM10AM 145,10AM11AM 92,11AM12AM 64,11PM12PM 27,数据准备与分析,本问题的核心条件是要知道，按每个小时作为一个时间区间，根据航班数量和飞机类型（决定清洁作业的额定人数），需要多少个清洁工人，能够满足作业需求为了估计这些人数，我们可以采用两种方法：,分析某一天的典型数据。

根据有代表性的一天的航班数量，航班性质，飞机类型，过站时间等，计算出每架飞机所需的作业人数，将这些人数加起来，在分析确定每个清洁工人在这一小时能完成的飞机数（称为作业效率指数），两者相乘，可以得到每小时的需求人数的估计抽取多日航班数据，按照,1,）的方法计算每天每小时的人数需求量，对这些数据求统计均值，作为代表数据第二种方法显然所需要的数据量大，但得到的结果具有更好的平均代表性，而第一种方法具有更好的典型性，我们可以典型抽取不同季节、不同时期的航班数据，随时计算更新计划方案在下面的分析中，我们采用第一种方法计算需求数，按照,2002,年,11,月某一天航班数据作为代表性数据图,1,是该日需求的曲线，其中我们取作业效率指数为,0.4,，相当于每个清洁工人每小时可以清洁,2.5,架飞机，各种机型清洁工作人数按照表,1,来确定机型 出港航班 过站航班 进港航班,BAE-146,及以下,36 6,737-800,以下机型,38 8,762,、,763,、,765 516 16,777-200,、,777-300 820 20,747,、,A340,、,DC-10 820 20,决策变量的状态矩阵,当班组数,时 间,投入组数,0600,0700,0800,.,.,.,.,.,.,.,.,2300,最优倒班安排方案（,Shifting Problem),设有,M,个时段，最优安排倒班组数的模型为：,清洁小组数,时，目标变为求最少的,取,班下的工资标准，当均,为,班下安排多少清洁小组,为决策变量，表示,组数量；,小时段所需要的清洁小,其中,为整数变量,1,0,.,min,2,2,1,1,2,2,2,22,1,21,1,1,2,12,1,11,2,2,1,1,j,c,j,x,i,b,x,b,a,x,a,x,a,b,a,x,a,x,a,b,a,x,a,x,a,t,s,x,c,x,c,x,c,j,j,j,j,m,mn,m,m,n,n,n,n,=,+,+,+,+,+,+,+,+,+,+,+,+,L,M,L,L,L,最优排班方案的数学模型,最优整数规划问题,由于问题的特殊结构，可规成求解线性规划问题,这是一个线性整数规划问题，一般性的整数规划问题是很难得到最优解（,NP-Hard,）的，但本问题的约束矩阵,A,具有特殊结构，由于工人上班是连续工作的，这种工作方式使得,A,的每一列在取值为,1,的位置上是连续的，例如在第一种排班方式下，第一列从第一行到第六行均为,1,，其余为零。

可以证明，该线性整数规划问题松弛为一般的线性规划问题时，所得到的解就是整数解，这给我们求解出最优方案提供了条件0600-120042,0700-130019,0800-140020,0900-150045,1000-1600 3,1100-170031,1200-180011,1300-1900 0,1400-200051,1500-2100 8,1600-2200 1,1700-2300 0,1800-240038,谢谢,。