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

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

广义指派问题

广义指派问题可以表述为：指派ｍ位人员执行ｎ项任务,指派人员ｉ执行任务ｊ的收益为ｃｉｊ,需指派人员ｉ执行ａｉ至ａｉ项任务和ｂｊ至ｂｊ位人员执行任务ｊ,问如何指派使总效益最优。广义指派问题可以转化为一个能用对偶运输解法求解的容量运输问题     

分配小于人数和任务数的指派问题的反点算法

摘要：本文对从 个人中派出 个人去完成 项任务中的 项任务使总效率最高这类指派问题给出了新算法，通过对这类指派问题引入了反点的概念，讨论了反点所具有的一些性质并证明了相关结论，利用这些结论找到了通过增加反点来解决此类指派问题的反点算法。     

一类二阶段指派问题

经典的指派问题是研究资源与任务的二元匹配。作为推广,三维指派问题是研究资源、任务与作业的三元匹配。前者已有成熟的有效算法,后者是著名的NP困难问题。本文讨论介于二者之间的一类二阶段指派问题,即可分解为二阶段决策的特殊三维匹配问题,给出多项式时间算法。     

基于全局搜索算法的不平衡指派问题研究

目前求解不平衡指派问题的主要是将其转化为平衡的指派问题后再去处理.针对不平衡指派问题提出了全局搜索算法,算法不用将不平衡问题转化为平衡问题进行求解,而是基于全局最优策略对任务进行指派,方法理论更加简单,操作更加方便,使得不平衡指派问题得到了很好地解决,同时,这种算法对平衡指派问题、运输问题等依然有效.     

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

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

指派问题的解法及其适用范围的拓广

