오픈숍 일정계획 문제의 다항시간 알고리즘

이상운(Sang-Un Lee) 한국정보기술학회 2014 한국정보기술학회논문지 Vol.12 No.4

This paper proposes a polynomial time algorithm designed to obtain near-optimal solution to NP-complete open shop scheduling problem. The open shop scheduling problem is a scheduling problem where given m machines, n jobs, and m×n processing time, job orders and input sequence are determined in such a way that the processing time is minimized. The algorithm proposed in this paper commences simultaneous execution of all jobs while that of those with the maximum processing time shall be a priority, after which remaining jobs are executed in an order. This paper also improves on the makespan minimizing solution by switching job location on a critical path when certain criteria are met. When applied to 6 data, the proposed algorithm has executed optimization process on two of them in order to derive the optimal solutions.

그룹 고장 데이터의 소프트웨어 신뢰성 예측에 관한 신경막 모델

이상운(Sang Un Lee),박영목(Yeong Mok Park),박수진(Soo Jin Park),박재홍(Jae Heung Park) 한국정보처리학회 2000 정보처리학회논문지 Vol.7 No.12

Many software projects collect grouped failure data (failures in some failure interval or in variable time interval) rather than individual failure times or failure count data during the testing or operational phase. This paper presents the neural network (NN) modeling that is able to predict cumulative failures in the variable future time for grouped failure data. A NN''s predictive ability can be affected by what it learns and in its learning sequence. Eleven training regimes that represents the input-output of NN are considered. The best training regimes are selected based on the next-step average relative prediction error (AE) and normalized AE (NAE). The suggested NN models are compared with other well-known NN models and statistical software reliability growth models (SRGMs) in order to evaluate performance. Experimental results show that the NN model with variable time interval information is necessary in order to predict cumulative failures in the variable future time interval.

PCB 부품배치기계의 조립시간 최소화에 관한 중량급 부품 우선 배치 알고리즘

이상운(Sang-Un Lee) 韓國컴퓨터情報學會 2016 韓國컴퓨터情報學會論文誌 Vol.21 No.3

This paper deals with the PCB assembly time minimization problem that the PAP (pick-and-placement) machine pickup the K-weighted group of N-components, loading, and place into the PCB placement location. This problem considers the rotational turret velocity according to component weight group and moving velocity of distance in two component placement locations in PCB. This paper suggest heavy-weight component group first pick-and-place strategy that the feeder sequence fit to the placement location Hamiltonean cycle sequence. This algorithm applies the quadratic assignment problem (QAP) that considers feeder sequence and location sequence, and the linear assignment problem (LAP) that considers only feeder sequence. The proposed algorithm shorten the assembly time than iATMA for QAP, and same result as iATMA that shorten the assembly time than ATMA.

최소 경유 2층 인쇄회로기판 배선도의 3-색 알고리즘

이상운(Sang-Un Lee) 韓國컴퓨터情報學會 2016 韓國컴퓨터情報學會論文誌 Vol.21 No.3

The printed circuit board (PCB) can be used only 2 layers of front and back. Therefore, the wiring line segments are located in 2 layers without crossing each other. In this case, the line segment can be appear in both layers and this line segment is to resolve the crossing problem go through the via. The via minimization problem (VMP) has minimum number of via in layout design problem. The VMP is classified by NP-complete because of the polynomial time algorithm to solve the optimal solution has been unknown yet. This paper suggests polynomial time algorithm that can be solve the optimal solution of VMP. This algorithm transforms n-line segments into vertices, and p-crossing into edges of a graph. Then this graph is partitioned into 3-coloring sets of each vertex in each set independent each other. For 3-coloring sets C〈SUB〉i〈/SUB〉,(i=1,2,3) , the C〈SUB〉1〈/SUB〉 is assigned to front F,C〈SUB〉2〈/SUB〉 is back , and C〈SUB〉3〈/SUB〉 is B-F and connected with via. For the various experimental data, though this algorithm can be require O(np) polynomial time, we obtain the optimal solution for all of data.

대칭 램지 수의 실험적 증명

이상운(Sang-Un Lee) 한국컴퓨터정보학회 2015 韓國컴퓨터情報學會論文誌 Vol.20 No.3

