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

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.

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

工件加工时间可控的排序问题与依赖资源指派问题在钢铁制造业及医疗救助业等方面有着广泛的应用，是当今国际研究的热点问题之一。本项目的研究成果主要包括三方面内容：(1)工件的加工时间与开工时间有关的可控排序。考虑单机成组可控排序问题， 对凸资源分配模型，在总资源有限的基础上极小化最大完工时间问题，证明了一种特殊情况是多项式时间可解的。此外对于一般情况，给出了一个启发式算法和分支定界算法。(2)工件加工时间与所排位置有关的可控排序问题。研究了单机情况下具有截断学习效应的可控排序问题。对一系列正则排序目标和资源的费用目标的四种组合情况分别给出了求解算法。对成组情况的单机可控排序问题，对凸资源分配模型，在总资源有限下的最大完工时间极小化问题，给出了求解算法。(3) 工件加工时间同时与所排位置（学习效应）、开工时间（恶化效应）和资源有关的可控排序问题。提出了工件加工时间与开工时间、所排位置和所用资源都有关系的可控排序问题。在单机和不相关平行机情况下，对一些排序目标和资源目标下的各种组合分别进行了分析，证明了一系列问题都存在多项式时间最优算法，对找不到多项式时间算法的问题给出了启发式算法和分支定界算法。