Studies on Approximation Algorithm for Multi-objective Discrete Optimization Problems

在研究中，我们研究了多目标离散优化问题，包括多目标调度问题、网络设计问题和多目标设施选址问题等，并提出了优化的近似方法。应用非线性泛函分析方法，研究了模糊微分方程组和模糊优化问题，为优化奠定了基础。在分析多目标调度问题时，我们不仅引入了一种新的具有模糊性和适应性的调度问题模型，而且通过发展新的下界计算，提出了非支配解的算法和基于波束搜索法的一些算法。数值实验表明了该算法在多目标流水作业问题中的有效性。此外，我们还给出了并行多功能机器的多目标排序问题的理论结果。在研究多目标网络优化问题时，我们考虑了随机网络问题的总可靠性。有两个特点。一是给出了总可靠度有效下界的实用方法和有效解--最大化总可靠度和最小化网络建设费用的双目标优化方法。我们得到了电信网络优化设计的结果，可以应用于网络问题的许多领域。在设施选址分析中，我们研究了竞争问题，并考虑了企业和居民之间的情况，得到了实用的最优解。此外，为了应用优化和建模这两种新方法，我们还研究了模糊微分方程组和模糊优化问题。

In our research we studied multi-objective discrete optimization which include multi-objective scheduling problems, network design problems and multi-objective facility location problems and so on as well as we advanced approximation methods for the optimization. Moreover we studied fuzzy differential equations and fuzzy optimization problems for foundation of the optimization by applying the methods of nonlinear functional analysis. In analyzing multi-objective scheduling problems not only we introduced a new model of scheduling problems with fuzziness and adaptability but also we schemed an algorithm for non-dominated solutions and some algorithms based on the beam-search method by developing calculation of a new lower bound. Numerical experiment illustrates utility of our algorithms to multi-objective flow shop problems. Moreover we gave theoretical results on multi-objective scheduling problems concerning parallel and multi-functional machines. In studying multi-objective network optimization problems we considered the total reliability of stochastic network problems. There are two characteristics. One is to give a utilized method for effective lower bounds of the total reliability and a fruitful solution-method of two-objective optimization with maximizing the total reliability and minimizing costs of construction of networks. We got results on optimal design of tele-communication networks, which can be applicable in many fields of network problems. In facility location analysis we investigated competitive problems and obtained practical optimal solutions with considering situations between firms and residents. Furthermore in order to apply optimization and modeling as new methods we studied fuzzy differential equations and fuzzy optimization problems.