* 본 문서는 배포용으로 복사 및 편집이 불가합니다.
서지정보
ㆍ발행기관 : 한국산업경영시스템학회
ㆍ수록지정보 : 산업경영시스템학회지 / 38권 / 4호
ㆍ저자명 : 원중연
ㆍ저자명 : 원중연
목차
1. 서 론2. 선수제약 다기간 선형계획 배낭문제
3. 문제의 분해
4. 다기간 제약구조의 특성 및 해법
5. 수치예제
6. 결 론
영어 초록
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(n2log n), O(mn2)], where m is the number of periods and n is the total number of jobs. We illustrate a numerical example.참고 자료
없음"산업경영시스템학회지"의 다른 논문
고령자를 위한 무동력 기립보조의자 개발7페이지
국내 무인항공기의 경로계획 연구14페이지
물류자동화 시스템의 효율적 구축을 위한 컨설팅 방법론 제안 : K기업의 사례를 중심으로10페이지
기업 정보보안 전략 수립을 위한 보안 사고 유형 분류에 관한 연구9페이지
시니어전용 기능성 깔창의 체계적인 개발 및 효과분석9페이지
점진성형에서 형상 정밀도에 영향을 미치는 공정 변수7페이지
제품-서비스 시스템 개발을 위한 객체 지향 설계 프레임워크 개발9페이지
반도체 프로브 공정에서의 2단계 계층적 생산 계획 방법 연구9페이지
이산사건 시뮬레이션 시스템을 활용한 생산성 개선 사례 연구10페이지
열화되는 성능 파라메터를 가지는 시스템의 신뢰성 예측에 관한 연구7페이지