基于学习效应的资源分配排序问题研究

For classical scheduling problems, it is assumed that the processing time of a job is a fixed constant. However, in many realistic problems of operations management in which job processing times may be subject to change due to the phenomenon of learning and resource allocation, then the the resource allocation scheduling problems with learning effects are produced, such problems are an important combinatorial optimization problem, is one of the hot issues in today's international research. This research project considers resource allocation scheduling problems with learning effects by using the submodular optimisation techniques, computer algorithm analysis and operations research methods, main contents are as follows: (1) For the linear resource allocation function and convex resource allocation function, considering some just-in-time objective functions; (2) Propose new resource allocation scheduling models with learning effects, analysis the characteristics of these models, and give algorithm; (3) By using the submodular optimisation techniques, the branch and bound algorithms and heuristic algorithms, studing the computational complexity and algorithms of the various kinds combination of the total completion time cost and the total resource consumption cost.

经典排序问题中一般假定工件的加工时间为给定常数，然而在现实的生产过程中，工件的加工时间可能受所排位置和（或）所用资源的影响，由此产生基于学习效应的资源约束排序问题，此类问题是一类重要的组合优化问题，是当今国际研究的热点问题之一。本项目主要运用次模优化技术、计算机算法分析和运筹学方法来研究工件加工时间既有学习效应，又与所用资源有关的排序问题。主要研究：（1）在线性资源与凸资源条件下工件提前时间和延误时间有关的准时制目标函数等问题；（2）提出更符合实际的具有学习效应和资源分配的排序模型，分析此模型的特性并给出求解算法；（3）运用次模优化技术，分支定界法及基于软计算的搜索算法，研究使总完工时间费用和总资源消耗费用的各种组合下，这些问题的求解算法。

研究基于学习效应、恶化效应和资源分配排序问题，对单机问题、流水作业问题和成组排序问题，建立了排序模型。根据各个具体模型的特点，考虑最小化正则及非正则目标函数问题。目标函数包括最小化最大完工时间、总完工时间、加权总完工时间、完工时间（等待时间）的总偏差的加权和、与工期相关的非正则目标函数等。对提出的问题证明了它们有一些是多项式时间可解的，有一些是NP-难的，并给出相应的分支定界算法和启发式求解算法。