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.