선수제약 다기간 선형계획 배낭문제 (The Cardinality Constrained Multi-Period Linear Programming Knapsack Problem)

서지정보

· 발행기관 : 한국산업경영시스템학회
· 수록지 정보 : 한국산업경영시스템학회지 / 38권 / 4호 / 64 ~ 71페이지
· 저자명 : 원중연

초록

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.

영어초록

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.

참고자료

· 없음