加工时间可控排序问题及依赖资源指派问题研究

项目名称： 加工时间可控排序问题及依赖资源指派问题研究

项目编号： No.71471120

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 管理科学

项目作者： 王吉波

作者单位： 沈阳航空航天大学

项目金额： 58万元

中文摘要： 运用运筹学方法、计算机算法分析和数值仿真来研究工件加工时间可控的排序问题与依赖资源指派问题模型，并对这些复杂模型进行理论分析和仿真研究，以求深刻理解这些问题的本质。1.研究完工时间费用为加权完工时间平方和、加权总延迟时间、一些非正则等更复杂实用的目标函数及资源凸函数有界条件下极小化加权总完工时间等若干未解决的问题；2. 对于NP-难问题，主要基于列生成的分支定界法研究小规模问题的最优算法，大规模问题的启发式算法和基于软计算的搜索算法等来设计高速有效的近似算法及启发式算法；3.依赖资源指派问题中，指派费用函数为线性函数和凸函数的情况下，研究总指派成本和总资源消耗成本的各种组合下，这些问题的计算复杂性和提出优化算法。工件加工时间可控的排序问题与依赖资源指派问题更为实用，也更为复杂，绝大多数都是NP-难的，通过探讨可行排序或最优排序的局部及整体性质和数量关系，建立系统有效的计算方法和基本理论。

中文关键词： 排序；可控加工时间；指派问题

英文摘要： This research project considers scheduling problems with controllable processing times and resource dependent assignment problem by using the operational research method, computer algorithm analysis and numerical simulation methods, and studies theory analysis and simulation research of these complex models, in order to deeply understand the nature of these problems, main contents are as follows: 1. Considering job completion cost such as the weighted sum of squared completion times, the total weighted tardiness, some non-regular more complex practical objective functions and some unresolved problems such as minimize the total weighted flow time subject to a constraint on the total amount of resource consumed; 2. For NP-hard problems, proposing the branch and bound algorithms based on column generation methods for small-sized problems, and high-speed and effective approximate algorithms and heuristic algorithms for large-sized problems; 3. For the resource dependent assignment problem in which the assignment cost function is a linear function and a convex function, consider the computational complexity and algorithms of the various kinds combination of the total assignment cost and the total resource consumption cost. The scheduling problems with controllable processing times and resource dependent assignment problem are more useful and complex than classical scheduling problems and linear assignment problem, most of which are NP-hard problems, by making insights into the local and global structural properties and relations of the feasible and optimal solutions, systematic basic theories and effective computational methods will be established.

英文关键词： scheduling;controllable processing times;assignment problem