활주로 배정 문제의 정확피복 알고리즘

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

The optimal solution of minimum delay time for runway assignment problem (RAP) is very difficult problem because the approached aircraft are random time interval in the different runways. Therefore this problem has been applied by various metaheuristic methods. This paper suggests O(n log n) polynomial time heuristic algorithm to obtain the optimal solution for RAP. This algorithm decides the first aircraft with minimum target time in the given runway. Then the runway is assigned with aircraft of minimum delayed times take account of separation time. The remained aircraft can be assigned another runway in the same method. We apply optimization method that the aircraft in a runway with maximum delay time to swap of aircraft in another runway. For the P1-12-3, P2-15-3, and P3-20-5 benchmark data of RAP, this algorithm can be head and shoulders above all the other metaheuristic methods.

단일노선 다중임무 버스기사 일정계획 문제의 삽입 알고리즘

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

This paper suggests O(m) linear time heuristic algorithm to obtain the solution for the bus driver scheduling problem with single-route and multiple duty types (mBDSP). This problem is known as NP-complete problem. The proposed algorithm obtains the initial assignment of n minimum number of drivers from given m schedules satisfies the maximum working time (MWT) constraint. Nextly, this algorithm gets the optimal solution using the insert the trip schedule that is over the any dutys sign-off time to possible crews starting schedule at next duty. Although this algorithm is a heuristic linear time algorithm with O(m) time complexity rules, this algorithm is better result than Tabu search method as a kind of metaheuristic methods. To conclude, this paper shows the BDSP is not NP-complete problem but Polynomial time (P)-problem with searching rules.

LSAP의 해 개선 방법을 적용한 LBAP 알고리즘

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

In this paper, we propose a simple linear bottleneck assignment problems (LBAP) algorithm to find the optimal solution. Generally, the LBAP has been solved by threshold or augmenting path algorithm. The primary characteristic of proposed algorithm is derived the optimal solution of LBAP from linear sum assignment problem (LSAP). Firstly, we obtains the solution for LSAP from the selected minimum cost of rows and moves the duplicated costs in row to unselected row with minimum increasing cost in direct and indirect paths. Then, we obtain the optimal solution of LBAP according to the maximum cost of LSAP can be move to less cost. For the 29 balanced and 7 unbalanced problem, this algorithm finds optimal solution as simple.

최소 차수 정점에 인접한 최대 차수 정점 선택 방법을 적용한 정점 최소 지배집합 알고리즘

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

This paper proposes a polynomial time algorithm to Dominating Set problem, which thus far has been known to be NP-complete. From a given graph G(V, E), the proposed algorithm carries out two simple steps: selecting the maximum degree vertex v among all the vertices adjacent to the minimum degree vertex u; and assigning this to the Dominating Set D In this paper, both the suggested algorithm and Greedy algorithm - which is known to solve set cover problem - have been applied to 11 various vertex dominating set problems. Whereas Greedy algorithm has failed to find the optimal solution for 3 of these problems, the suggested algorithm has yielded the optimal solution for all the cases. This thus proves that the vertex dominating set problem could be P-problem rather than NP-complete.

k-opt를 적용한 차수 제약 최소신장트리 알고리즘

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

방향 가중 그래프의 차수제약 최소신장트리 (degree-constrained minimum spanning tree, d-MST) 문제는 정확한 해를 구하는 다항시간 알고리즘이 존재하지 않아 NP-완전 문제로 알려져 왔다. 따라서 휴리스틱한 근사 알고리즘을 적용하여 최적 해를 구하고 있다. 본 논문은 차수와 사이클을 검증하는 Kruskal 알고리즘으로 d-MST의 초기 해를 구하고, d-MST의 초기 해에 대해 k-opt를 수행하여 최적 해를 구하는 다항시간 알고리즘을 제안하였다. 제안된 알고리즘을 4개의 그래프에 적용한 결과 2-MST까지 최적 해를 구할 수 있었다. The degree-constrained minimum spanning tree (d-MST) problem is considered NP-complete for no exact solution-yielding polynomial algorithm has been proposed to. One thus has to resort to an heuristic approximate algorithm to obtain an optimal solution to this problem. This paper therefore presents a polynomial time algorithm which obtains an intial solution to the d-MST with the help of Kruskal’s algorithm and performs k-opt on the initial solution obtained so as to derive the final optimal solution. When tested on 4 graphs, the algorithm has successfully obtained the optimal solutions.

공항 도착-출발 시스템의 가용량 할당문제에 관한 알고리즘

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

