http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
원중연(Joong-Yeon Won) 대한산업공학회 2014 대한산업공학회지 Vol.40 No.4
The multi-divisional knapsack problem is defined as a binary knapsack problem where each mutually exclusive division has its own capacity. In this paper, we present an extension of the multi-divisional knapsack problem that has generalized multiple-choice constraints. We explore the linear programming relaxation (P) of this extended problem and identify some properties of problem (P). Then, we develop a transformation which converts the problem (P) into an LP knapsack problem and derive the optimal solutions of problem (P) from those of the converted LP knapsack problem. The solution procedures have a worst case computational complexity of order O(n² logn), where n is the total number of variables. We illustrate a numerical example and discuss some variations of problem (P).
일반화된 일반상한제약을 갖는 이차원 선형계획 배낭문제 연구
원중연(Joong Yeon Won) 대한산업공학회 2011 대한산업공학회지 Vol.37 No.3
We study on a generalization of the two dimensional linear programming knapsack problem with the extended GUB constraint, which was presented in paper Won(2001). We identify some new parametric properties of the generalized problem and derive a solution algorithm based on the identified parametric properties. The solution algorithm has a worst case time complexity of order O(n2logn), where n is the total number of variables. We illustrate a numerical example.
원중연(Joong Yeon Won) 한국산업경영시스템학회 2015 한국산업경영시스템학회지 Vol.38 No.4
In this paper, we present a multi-period 0-1 knapsack problem which has the cardinality constraints. Theoretically, the presented problem can be regarded as an extension of the multi-period 0-1 knapsack problem. In the multi-period 0-1 knapsack problem, there are n jobs to be performed during m periods. Each job has the execution time and its completion gives profit. All the n jobs are partitioned into m periods, and the jobs belong to i-th period may be performed not later than in the i-th period, i=1, ⋯, m . The total production time for periods from 1 to i is given by bi for each i=1, ⋯, m, and the objective is to maximize the total profit. In the extended problem, we can select a specified number of jobs from each of periods associated with the corresponding cardinality constraints. As the extended problem is NP-hard, the branch and bound method is preferable to solve it, and therefore it is important to have efficient procedures for solving its linear programming relaxed problem. So we intensively explore the LP relaxed problem and suggest a polynomial time algorithm. We first decompose the LP relaxed problem into m subproblems associated with each cardinality constraints. Then we identify some new properties based on the parametric analysis. Finally by exploiting the special structure of the LP relaxed problem, we develop an efficient algorithm for the LP relaxed problem. The developed algorithm has a worst case computational complexity of order max[O(n2logn), O(mn2)], where m is the number of periods and n is the total number of jobs. We illustrate a numerical example.
일반상한 및 확장된 다중선택 제약을 갖는 연속 예산배정문제
원중연 ( Won Joong-yeon ) 한국경영공학회 2018 한국경영공학회지 Vol.23 No.3
This paper presents a budgeting problem where a specified number of projects from some disjoint classes should be selected such that the total cost of the selected projects does not exceed a given budget. The problem is formulated as a 0-1 mixed integer knapsack problem with GUB (generalized upper bound) and generalized multiple choice constraints. The presented problem is a natural extension of the 0-1 integer knapsack problem with only either GUB constraints or multiple choice constraints. The formulation can be arisen in applications to transportation management, government budgeting, planning, and as relaxations from other combinatorial optimization problems. In this paper, we consider the LP relaxed continuous budgeting problem, which could be used as a bounding strategy in the branch and bound method for the presented 0-1 mixed integer budgeting problem. We explore the special structure of the continuous budgeting problem and then identify several fundamental properties. By exploiting these properties, we develop an efficient solution algorithm for the continuous budgeting problem and analyze the worst case computational complexity of the solution algorithm. We illustrate a numerical example.
허태영(Tae-Young Hur),원중연(Joong-Yeon Won),김현수(Hyun-Soo Kim),한대희(Dae-Hee Han),한우철(Woo-Chul Han) 한국컴퓨터정보학회 2009 韓國컴퓨터情報學會論文誌 Vol.14 No.7
본 논문은 폐가전제품의 재활용을 위한 공동회수모형을 연구한 것이다. 이 모형은 지자체 및 생산자의 폐가전제품 수집소에 회수되어 있는 폐가전제품을 R/C(재활용 센터) 운송하는 거리를 최소화하는 것을 목적으로 한다. 현재 재활용을 위한 폐가전제품 회수물류 활동은 수집소 개별적으로 이루어지고 있어, 과도한 운송거리 및 운송비용의 초래 및 낮은 차량 적재율 등의 비효율적인 면이 존재하고 있다. 본 논문에서는 이러한 비효율적인 점을 개선하기 위해 공동회수모형을 제안하고 이를 정수계획모형과 실제 R/C의 입고자료를 이용하여 그 효과를 분석했다. In this paper, we studied about an consolidated transportation model to transport EOL (end-of-life) electronic household appliances for recycling in South Korea. The objective is to minimize the total traveling distance of the vehicles transporting EOL electronic household appliances collected by local authorities and major manufacturers' distribution centers to assigned R/C(recycling center) in South Korea. Current reverse logistics for recycling EOL electronic household appliances is operated by local authorities and major manufacturers individually, and it is inefficient for the following reasons: excessive traveling distance, transportation cost, low truck capacity utilization, and so on. The presented model is developed to solve this problem. We apply a integer programming to solve this problem and present computational results using actual field data.