一种具有区间数信息的多目标指派方法

针对具有区间数信息的多目标指派问题,给出了一种指派方法。首先,将不同类型目标的区间数损益矩阵规范化为区间数成本矩阵,并应用区间数运算法则构建区间数多目标指派问题的总成本矩阵。然后,通过事先定义的任意两个区间数的序关系,将区间数指派问题优化模型转化为一个双目标优化模型,并采用线性加权法将其转化为单目标优化模型来进行求解,同时还考虑了如何处理人员数量与任务数量不相等的情形的指派问题;最后,通过一个实例分析说明了本文给出方法的可行性和有效性。本文的方法丰富了已有的求解方法,具有实际应用价值。     

基于“员工技能库”的多技能员工动态指派

针对在复杂市场需求环境的新订单到达情况,具有不同技能数量和技能水平的多技能员工为完成新订单的指派问题,提出基于"员工技能库"的、满足交货期的多技能员工动态指派方案,给出了与实际情况相吻合的约束条件,建立相应的0-1整数规划模型.并设计了采用优先规则的启发式算法,在每次迭代中优先选择与订单最低需求基本匹配的员工加以指派任务,直至所有任务都完成指派,通过算例测试表明,基于"员工技能库"的动态指派方案能快速准确地进行员工指派.     

考虑人员培训的任务指派问题模型及算法

随着劳动力成本的快速增长,越来越多的企业选择雇佣兼职员工。本文研究了中国一家家居企业的任务指派问题,该任务指派问题的特点是一个任务由多个子任务组成,并在安排时需要同时考虑人员培训和满足客户的服务时间的要求,该问题的目标是安排尽可能多的家装任务并获得尽可能多的收益。为了解决该问题,本文建立了整数规划模型,并设计高效的局部分支算法对模型进行求解。为了获得最佳的求解效果,我们实验分析了不同的分支变量和参数设置对算法性能的影响,并获得了最佳的参数设置。特别的,我们发现有效分支变量的选择与问题特点相关。实验还表明,在相同求解时间内,在13个算例中,局部分支算法在9个算例上的表现优于Gurobi。     

基于可能度排序法的区间信息指派方法

针对具有区间数信息的多目标指派问题,利用区间数可能度排序方法,给出了一种新的指派方法.该方法充分利用实际所给的区间信息进行求解,克服了以往这类指派问题最后由多目标问题转换为单目标问题时权数确定主观性大的缺陷.最后给出了该方法的一个算例.     

多因素指派模型全局优化问题研究

基于多因素资源优化分配问题的不确定性,建立基于区间数型下的不确定多因素指派模型,给出模型建立的理论依据与全局优化算法,拓展区间数型多因素指派模型,解决了不确定条件下多因素资源优化分配问题.考虑多因素影响,基于任务完成效率,以5类任务多因素分配问题为例,获得了指派模型全局优化的解.为不确定条件下资源优化分配问题的研究拓宽了决策途径.     

项目多技能人力资源指派与调度混合算法

研究多技能人力资源在项目活动上的指派与调度问题.首先,从问题特点出发,把原始问题分解为指派问题子模型和调度问题子模型.然后,对项目活动间的重叠关系进行识别,将其转化为对指派问题的有效约束,构建数学规划与约束规划相结合的混合算法对问题求解,并采用CPLEX编程实现.研究表明,算法可有效缩减指派问题的可行域,快速地找到问题的近优解,从而提高多技能人力资源的使用效率,是求解项目多技能人力资源指派与调度问题的一个有效方法.     

飞机维修短期计划模型及其算法研究

目前对于飞机维修计划的研究,大都通过精确算法一次性完成周期内所有飞机的排班优化。本文在分析传统数学规划模型的基础上,以最大化利用两次维修之间的可用飞行时间为目标,构造了飞机维修计划优化模型。然后提出了求解此模型的启发式两阶段分解算法,第一阶段优先完成需维修飞机的任务指派,第二阶段再完成余下飞机的任务指派。利用航空公司真实数据进行的数值试验表明,两阶段分解算法能够显著提高模型的求解效率和质量,可以有效求解大规模飞机维修计划制定问题。     

呼叫中心坐席人员排班问题优化模型与算法研究