본 논문은 램지 수에 대해 해결하지 못한 43 ≤ R(5,5) ≤ 49와 102 ≤ R(6,6) ≤ 165의 문제를 해결하였다. Kn 완전 그래프의 램지 수 R(s,t)는 임의의 정점 ν의 n-1개 부속 간선수가 (n-1)/2=R과 (n-1)/2=B의 2가지색으로 정확히 양분된다. 따라서 임의의 정점 ν로부터 거리 개념을 적용하여 {KL, ν}의 (n-1)/2=R, {ν, KR}의 (n-1)/2=B색이 되도록 Kn=KL+ν+KR분할 그래프를 형성하였다. 이로부터 KL이 Ks-1의 R색을 형성하면 Ks를 얻을 수 있다. KR이 Kt-1의 B색을 형성하면 Kt를 얻는다. KL과 KR의 최대 거리는 짝수와 모든 정점의 부속 간선 수는 동일하다는 필요충분조건을 만족시키는 R (s,t)=Kn을 구하였다. 결국, R(5,5)=43과 R(6,6)=91 을 증명하였다. This paper offers solutions to unresolved 43 ≤ R(5,5) ≤ 49 and 102 ≤ R(6,6) ≤ 165 problems of Ramsey’s number. The Ramsey’s number R(s,t) of a complete graph Kn dictates that n-1 number of incidental edges of a arbitrary vertex ν is dichotomized into two colors: (n-1)/2=R and (n-1)/2=B. Therefore, if one introduces the concept of distance to the vertex ν, one may construct a partite graph Kn=KL+ν+KR, to satisfy (n-1)/2=R of {KL, ν} and (n-1)/2=B of {ν, KR}. Subsequently, given that KL forms the color R of Ks-1, Ks is attainable. Likewise, given that KR forms the color B of Kt-1, Kt is obtained. By following the above-mentioned steps, R(s,t)=Kn was obtained, satisfying necessary and sufficient conditions where, for KL and KR, the maximum distance should be even and incidental edges of all vertices should be equal are satisfied. This paper accordingly proves R(5,5)=43 and R(6,6)=91.

한정된 응급시설의 최적위치 문제

이상운(Sang-Un Lee) 한국컴퓨터정보학회 2013 韓國컴퓨터情報學會論文誌 Vol.18 No.10

본 논문은 여러 구역으로 분할된 도시에서 응급환자가 발생하였을 때 이에 대처하기 위한 최대 허용 도착시간 T를 충족시키면서, 응급시설 수 p를 한정시켰을 때 최대한의 주민수를 커버할 수 있는 응급시설의 최적 위치를 결정하는 알고리즘을 제안하였다. 이 문제는 일반적으로 두 구역 간 소요시간이 최대허용 도착시간이내이면 1로, 그렇지 않으면 0으로 하는 정수계획법으로 변환시키고, 선형계획법 도구를 활용하여 해를 구한다. 본 논문은 p=1인 경우 최대로 커버하는 노드로 결정하며, p≥2인 경우 최대한으로 커버할 수 있는 노드 상위 5개를 p₁기준으로 포함-배제 원칙을 적용하여 p₁이 커버하는 영역을 삭제하였을 때 남은 노드들 중에서 최대로 커버하는 노드를 p₂로, p₁,p₂ 커버 영역을 삭제시 최대로 커버할 수 있는 노드를 p₃로 결정하였다. 이들 5개 기준 노드 집합 들 중에서 최대로 커버하는 노드 집합을 최적의 응급시설 위치로 결정하였다. 제안된 알고리즘을 12-노드 망, 21-노드 망과 Swain의 55-노드 망에 적용한 결과 최적해를 쉽고 빠르며, 정확하게 결정할 수 있었다. This paper proposes an EMS algorithm designed to determine the optimal locations for Emergency Medical Service centers that both satisfy the maximum ambulance response time T in case of emergency and cover the largest possible number of residents given a limited number of emergency medical services p in a city divided into different zones. This methodology generally applies integer programming whereby cases are categorized into 1 if the distance between two zones is within the response time and 0 if not and subsequently employs linear programming to obtain the optimal solution. In this paper, where p=1, the algorithm determines a node with maximum coverage. In cases where p≥2, the algorithm selects top 5 nodes with maximum coverage. Based on inclusion-exclusion method, this selection entails repeatedly selecting a node with the maximum coverage when nodes with lower numbers are deleted. Among these 5 selected nodes, the algorithm selects a single node set with the greatest coverage and thereby as the optimal EMS location. The proposed algorithm has proven to accurately and expeditiously obtain the optimal solutions for 12-node network, 21-node network, and Swain's 55-node network.