一、前言 指定m个人(或物)去完成m项任务,分派哪个人承担哪项任务,能够使他们花费的总时间为最小(或获得的总效益为最大)?诸如此类的问题,统称为指派问题. 指派问题分成最小化和最大化两类.关于它们的解法,即最优指派方案的计算步骤,本文准备给予周详的阐述. 指派问题的解法,是针对“m个人完成m项任务”提出来的,应用上存在着一定的局限性.为了拓广适用范围,本文就“m个人完成n(相似文献   

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

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

机场任务指派问题的优化方案研究

本文研究了机场任务指派问题,该问题是指将具有特殊属性的任务指派给有限数量的班次。由于机场任务和班次属性的多样性,机场任务指派问题是一个复杂的组合优化问题,属于NP-完全问题。本文以任务完成产生的效益总和最大化为目标建立数学优化模型,提出有效不等式,应用CPLEX软件对实际数据进行求解,结果表明,CPLEX可以在较短时间内对一定规模的算例求得最优解。同时对影响目标函数的四个因素:任务数量、班次数量、班次工作时长和任务属性分别进行分析,通过实际算例测试对比,得出具有指导意义的结论,即根据机场特征分别调整四个因素不仅能够提高机场资源的有效利用率,而且能够提高机场的运行效率和服务水平。     

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

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

Three steps multiobjective decision process for software release planning

This paper deals with how to determine which features should be included in the software to be developed. Metaheuristic techniques have been applied to this problem and can help software developers when they face contradictory goals. We show how the knowledge and experience of human experts can be enriched by these techniques, with the idea of obtaining a better requirements selection than that produced by expert judgment alone. This objective is achieved by embedding metaheuristics techniques into a requirements management tool that takes advantage of them during the execution of the development stages of any software development project. © 2015 Wiley Periodicals, Inc. Complexity 21: 250–262, 2016     

Discrete time/cost trade-offs in project scheduling with time-switch constraints

The discrete time/cost trade-off problem assumes the duration of project activities to be discrete, non-increasing functions of the amount of a single non-renewable resource. The problem has been studied under three possible objectives. The so-called deadline problem involves the scheduling of project activities in order to minimize the total cost of the project while meeting a given deadline. The budget problem aims at minimizing the project duration without exceeding a given budget. A third objective involves the generation of the complete efficient time/cost profile over the set of feasible project durations. In this paper we describe a solution procedure for the deadline problem in which three special cases of time-switch constraints are involved. These constraints impose a specified starting time on the project activities and force them to be inactive during specified time periods. We propose a branch-and-bound algorithm and a heuristic procedure which both make use of a lower bound calculation for the discrete time/cost trade-off problem (without time-switch constraints). The procedures have been coded in Visual C++, version 6.0 under Windows 2000 and have been validated on a randomly generated problem set. We also discuss an illustrative example based on a real-life situation.     

Determination of the possibility of rock burst in a coal seam

The article presents an algorithm for computing a quantity that serves as a criterion for the possibility of rock burst in a coal seam.We propose to seek this quantity in the two steps: At the first step, an inverse problem is solved to find the necessary quantities; while at the second step, we solve a boundary value problem for the biharmonic equation. The inverse problem can be solved by minimizing an objective functional that is shown to be strongly convex.     

On the complexity of project scheduling to minimize exposed time

We consider project scheduling where the project manager’s objective is to minimize the time from when an adversary discovers the project until the completion of the project. We analyze the complexity of the problem identifying both polynomially solvable and NP-hard versions of the problem. The complexity of the problem is seen to be dependent on the nature of renewable resource constraints, precedence constraints, and the ability to crash activities in the project.     

Optimizing the supply chain configuration for make-to-order manufacturing

We consider a make-to-order (MTO) manufacturer who has won multiple contracts with specified quantities to be delivered by certain due dates. Before production starts, the company must configure its supply chain and make sourcing decisions. It also needs to plan the starting time for each production task under limited availability of resources such as machines and workforce. We develop a model for simultaneously optimizing such sourcing and planning decisions while exploiting their tradeoffs. The resulting multi-mode resource-constrained project scheduling problem (MMRCPSP) with a nonlinear objective function is NP-complete. To efficiently solve it, a hybrid Benders decomposition (HBD) algorithm combining the strengths of both mathematical programming and constraint programming is developed. The HBD exploits the structure of the model formulation and decomposes it into a relaxed master problem handled by mixed-integer nonlinear programming (MINLP), and a scheduling feasibility sub-problem handled by constraint programming (CP). Cuts are iteratively generated by solving the feasibility sub-problem and added back to the relaxed master problem, until an optimal solution is found or infeasibility is proved. Computational experiments are conducted to examine performance of the model and algorithm. Insights about optimal configuration of MTO supply chains are drawn and discussed.     

Time-cost trade-off via optimal control theory in Markov PERT networks

We develop a new analytical model for the time-cost trade-off problem via optimal control theory in Markov PERT networks. It is assumed that the activity durations are independent random variables with generalized Erlang distributions, in which the mean duration of each activity is a non-increasing function of the amount of resource allocated to it. Then, we construct a multi-objective optimal control problem, in which the first objective is the minimization of the total direct costs of the project, in which the direct cost of each activity is a non-decreasing function of the resources allocated to it, the second objective is the minimization of the mean of project completion time and the third objective is the minimization of the variance of project completion time. Finally, two multi-objective decision techniques, viz, goal attainment and goal programming are applied to solve this multi-objective optimal control problem and obtain the optimal resources allocated to the activities or the control vector of the problem     

可抢占条件下的项目调度研究综述

可抢占条件下的项目调度通过暂时中断某些活动的执行,释放资源给更重要的活动,从而优化项目的工期、成本等绩效指标。可抢占项目调度问题以其重要的理论价值和应用背景,受到了学界和业界的广泛关注。对国内外可抢占项目调度的研究成果进行了系统性总结与梳理,综述了可抢占项目调度问题的数学模型及其求解算法,总结了可抢占项目调度问题的一些扩展问题和应用情况,最后指出了未来进一步的研究方向。     

Iterative algorithms for the curfew planning problem

The curfew planning problem is to design an annual timetable for railway track maintenance teams. Each team is capable of handling certain types of repairs and replacement jobs. The jobs are combined into a set of projects according to their locations and types. The timetable shows which project should be worked on by each team on a weekly basis throughout an entire year. Our objective is to design a schedule with minimum network disruption due to ongoing maintenance projects that require absolute curfew. Absolute curfew projects are those that cause complete closure of the rail traffic. For tackling this problem, we develop four optimization-based iterative algorithms. We also present very promising computational results obtained within a few minutes using data provided by a major North American railroad.     

Multi-period lot-sizing with supplier selection: Structural results,complexity and algorithms

We consider a multi-period lot-sizing problem with multiple products and multiple suppliers. Demand is deterministic and time-varying. The objective is to determine order quantities to minimize the total cost over a finite planning horizon. This problem is strongly NP-hard. For a special case, we extend the classical zero-inventory-ordering principle and solve it by dynamic programming. Based on this new extension, we also develop a heuristic algorithm for the general problem and computationally show that it works well.     

Project Scheduling under Time Dependent Costs – A Branch and Bound Algorithm

In a given project network, execution of each activity in normal duration requires utilization of certain resources. If faster execution of an activity is desired then additional resources at extra cost would be required. Given a project network, the cost structure for each activity and a planning horizon, the project compression problem is concerned with the determination of optimal schedule (duration) of performing each activity while satisfying given restrictions and minimizing the total cost of project execution. This paper considers the project compression problem with time dependent cost structure for each activity. The planning horizon is divided into several regular time intervals over which the cost structure of an activity may vary. But the cost structure of the activities remains the same (constant) within a time interval. Key events of the project attract penalty for finishing earlier or later than the corresponding target times. The objective is to find an optimal project schedule minimizing the total project cost. We present a mathematical model for this problem, develop some heuristics and an exact branch and bound algorithm. Using simulated problems we provide an insight into the computational performances of heuristics and the branch and bound algorithm.