The delay aircraft minimization problem in airport arrivals/departures is a significant issue for determinant of airport competitiveness. This problem can be solved only mathematical optimization method. This paper suggests heuristic algorithm for this problem that has a rule to find the solution. The proposed algorithm selects the minimum delays capacity in various airport capacities for number of arrivals/departures aircraft in i<SUP>th</SUP> time interval (15 minutes). In details, we apply three strategies: minimum arrival delays, minimum departure delays, minimum balance delays. The proposed algorithm can be get the minimum delay optimal solution same as the result of previous various algorithms about distinct algorithm apply to four actual experimental data.

불완전 비용 리스트를 가진 대규모 수송문제의 배정-교환 알고리즘

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

본 논문은 불완전 비용 리스트를 가진 대규모 운송 문제의 최적 해를 O(mn) 수행 복잡도로 구하는 배정-교환 알고리즘을 제안한다. 완전 비용 리스트를 가진 운송 문제의 해는 일반적으로 TSM을 적용한다. 그러나 대규모 운송문제에 대해 TSM을 적용하는데 문제가 있으며, 특히 불완전 비용 리스트를 가진 경우에는 TSM으로 풀기에는 더욱 더 어려움이 가중된다. 따라서, 실무분야 전문가들은 상용화된 선형계획법 패키지를 단순히 활용한다. 제안된 알고리즘은 첫 번째로, 운송비용 오름차순으로 운송량을 배정하는 전략을 수행하였다. 이 결과 공급 여유량을 가진 지역으로 부터 요구량을 충족시키지 못하는 지역에 배정량을 조정하였다. 두 번째로, 2-opt와 1-opt의 교환 최적화 전략을 수행하여 최적 해를 구하였다. 제안된 방법을 31×15 불완전 비용 행렬 문제에 적용한 결과, 배정-교환 방법이 상용 선형계획법 패키지인 LINGO의 해를 보다 개선하는 효과를 보였다. This paper suggests assignment-swap algorithm with time complexity O(mn) to obtain the optimal solution for large-scale of transportation problem (TP) with incomplete cost lists. Generally, the TP with complete cost lists can be solved with TSM (Transportation Simplex Method). But, we can"t be solved for large-scale of TP with TSM. Especially. It is hard to solve for large-scale TP with incomplete cost lists using TSM. Therefore, experts simply using commercial linear programming package. Firstly, the proposed algorithm applies assignment strategy of transportation quantity to ascending order of transportation cost. Then, we reassign from surplus of supply to shortage of demand. Secondly, we perform the 2-opt and 1-opt swap optimization to obtain the optimal solution. Upon application to 31×15 incomplete cost matrix problem, the proposed assignment-swap algorithm more improves the solution than LINGO of commercial linear programming.

지배집합 알고리즘

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

본 논문은 아직까지 정확한 해를 다항시간으로 구하는 알고리즘이 존재하지 않아 NP-완전 문제로 알려진 지배집합 (DS) 문제의 정확한 해를 선형시간으로 구하는 알고리즘을 제안하였다. 제안된 알고리즘은 그래프의 간선이 존재하지 않을 때까지 최소차수 Δ(G)를 가진 정점 u의 인접정점들 중 최대차수 Δ(G)를 가진 정점 v를 최소 독립지배집합(MIDS)의 원소로 포함시키고 v의 부속 간선을 삭제하는 방법을 반복적으로 수행하여 구하였다. MIDS로부터 최소 지배집합 (MDS)으로 변환시키고, MDS로부터 최소연결 DS (MCDS)로 변환시키는 방법으로 DS 관련 모든 문제의 정확한 해를 구할 수 있었다. 제안된 알고리즘을 10개의 다양한 그래프에 적용한 결과 정확한 해를 선형 시간복잡도 O(n)으로 구하는데 성공하였다. 결국, 제안된 지배집합 알고리즘은 지배집합 문제가 P-문제임을 증명하였다. This paper proposes a linear-time algorithm that has been designed to obtain an accurate solution for Dominating Set (DS) problem, which is known to be NP-complete due to the deficiency of polynomial-time algorithms that successfully derive an accurate solution to it. The proposed algorithm does so by repeatedly assigning vertex v with maximum degree Δ(G)among vertices adjacent to the vertex v with minimum degree Δ(G) to Minimum Independent DS (MIDS) as its element and removing all the incident edges until no edges remain in the graph. This algorithm finally transforms MIDS into Minimum DS (MDS) and again into Minimum Connected DS (MCDS) so as to obtain the accurate solution to all DS-related problems. When applied to ten different graphs, it has successfully obtained accurate solutions with linear time complexity O(n). It has therefore proven that Dominating Set problem is rather a P-problem.

