Open Access System for Information Sharing

Login Library

 

Thesis
Cited 0 time in webofscience Cited 0 time in scopus
Metadata Downloads

주문의 통합 처리를 위한 최대 클리크에 웨이트 할당 문제

Title
주문의 통합 처리를 위한 최대 클리크에 웨이트 할당 문제
Authors
곽우람
Date Issued
2013
Publisher
포항공과대학교
Abstract
원자재산업(석유화학산업, 철강산업 등)의 대표적인 생산방식인 배치생산에서는 묶음처리가 가능한 서로 다른 주문들, 즉, 상호 호환이 가능한 주문들이 존재하고, 이 주문들은 일정한 용량을 가지는 하나의 작업 단위로 통합되어 묶음처리될 수 있다. 이때, 배치생산의 효율을 극대화하기 위해서는 어떤 주문들을 선택하여 통합처리 할 것인가에 대한 의사결정이 필요하고, 이러한 의사결정을 다루는 문제를 주문 통합 문제(OCP)라고 한다. OCP는 생산환경에 따라서, 서로 다른 목적을 가지는 두 개의 문제로 나누어 볼 수 있다. 생산능력이 처리해야 할 주문량에 비해 부족한 경우에는 주어진 용량을 꽉 채운 작업 단위를 최대한 편성하는 것이 중요하며, 이렇게 꽉 채운 작업 단위 수를 최대화하는 문제를 최대 선택 주문 통합 문제(MSP)라고 부른다. 반대로, 생산능력이 처리해야 할 주문량에 비해 여유가 있는 경우에는 주어진 주문들을 모두 처리하기 위해 최소한으로 작업 단위를 편성하는 것이 중요하고, 이것을 목적으로 하는 문제를 최소 커버 주문 통합 문제(MCP)라고 한다. 주문들의 호환성 관계는 호환성 그래프로 불리는 그래프를 이용하여 표현될 수 있다. 만약에 주어진 주문들에 대한 호환성 그래프가 특별한 제한이 없는 일반적인 그래프이면, 두 OCP는 NP-hard이고, APX-hard임이 알려져 있다. 따라서 본 논문의 목적은, 호환성 그래프가 실용적 측면에서 또는 이론적 측면에서 중요한 어떤 그래프 클래스로 제한될 때, 두 문제에 대한 최적 알고리즘을 개발하는 것이다. 이때, 우리는 기존의 문제 접근 방법에서 벗어나, 두 OCP에 대한 대안적 정의들을 각각 개발하고, 이 대안적 정의들을 이용하여 각 문제에 접근한다. 최대 선택을 위한 최대 클리크에 웨이트 할당 문제(WAMC-MS)는 MSP의 대안적 정의이다. 우리는 호환성 그래프가 블록 그래프(block graph), 쿼지쓰레스홀드 그래프(quasi-threshold graph), 그리고 인디퍼런스 그래프(indiffer-ence graph)로 제한될 때, WAMC-MS를 푸는 최적 알고리즘들을 각각 개발하였다. 이때, 우리는 호환성 그래프가 n개의 버텍스(vertex)와 m개의 엣지(edge)를 가지는 블록 그래프일 때, WAMC-MS는 O(n log n + m) 시간 안에 최적으로 풀린다는 것을 보이고, 호환성 그래프가 n개의 버텍스를 가지는 쿼지쓰레스홀드 그래프일 때에는 WAMC-MS가 O(n2 log n) 시간 안에 최적으로 풀린다는 것을 보였다. 또한, 우리는 n개의 버텍스를 가지는 인디퍼런스 그래프에 대해서 WAMC-MS가 O(n2) 시간 안에 최적으로 풀릴 수 있다는 것을 증명하였다. 한편, 최소 커버를 위한 최대 클리크에 웨이트 할당 문제(WAMC-MC)는 MCP의 대안적 정의이며, 우리는 WAMC-MC를 이용하여 MCP에 접근하였다. 이때, 우리는 호환성 그래프가 블록 그래프로 제한될 때의 WAMC-MC에 대한 최적 알고리즘을 개발하였고, n개의 버텍스와 m개의 엣지를 가지는 블록 그래프에 대해서 WAMC-MC가 O(n + m) 시간에 풀린다는 것을 증명하였다. 마지막으로, 우리는 호환성 그래프가 인터벌 그래프(interval graph)로 제한될 때의 WAMC-MC에 대한 최적 알고리즘을 개발하였고, 이 알고리즘이 n개의 버텍스를 가지는 인터벌 그래프에 대해 O(n2) 시간 안에 최적해를 찾는다는 것을 증명하였다. 이때, 이 알고리즘의 시간복잡도는, 기존 문헌에서 인터벌 그래프에 대해 MCP를 푸는 최적 알고리즘의 시간복잡도와 같다.
In batch production, which is common in raw-material industries such as in petrochemical and steel industries, whole or parts of multiple customer orders may be consolidated and processed in the same batch if their product specifications are compatible. Then, a problem arises on how to group the orders to form batches to ensure production efficiency, and it is called order consolidation problem (OCP). Depending on the production environment, two versions of the order consolidation exist. The maximum selection OCP (MSP) maximizes the number of batches that are completely filled up to the batch size with respect to the actual products ordered. On the contrary, the minimum cover OCP (MCP) finds the least possible number of batches required to accommodate all customer orders. The compatibility relationship among customer orders is presented by a graph called the compatibility graph. If the compatibility graph is an arbitrary graph, both versions of the OCP are known to be NP-hard and APX-hard. Hence, the main objective of this dissertation is to develop an optimal algorithm to solve each version of the OCP for the case where the compatibility graph is restricted to some special graph classes, which are important both practically and theoretically. Then, we develop and employ an alternative definition of each version of the OCP to approach the problem. The weight allocation to maximal clique for maximum selection (WAMC-MS) is an alternative definition of MSP. We develop an optimal algorithm to solve the WAMC-MS for each case where the compatibility graph is restricted as block, quasi-threshold, and indifference graphs. Then, we show that if the compatibility graph is a block graph with n vertices and m edges, the WAMC-MS can be optimally solved within O(n log n + m) time
when the compatibility graph is a quasi-threshold graph with n vertices, the WAMC-MS can be solved optimally in O(n2 log n) time. We also prove that the WAMC-MS on indifference graphs can be solved optimally within O(n2) time for an n-vertex graph. On the other hand, the weight allocation to maximal clique for minimum cover (WAMC-MC) is an alternative definition of MCP, and we approach MCP using its alternative definition, WAMC-MC. Then, we present an optimal algorithm for the WAMC-MC on block graphs and show that the problem can be solved in O(n + m) time, where n and m are the number of vertices and edges in a block graph, respectively. Lastly, we develop an optimal algorithm for WAMC-MC when the compatibility graph is an interval graph and prove that it finds an optimum solution within O(n2) time for an n-vertex graph. Its time complexity is the same as that of the optimal algorithm of MCP in the literature.
URI
http://postech.dcollection.net/jsp/common/DcLoOrgPer.jsp?sItemId=000001628554
http://oasis.postech.ac.kr/handle/2014.oak/2023
Article Type
Thesis
Files in This Item:
There are no files associated with this item.

qr_code

  • mendeley

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Views & Downloads

Browse