复杂环境下不确定瓶颈指派问题研究

Bottleneck assignment problems have a very wide range of applications in manufacturing scheduling, personnel scheduling and vehicle scheduling. Complex environments often contain uncertain factors that have a significant impact on developing an assignment scheme. Hence, how to solve the bottleneck assignment problems in complex environments is worthy of discussion and study. This research investigates uncertain bottleneck assignment problems in complex environments, with the aim to provide the optimal assignment schemes for bottleneck assignment problem, lexicographic bottleneck assignment problem and quadratic bottleneck assignment problem. Firstly, influence of the uncertainty on the progress of the project and the work efficiency is analyzed. Next, uncertain maximum cardinality matching problem and uncertain maximum weighted matching problem are studied. However, in many cases, uncertainty and randomness simultaneously appear in a bottleneck problem. Hence, chance theory is used to describe this phenomenon. Models of uncertain bottleneck assignment problems are established. Secondly, mathematical properties are analyzed by mathematical derivation and proof. According to the mathematical properties of different models, two types of algorithms are developed. One is to convert bottleneck assignment problems into equivalent uncertain network optimization problems and design exact algorithms; the other is to develop heuristic algorithms giving the lower bound. Finally, the problems are solved and assignment schemes are given. This research will provide basic theory and methods for solving the uncertain bottleneck problem in complex environments.

瓶颈指派问题在工序优化、人员排班和车辆调度中有非常广泛的应用。复杂环境中包含的不确定因素将对最终指派方案的制订产生关键影响。因此，求解复杂环境下不确定瓶颈指派问题是值得深入探讨和研究的课题。本项目以瓶颈指派问题为研究对象，以提供最合适指派方案为目标，研究复杂环境下一般不确定瓶颈指派问题、不确定字典序瓶颈指派问题和不确定二次瓶颈指派问题。首先，分析不确定工作完成的可能性和不确定工作效率对指派方案的影响，研究不确定最大基数匹配和最大赋权匹配问题。在此基础上分析同时有多种不确定变量对指派方案的影响，建立不确定瓶颈指派问题模型。然后，通过数学推导和证明，分析不同模型的性质，分别设计精确算法（将不确定瓶颈指派问题转化为等价不确定网络优化问题进行求解）和启发式算法（计算问题下界）。最后，求解模型，给出指派方案。本项目的研究将为制订复杂环境下不确定瓶颈指派问题的指派方案提供基本理论和方法。

在管理中经常遇到瓶颈指派问题，如作业调度，集成电路布线和工厂位置布局等。目前，确定性瓶颈指派问题和随机瓶颈指派问题已经得到了长足发展。然而，实际复杂环境中，不仅有常数和随机变量，而且还有其他不确定变量。为了解决多种变量共存的瓶颈指派问题，本项目研究复杂环境下不确定瓶颈指派问题。研究内容涉及理论研究和实际应用两个方面。基本建立了复杂环境下不确定瓶颈指派问题的理论框架，包括模型的建立，数学性质的推导和分析，有效求解算法的设计。所设计的算法可以得到所有不确定随机变量的机会分布。另外，还将理论用于实际管理中，选择学生参加河南省物流仿真设计大赛，并最终获得一等奖。文献检索表明，本项目的研究已经被其他研究者应用于网络优化，图论和不确定规划等领域。