외판원 문제의 확장된 k-opt 알고리즘

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

본 논문은 지금까지 해결하지 못한 NP-Hard 문제들 중의 하나인 외판원 문제를 해결할 수 있는 알고리즘을 제안한다. 제안된 알고리즘은 간선교환 방법을 적용한 발견적 알고리즘이다. 초기해를 구하는 전형적인 방법은 첫 번째 노드부터 가장 인접한 노드를 방문하여 외판원의 경로를 결정하는 방법이다. 본 논문에서는 각 노드의 최소 간선을 선택하여 선택된 간선들 중 최소값을 가진 노드부터 출발하는 Min-Min 방법과 최대값을 가진 노드부터 출발하는 Min-Max 방법을 적용하고 두 방법 중 최소 경로길이를 가진 방법을 초기해로 결정하였다. 초기해로부터 최적해를 구하는 과정은 기존의 2-간선 교환 방법 (2-opt)을 기본적으로 적용하고, 추가로 확장된 3-opt와 4-opt를 제안하였다. 이와 같은 방법을 7개의 실제 데이터들에 적용한 결과 지금까지 알려진 최적해를 빠르고 정확히 구하는데 성공하였다. This paper suggests traveling salesman problem algorithm that have been unsolved problem with NP-Hard. The proposed algorithm is a heuristic with edge-swap method. The classical method finds the initial solution starts with first node and visits to mostly adjacent nodes then decides the traveling path. This paper selects minimum weight edge for each nodes, then perform Min-Min method that start from minimum weight edge among the selected edges and Min-Max method that starts from maximum weight edges among it. Then we decide tie initial solution to minimum path length between Min-Min and Min-Max method. To get the final optimal solution, we apply previous two-opt to initial solution. Also, we suggest extended 3-opt and 4-opt additionally. For the 7 actual experimental data, this algorithm can be get the optimal solutions of state-of-the-art with fast and correct.

소프트웨어 개발기간 추정 모델

이상운(Sang-Un. Lee) 한국정보과학회 2004 정보과학회논문지 : 소프트웨어 및 응용 Vol.31 No.1

소프트웨어 개발 초기에 개발비용, 소요인력과 기간을 추정하는 것은 소프트웨어공학 분야의 중요하면서도 어려운 문제이다. 기존 모델은 개발업체의 생산성 수준을 고려하지 않고 단순히 기능점수와 노력, 노력과 개발기간 관계에 대한 회귀분석을 통해 개발노력과 기간을 추정하는 모델을 제시하였다. 그러나 동일한 규모의 소프트웨어라도 개발업체의 생산성 수준에 따라 다른 노력의 양이 투입되며, 동일한 노력이 투입되더라도 생산성에 따라 개발기간이 달라진다. 생산성 수준을 고려하지 않은 제안된 모델들은 실제 개발될 프로젝트 적용에 제한점을 갖고 있다. 본 논문은 기존 모델의 단점을 보완하기 위해 생산성을 고려하여 개발기간을 추정할 수 있는 모델들을 제안한다. 생산성에 기반하여 다양한 방법으로 개발기간을 추정할 수 있는 모델을 제안하고 모델들의 성능을 비교하였다. 모델 성능 비교 결과 생산성에 기반하여 소프트웨어 규모로부터 개발기간을 추정하는 모델이 단순하면서도 가장 좋은 결과를 얻었다. 본 모델은 사업 초기에 프로젝트 관리자에게 소프트웨어 개발 기간 의사결정 정보를 제공한다. Estimation of software project cost, effort, and duration in the early stage of software development cycle is a difficult and key problem in software engineering. Most of development effort and duration estimation models presented by regression model of simple relation function point vs. effort and effort vs. duration instead of considering developer's productivity. But different project have need for different effort according to developer's productivity if the projects are same software size. Also, different duration takes according to developer's productivity if the projects require the same effort. Therefore, models that take into account of productivity have a limited application in actual development project. This paper presents models that can be estimate the duration according to productivity in order to compensate a shortcoming of the previous models. Propose model that could presume development period by various methods based on productivity and compared models' performance. As a result of performance comparison, an estimating model of development period from software size got simple and most good result. The model gives decision-making information of development duration to project management in the early stage of software life cycle.