An augmented Lagrangian-based decentralized coordination algorithm for multi-objective optimization

Abstract

다목적 최적화에서 모든 목표를 동시에 최적화하는 최적해는 존재하지 않는다. 즉, 의사결정자는 허용 가능한 절충을 위해 협상한다. 본 논문은 공통 또는 개별 목표를 달성하기 위해 서로 다른 분야가 협력해야 하는 다분야 최적화 환경과 유사한 block angular 구조를 가지는 다목적 프로그래밍 문제를 다룬다. 이러한 분산형 환경에서는, 지역 전체의 정보를 공유하지 않고, 지역적으로 최적화된 의사결정자의 솔루션을 파레토 최적 솔루션으로 유도하는 분산 코디네이션 알고리즘이 필요하다. 본 연구에서 제안하는 분산 코디네이션 알고리즘은 솔루션을 생성하기 위한 augmented Lagrangian 접근법에 기초하며 두 단계로 구분된다. 첫 번째 단계는 각 단일 목표에 대한 이상적인 해를 결정할 것이고, 두번째 단계는 이상적인 해에서 시작하여 절충해를 찾는 과정이다. 이때 생성된 솔루션 은 하나의 해로 수렴함과 파레토 최적해임을 보장한다. 제안된 분산 알고리즘의 성능을 보여주기 위해 알고리즘을 목적 함수의 성격과 의사결정의 실시간성 여부에 따라 정의된 다수의 도메인에 적용했다. 첫째, 두개의 선형 목적 함수를 가지는 재방문이 있는 흔합흐름공장에서의 정적 생산 계획을 고려한다. 각 제조 단계는 동일한 병렬 기계로 구성되며 어떤 단계에서든 동일 기계 중 하나에서 제품을 처리할 수 있다. 또한 제품은 일부 단계를 여러 번 재방문할 수 있다. 본 연구에서는 박막 트랜지스터와 액정표시장치(TFT-LCD) 산업에서의 생산 계획 문제를 고려하여 두 가지 유형의 에이전트(프로세스 관리자 및 플랜트 코디네이터)가 있는 경우의 협력적 생산계획 문제에 대한 해법으로 제안된 알고리즘을 적용하였다. 고려한 두개의 목적함수는 재공재고(WIP)의 최소화, 지연된 수요의 최소화로기존의 알려진 다른 중앙집중식 방법과 비교하여 무작위로 생성된 문제에 대해 제안된 메커니즘과 비교하였다. 실험 결과, 제안된 분산형 방법은 다른 중앙집중식 방법에 비해 평균 50% 더 우수한 성능을 보였다. 둘째,비선형 다목적 함수를 가지는 제품 플렛폼 설계 문제를 고려한다. 제품 플렛폼설계 환경은 본질적으로 분산되어 있으며 공통된 목표를 달성하기 위해 다수의 의사결정자가 존재한다. 제품 플렛폼 설계에서의 핵심은 비슷한 구성 요소와 제품군 내 개별 제품을 차별화하는 구성 요소를 찾는 것으로 설계 변수, 생산 비용 및 기타 요인과 관련하여 다목적 최적화로 모델링할 수 있다. 분산형 환경에서 부분적인 정보나 정보 프라이버시 문제는 설계의 성능을 저하시킬 수 있지만 분산형 의사결정 구조는 빠른 의사결정을 촉진시킬수 있다.. 본 연구에서는 의사결정에 참여하는 에이전트를 플랫폼 디자이너와 제품 디자이너로 구분한 수학 모델을 제안한다. 제안된 알고리즘의 효율성을 입증하는 두 가지 사례 연구, 즉 General Aviation Aircraft와 Universal Electric Motor 제품군 설계 문제가 고려되었다. 두 경우 모두 분산 코디네이션 알고리즘이 기존의 설계 알고리즘보다 더 좋은 성능을 발휘했다. 마지막으로 앞에서 연구한 생산 계획 문제를 동적 환경인 동적 생산 계획으로 확장하였다. 이 연구에서는 먼저 우리는 레고와 라즈베리파이, NFC tag와 reader로 구성된 사이버 물리 생산 시스템(CPPS)을 설계하고 개발하였다. 이러한 CPSS에서 기계고장과 수요변화등의 다양한 동적인 이벤트가 발생할 때 이벤트에 기반한 생산계획을 수립하기 위한 목적으로 본 연구에서 제안한 알고리즘을 적용하였다. 제안된 분산 코디네이션 알고리즘은 동적 이벤트가 발생할 때마다 생산 시작 전 및 생산 계획구간 전체에 걸쳐 생산 계획을 재최적화하도록 설계하였다. 알고리즘은 기존의 방법처럼 이전 계획을 전면적으로 재최적화하는 것이 아니라 기존의 계획에서 수정하는 방식이므로 이벤트에 대해 즉각적인 반응이 가능하여 변화에 따른 빠른 최적화가 가능하였다. 실험 결과에 따르면, 제안된 분산 코디네이션 알고리즘이 50% 이상 다른 중앙 집중식 계획 알고리즘을 능가한 것으로 나타났다.; In multi-objective optimization, an optimal solution which optimizes all the objectives simultaneously does not exist and therefore the decision-maker(s) involved negotiate for an acceptable tradeoff. This dissertation deals with multi-objective programming problems with block angular structure characterized by constraint functions that are specific to . In this decentralized environment, a mechanism to guide locally-optimized decision-makers’ solution to a Pareto optimal solution without sharing the entire local information is developed. The mechanism is based on augmented Lagrangian approach to generate a solution and is separated into two Phases. The first Phase determines an ideal point for each of the single objectives and Phase II searches for a compromise solution starting from a single ideal point. Furthermore, a proof to guarantee the convergence and Pareto optimality of solutions generated is provided. To show the usefulness of the proposed decentralized algorithm, the algorithm has been applied to a number of domains defined by the nature of the problem functions and evolution of information. First, we consider a linear multi-objective environment, specifically, static production planning in a reentrant hybrid flow shop with serial stages. Each stage comprises of identical parallel machines and products can be processed on any one of these machines at any stage. Also, a product may revisit some stages multiple times. We consider a Thin Film Transistor and Liquid Crystal Display (TFT-LCD) industry production planning problem and apply the proposed algorithm that allows entities to partake in planning decisions while preserving their autonomy to achieve a globally feasible plan. Via experts’ opinion, we identified two types of agents (process managers and plant coordinator) in this environment to facilitate the use of the proposed algorithm. With these agents, problem decomposition and assignment of roles as well as application of the decentralized coordination algorithm are detailed. Also, we provide computational results of the application of the proposed mechanism to randomly generated problems in comparison to other known centralized methods in literature in terms of work-in-progress (WIP), delayed demand and throughput. Experimental results showed that the decentralized method had an average 50% better performance compared to other centralized methods. Secondly, we consider a non-linear multi-objective problem that concerns collaborative product family design. Product family design environment can be inherently decentralized and requires a number of decision-makers to achieve a common goal. The basic problem here is to find components that are similar and those that differentiate the individual products in the family. Issues related to product platform design can be modeled as multi-objective optimization with respect to design variables, production cost and other factors. A common drawback in decentralized environments is information sharing which can reduce the quality of the decision especially under partial information or information privacy restrictions. However, this decentralized structure can be harnessed for faster decision-making. After identifying the agents that participate in the decision-making, i.e., a platform designer and product designers, we develop a math model. This math model allows the use of the decentralized algorithm. Two case studies are considered to demonstrate the efficiency of the proposed algorithm namely, a General Aviation Aircraft and a Universal Electric Motor product family design problem. For both cases, the decentralized algorithm performed better. Finally, we extend the production planning problem studied earlier to a dynamic environment —dynamic production planning. We design and develop a cyber-physical production system (CPPS) which models a reentrant manufacturing system. Consistent with extant literature on CPPS, we develop a somewhat completely automated CPPS and a decentralized coordination mechanism that harnesses the inherent decentralized structure of CPPS. We provide details on the design and technologies used in building the CPPS. In this dynamic decision-making environment, we consider two types of dynamic events: machine break down and demand change. The decentralized algorithm determines a plan prior to start of production and over the course of the production horizon re-optimizes this plan whenever dynamic events occur. Numerical investigation results show that the proposed decentralized coordination algorithm outperforms other centralized planning algorithms on more than 50% of the performance measures considered.