国内呼叫企业在保证每个坐席人员周内当值相同班次情况下,通过灵活安排周内当班日期与班次来制定排班方案。针对该实际排班场景,构建问题整数规划模型。通过对问题数据特征及优化性质分析,以及对班次人力有效满足区段电话服务需求的量化指标表征,分别提出两个构造性启发式算法。使用企业实例数据对模型算法进行计算实验。实验结果显示,整数规划模型适合于求解小规模排班问题最优解,而启发式算法能够以小计算成本获得大规模排班问题优化解。最后讨论保证员工上班规律性的同班次用工制度对企业人力成本控制的影响。     

非平衡指派模型及其在航空机务维修中的应用

非平衡指派问题是最优平衡指派问题的推广与深化,在航空机务维修工作中,维修任务的合理配置对及时完成维修任务,保障训练作战计划非常重要.本文从装备完好率和人力资源的优化配置角度出发,按照不考虑维修任务等待时间和考虑维修任务等待时间两种情况分别建立了非平衡指派优化模型,并给出了这两种情况下效益矩阵的构造方法,进而将优化模型转化为最优平衡指派模型进行求解,从而为航空机务维修工作中维修人员的优化配置提供了一种科学、合理的决策方法.     

基于多目标规划的飞机路径恢复最优化算法研究

本文针对同一机场中同机型的多架飞机受到干扰后, 飞机路径恢复的多目标最优化问题进行研究。首先根据航空公司实际航班调整的常用原则和航班干扰管理的基本思想, 基于连接网络建立多目标规划模型, 其中两个目标按照优先级排列:第一个目标为最小化航班的最大延误时间, 第二个目标为最小化参与交换的飞机数量。然后根据该问题的航班波结构特点, 结合求解多目标规划的分层序列法, 分析优化问题的若干最优性质, 并基于快速排序算法和最小费用路算法设计出多项式算法。最后用算例验证了算法的有效性。该研究结果可以为航空公司减少航班延误提供理论和技术支持。     

面向靠桥率及道口冲突率的航班-机位指派问题优化模型及其启发式算法研究

在给定航班时刻表条件下,对于进出港航班的机位分配,除了必须满足航班、飞机和机位之间的技术性要求之外,还要考虑尽量提高整个机场的机位利用率,且方便旅客出入港及时、安全和便捷.文章以飞机机型、所属航空公司、客运/货运航班、国内/国际航班等匹配条件为约束条件,以航班-机位分配完成率、靠桥率、道口非冲突率为目标,建立了一个航班-机位指派问题的全局优化模型.基于国内某机场的真实应用场景及其待决策变量维度的超大规模,导致模型求解成为一个NP-COMPLETE的混合整数规划问题.文章提出一种启发式快速求解算法,基于贪婪规则建立若干优先级队列的航班冲突调整方案,按照3个指标重要程度渐次探求近似最优解.而且,对于每一步贪婪规则的改进,文章都进行了算法有效性检验以及计算性能的对比实验.最终多重对比实验的结果表明,新算法的结果在与理论最优解差距不足3%的代价下,可节约超过90%求解时间.     

Assigning cooperating UAVs to simultaneous tasks on consecutive targets using genetic algorithms

A problem of assigning multiple agents to simultaneously perform cooperative tasks on consecutive targets is posed as a new combinatorial optimization problem. The investigated scenario consists of multiple ground moving targets prosecuted by a team of unmanned aerial vehicles (UAVs). The team of agents is heterogeneous, with each UAV carrying designated sensors and all but one carry weapons as well. To successfully prosecute each target it needs to be simultaneously tracked by two UAVs and attacked by a third UAV carrying a weapon. Only for small-sized scenarios involving not more than a few vehicles and targets the problem can be solved in sufficient time using classical combinatorial optimization methods. For larger-sized scenarios the problem cannot be solved in sufficient time using these methods due to timing constraints on the simultaneous tasks and the coupling between task assignment and path planning for each UAV. A genetic algorithm (GA) is proposed for efficiently searching the space of feasible solutions. A matrix representation of the chromosomes simplifies the encoding process and the application of the genetic operators. To further simplify the encoding, the chromosome is composed of sets of multiple genes, each corresponding to the entire set of simultaneous assignments on each target. Simulation results show the viability of the proposed assignment algorithm for different sized scenarios. The sensitivity of the performance to variations in the GA tuning parameters is also investigated.     

一类广义指派问题的有效解法

提出一类广义指派问题,这类问题研究的是m个人执行n项任务,每个人执行的任务数、执行每项任务的人数以及总的指派人项数均有限制,要求最优指派.对这类广义指派问题建立了数学模型,并找到一种转换方法,将这类问题转换为平衡指派问题,从而用传统方法,如匈牙利法求解.最后用一个箅例来说明这种转换方法的简便和有效性.     

