Studies on Approximation Algorithm for Multi-objective Discrete Optimization Problems

多目标离散优化问题的逼近算法研究

基本信息

批准号：
10205216
负责人：
ISHII Hiroaki
金额：
$ 5.31万
依托单位：
Osaka University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas (B)
财政年份：
1998
资助国家：
日本
起止时间：
1998 至 2000
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10205216/
关键词：
multi-objective optimization network design problem multi-objective scheduling problem nonlinear functional analysis multi-objective location problem beam search method fuzzy differential equation fuzzy optimzation 多目的スケジューリング多目的配置分枝限定法

项目摘要

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.

在我们的研究中，我们研究了多目标离散优化，其中包括多目标调度问题，网络设计问题和多目标设施位置问题等，以及我们高级近似方法进行优化。此外，我们通过应用非线性功能分析方法研究了模糊的微分方程和模糊优化问题，以基础优化。在分析多目标调度问题时，不仅我们引入了一个新的模型模型和适应性的调度问题模型。数值实验说明了我们算法与多目标流店问题的实用性。此外，我们对有关平行和多功能机器的多目标调度问题给出了理论结果。在研究多目标网络优化问题时，我们考虑了随机网络问题的总可靠性。有两个特征。一种是提供一种利用方法，用于有效的总可靠性的下限，并提供两种目标优化的富有成果的解决方案，以最大程度地利用总可靠性并最大程度地减少网络构建的成本。我们获得了远程通信网络的最佳设计的结果，这可能适用于许多网络问题领域。在设施分析中，我们研究了竞争问题，并通过考虑企业与居民之间的情况获得了实用的最佳解决方案。此外，为了将优化和建模应用于新方法，我们研究了模糊的微分方程和模糊优化问题。