위성 간 링크된 다중통신위성 일정계획 문제의 다항시간 알고리즘

이상운(Sang-Un Lee) 한국정보기술학회 2015 한국정보기술학회논문지 Vol.13 No.8

This paper deals with the time slot assignment problem (TSAP) that multi-satellite with intersatellite links (ISL) switches to traffic between 2n ground stations using on-board switching modes in SS/TDMA system. For this problem, there is only used to the linear programming (LP) or heuristic methods because there has been unknown the polynomial time algorithm to solve the optimal solution thus this problem has been classified as NP-hard. This paper suggests the algorithm with O(n)² time complexity to solve the optimal solution for this problem. Firstly, the proposed algorithm transforms the2n × 2n traffic matrix D into normalized D(ND) with all the rows and columns have the lower bound (LB) that is a maximum sum of traffic of rows or columns. Nextly, we select the maximum traffic of row and column in ISL first from ND matrix, then we select the other maximum traffic in nonoverlapping rows and columns. We decide the k th switch mode and the duration from the minimum traffic in the selected traffics. The proposed algorithm can be get the optimal solution for experimental data.

외판원 문제의 다항시간 알고리즘

이상운(Sang-Un Lee) 한국컴퓨터정보학회 2013 韓國컴퓨터情報學會論文誌 Vol.18 No.12

본 논문은 NP-완전으로 다항시간 알고리즘이 존재하지 않는 대규모 외판원 문제의 최적 해를 O(n²)의 다항시간으로 구하는 알고리즘을 제안하였다. 대규모 외판원 문제에서 가장 큰 문제는 처리될 데이터가 n×n으로 n이 커질수록 기하급수적으로 증가한다. 본 논문에서는 먼저, 데이터의 양을 약 n/2의 크기로 축소시킨다. 다음으로 임의의 정점에서 시작하여 양방향으로 경로를 탐색하는 방법을 적용하였다. 제안된 알고리즘을 26개의 유럽 도시들을 방문하는 TSP-1과 46개 미국 도시들을 방문하는 TSP-2에 적용한 결과 모두 최적 해를 O(n²) 수행 복잡도로 빠르게 구하는데 성공하였다. 따라서 제안된 알고리즘은 TSP의 일반화된 알고리즘으로 적용할 수 있을 것이다. This paper proposes a O(n²) polynomial time algorithm to obtain optimal solution for Traveling Salesman problem that is a NP-complete because polynomial time algorithm has been not known yet. The biggest problem in a large-scale Traveling Salesman problem is the fact that the amount of data to be processed is n×n, and thus as n increases, the data increases by multifold. Therefore, this paper proposes a methodology by which the data amount is first reduced to approximately n/2. Then, it seeks a bi-directional route at a random point. The proposed algorithm has proved to be successful in obtaining the optimal solutions with O(n²) time complexity when applied to TSP-1 with 26 European cities and TSP-2 with 46 cities of the USA. It could therefore be applied as a generalized algorithm for TSP.

소수 판별법

이상운(Sang-Un Lee),최명복(Myeong-Bok Choi) 한국컴퓨터정보학회 2011 韓國컴퓨터情報學會論文誌 Vol.16 No.8

대표적인 소수판별법으로 밀러-라빈방법이 적용되고 있다. 밀러-라빈판별법은 m=[2, n-1]에서 m을 k개 선택하여 n-1=2^* Generally, Miller-Rabin method has been the most popular primality test. This method arbitrary selects m at k-times from m=[2, n-1] range and (m,n)=1. Miller-Rabin method performs k×r times and reports prime as m^*

선거구 획정 문제의 분할정복 알고리즘

이상운(Sang-Un Lee) 한국컴퓨터정보학회 2015 韓國컴퓨터情報學會論文誌 Vol.20 No.12

This paper suggests heuristic algorithm with polynomial time complexity for rigging elections problem that can be obtain the optimal solution using linear programming. The proposed algorithm transforms the given problem into adjacency graph. Then, we divide vertices V into two set  and D. The set W contains majority distinct and the set D contains minority area. This algorithm applies divide-and-conquer method that the minority area D is include into majority distinct W. While this algorithm using simple rule, that can be obtains the optimal solution equal to linear programing for experimental data. This paper shows polynomial time solution finding rule potential in rigging elections problem.