Network flow models for intraday personnel scheduling problems

Personnel scheduling problems can be decomposed into two stages. In the first stage for each employee the working days have to be fixed. In the second stage for each day of the planning period an intraday scheduling problem has to be solved. It consists of the assignment of shifts to the employees who have to work on the day and for each working period of an employee a task assignment such that the demand of all tasks for personnel is covered. In Robinson et al. (Burke and Trick (Eds.), Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling, 18th August–20th August 2004, Pittsburgh, PA, USA, pp. 561–566, 2005), the intraday problem has been formulated as a maximum flow problem. The assumptions are that, employees are qualified for all tasks, their shifts are given, and they are allowed to change tasks during the day. In this work, we extend the network flow model to cover the case where not all employees are qualified to perform all tasks. The model is further extended to be able to calculate shifts of employees for the given day, assuming that an earliest starting time, a latest finishing time, and a minimal working time are given. Labour cost can be also taken into account by solving a minimum cost network flow problem.     

Heuristic Solution Methods for the Multilevel Generalized Assignment Problem

The multilevel generalized assignment problem is a problem of assigning agents to tasks where the agents can perform tasks at more than one efficiency level. A profit is associated with each assignment and the objective of the problem is profit maximization. Two heuristic solution methods are presented for the problem. The heuristics are developed from solution methods for the generalized assignment problem. One method uses a regret minimization approach whilst the other method uses a repair approach on a relaxation of the problem. The heuristics are able to solve moderately large instances of the problem rapidly and effectively. Procedures for deriving an upper bound on the solution of the problem are also described. On larger and harder instances of the problem one heuristic is particularly effective.     

考虑多救援点的突发事件应急救援人员派遣模型

针对具有多救援点的突发事件应急救援人员派遣问题,给出了一种应急救援人员派遣模型。首先,依据救援人员关于救援任务的能力指标评价值计算出不同出救点的救援人员对救援点中救援任务的胜任度;其次,依据救援人员到达救援点的应急救援时间计算出应急救援时间满意度;然后,将救援人员对救援点的胜任度与应急救援时间满意度进行集结,获得应急救援人员与各救援点的综合匹配度;进一步地,以综合匹配度最大为目标,构建应急救援人员派遣优化模型,并通过模型求解获得最优的应急救援人员派遣方案;最后,通过一个算例说明了所构建的应急救援人员派遣模型具有可用性。     

军用飞机维修质量管理的最优线性分派评估

在军机维修工作中,科学有效的管理,对及时完成维修任务,保障训练作战计划至关重要.在建立适合我军军机维修质量评估指标体系的基础上,定义了理想方案和贴近度,给出了排序频数的计算方法,进而将军机维修质量评估问题转化为最优线性分派问题来处理,从而为军机维修质量管理提供了一种科学、可靠的决策方法.     

Airport management: taxi planning

The Taxi Planning studies the aircraft routing and scheduling on the airport ground. This is a dynamic problem, which must be updated almost every time that a new aircraft enters or exits the system. Taxi Planning has been modelled using a linear multicommodity flow network model with side constraints and binary variables. The flow capacity constraints are used to represent the conflicts and competence between aircrafts using a given airport capacity. The “Branch and Bound” and “Fix and Relax” methodologies have been used. The computational tests have been run at the Madrid-Barajas airport, using actual data from the airport traffic.     

A genetic algorithm for robotic assembly line balancing

Flexibility and automation in assembly lines can be achieved by the use of robots. The robotic assembly line balancing (RALB) problem is defined for robotic assembly line, where different robots may be assigned to the assembly tasks, and each robot needs different assembly times to perform a given task, because of its capabilities and specialization. The solution to the RALB problem includes an attempt for optimal assignment of robots to line stations and a balanced distribution of work between different stations. It aims at maximizing the production rate of the line. A genetic algorithm (GA) is used to find a solution to this problem. Two different procedures for adapting the GA to the RALB problem, by assigning robots with different capabilities to workstations are introduced: a recursive assignment procedure and a consecutive assignment procedure. The results of the GA are improved by a local optimization (hill climbing) work-piece exchange procedure. Tests conducted on a set of randomly generated problems, show that the Consecutive Assignment procedure achieves, in general, better solution quality (measured by average cycle time). Further tests are conducted to determine the best combination of parameters for the GA procedure. Comparison of the GA algorithm results with a truncated Branch and Bound algorithm for the RALB problem, demonstrates that the GA gives consistently better results.