权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

要素間に先行順位関係をもつシステムの配置問題とメタ戦略

元素之间具有优先关系的系统的放置问题和元策略

基本信息

批准号：
08780410
负责人：
加地太一
金额：
$ 0.58万
依托单位：
Otaru University of Commerce
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1996
资助国家：
日本
起止时间：
1996 至无数据
项目状态：
已结题

项目摘要

本研究の対象として先行順位を持ついくつかの生産プロセスからなるシステムを考え、各プロセスは生産活動のために一定の資源量を必要とするが、1ステーションあたり使用できる資源量は定まっているとする。中間製品の移動には各ステーション間で、ある輸送コストを必要とするが、同一ステーション内の輸送コストは無視できるものとする。このとき、各生産プロセスを輸送コストの総和が最小になるように、先行順位の制限を無視せずに、ステーションごとに利用可能な資源量の範囲内で各ステーションに配置する問題を考える。この問題に対して無閉路有向グラフを先行順位を無視することなく分割するときに生ずるカット・エッジのコストの総和を最小化する問題としてモデル化を行う。さらに、動的計画法を適用し、無閉路有向グラフの構造に並列構造が認められるとき、多項式オーダーの実用時間内で計算可能な有効な厳密解法を提案する。しかし、無閉路有向グラフがランダムな構造を有するとき指数的オーダーとなり実質的に計算が困難となる。そこで、ランダムなグラフにも対応できるよう、昨今、種々の問題で優れた成果を示しているメタヒューリスティック法の採用を試みる。まず、Tabu Search法を用い、本問題に有効な近似解法の構成を示す。ただし、本問題の場合、系列性を保存する多分割問題であり、また、解の成分集合の個数、各成分集合の要素数が不定であり、効果的な近傍構造が構成しにくい。これに対して多重的な頂点移動により解に大きな変化をほどこし、部分的最適化を組入れた複合移動により近似解法の性能を引き出す。さらに、確率的要素を組込んだSimulated Annealing法を構成し、同様な複合移動の考えが効果的であり、Tabu Search法を凌駕することを示した。

This study aims to determine the amount of resources required for production activities in order to maintain the priority of production activities. The intermediate product is moved between different stages, and the transportation within the same stage is ignored. This paper discusses the problem of how to allocate resources within the range of possible resource utilization and how to minimize the cost of transportation and how to limit the cost of transportation in advance. This problem is not closed circuit, it is directed, it is ignored, it is divided, it is generated, it is integrated, it is minimized. In this paper, the dynamic planning method is applied, the structure of the closed-circuit direction-free structure is recognized, and the polynomial calculation is possible in the actual time. It is difficult to calculate the quality of the index without closed-circuit directional structure. For example, if you are interested in the application of the new method, you may find that the new method is suitable for you. This problem is solved by Tabu Search method. The number of component sets of the solution, the number of elements of each component set, and the composition of the adjacent structure of the result are variable. This allows multiple vertex shifts to be incorporated into the approximate solution. In addition, the elements of accuracy are grouped into Simulated Annealing methods, and the results of composite movement are shown in Tabu Search.