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.

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

项目成果

Saito,S., Ishii,H.: "On Systems of Fuzzy Convex Functions"J. Nonlinear and Convex Analysis. (to appaear).

Saito,S., Ishii,H.：“论模糊凸函数系统”J.

Saito,S., Ishii, H.: "On Bundary Value Problems of Fuzzy Differential Equations"Proc. of 2^<nd> Vietnam-Japan Bilateral Symposium on Fuzzy Systems and Applications (VJFUZZY2001). 152-159 (2001)

Saito,S., Ishii, H.：“模糊微分方程的边值问题”Proc。

Osumi, S., Shiode, S.: "Competitive Facility Location Problems Concerning Fuzzy Metric"Management System in 21th Century, Chap. 13 Toho Publ.. 265-283 (2002)

Osumi, S.、Shiode, S.：“关于模糊度量的竞争设施选址问题”21世纪管理系统，第1章。

Saito,S.,Ishii,H.: "On Systems of Fuzzy Convex Functions"J.Nonlinear and Convex Analysis-An International Journal-. (掲載予定).

Saito, S., Ishii, H.：“论模糊凸函数系统”J. 非线性和凸分析 - 国际期刊 -（即将出版）。

Muthusamy,K.,Ishii,H.,Mohri.S.,Masuda,T.: "Beam Search Approach for the Multiobjrctive Flow-shop Scheduling Problem"スケジューリングシンポジウム2000講演論文集. 142-148 (2000)

Muthusamy, K.、Ishii, H.、Mohri.、Masuda, T.：“多目标流水作业调度问题的束搜索方法”调度研讨会 2000 年论文集 142-148 (2000)。