[논문]The Three-Dimensional Bin Packing Problem

Martello, Silvano; Pisinger, David; Vigo, Daniele

doi:10.1287/opre.48.2.256.12386

The Three-Dimensional Bin Packing Problem

Operations research, v.48 no.2, 2000년, pp.256 - 267

Martello, Silvano (DEIS, University of Bologna, Viale Risorgimento 2, Bologna, Italy) , Pisinger, David (DIKU, University of Copenhagen, University Parken 1, Copenhagen, Denmark) , Vigo, Daniele (DEIS, University of Bologna, Viale Risorgimento 2, Bologna, Italy)

Abstract ▼ AI-Helper

The problem addressed in this paper is that of orthogonally packing a given set of rectangular-shaped items into the minimum number of three-dimensional rectangular bins. The problem is strongly NP-hard and extremely difficult to solve in practice. Lower bounds are discussed, and it is proved that the asymptotic worst-case performance ratio of the continuous lower bound is 1/8. An exact algorithm for filling a single bin is developed, leading to the definition of an exact branch-and-bound algorithm for the three-dimensional bin packing problem, which also incorporates original approximation algorithms. Extensive computational results, involving instances with up to 90 items, are presented: It is shown that many instances can be solved to optimality within a reasonable time limit.

참고문헌 (22)

Berkey, J. O., Wang, P. Y.. Two-Dimensional Finite Bin-Packing Algorithms. The journal of the Operational Research Society, vol.38, no.5, 423-429.

상세보기
Bischoff, E.E., Marriott, M.D.. A comparative evaluation of heuristics for container loading. European journal of operational research, vol.44, no.2, 267-276.

상세보기
Chen, C.S., Lee, S.M., Shen, Q.S.. An analytical model for the container loading problem. European journal of operational research, vol.80, no.1, 68-76.

상세보기
Christofides, Nicos, Whitlock, Charles. An Algorithm for Two-Dimensional Cutting Problems. Operations research, vol.25, no.1, 30-44.

상세보기
Chung, F. R. K., Garey, M.R., Johnson, D.S.. On Packing Two-Dimensional Bins. SIAM journal on algebraic and discrete methods, vol.3, no.1, 66-76.

상세보기
Approximation Algorithms for NP-Hard Problems Coffman E. G. 1997
Dell’Amico, Mauro, Martello, Silvano. Optimal Scheduling of Tasks on Identical Parallel Processors. ORSA journal on computing, vol.7, no.2, 191-200.

상세보기
Dyckhoff, H.. A typology of cutting and packing problems. European journal of operational research, vol.44, no.2, 145-159.

상세보기
10.1007/978-3-642-58165-6
Annotated Bibliographies in Combinatorial Optimization Dyckhoff H. 1997
Gehring, H., Menschner, K., Meyer, M.. A computer-based heuristic for packing pooled shipment containers. European journal of operational research, vol.44, no.2, 277-288.

상세보기
George, J.A., Robinson, D.F.. A heuristic for packing boxes into a container. Computers & operations research, vol.7, no.3, 147-156.

상세보기
Hadjiconstantinou, Eleni, Christofides, Nicos. An exact algorithm for general, orthogonal, two-dimensional knapsack problems. European journal of operational research, vol.83, no.1, 39-56.

상세보기
Enumerative Approaches to Combinatorial Optimization-Part 2, volume 11, Annals of Operations Research Ibaraki T. 1987
Labbé, Martine, Laporte, Gilbert, Mercure, Hélène. Capacitated Vehicle Routing on Trees. Operations research, vol.39, no.4, 616-622.

상세보기
Li, Keqin, Cheng, Kam-Hoi. On Three-Dimensional Packing. SIAM journal on computing, vol.19, no.5, 847-867.

상세보기
Knapsack Problems: Algorithms and Computer Implementations Martello S. 1990
Martello, S., Toth, P.. Lower bounds and reduction procedures for the bin packing problem. Discrete applied mathematics, vol.28, no.1, 59-70.

상세보기
Martello, Silvano, Vigo, Daniele. Exact Solution of the Two-Dimensional Finite Bin Packing Problem. Management science, vol.44, no.3, 388-399.

상세보기
Proceedings NOAS'97 Pisinger D. 1997
J. Inform. Process. Cybernet. Scheithauer G. 263 27 1991
Ricerca Operativa Scheithauer G. 3 83 1997

원문 URL 링크

DOI : 10.1287/opre.48.2.256.12386
ProQuest Central : 저널
JSTOR : 저널> 권호 > 논문
ProQuest Academic Research Library : 저널
ProQuest ABI/INFORM : 저널
INFORMS : 저널
EBSCOHost-Military & Government Collection : 저널
EBSCOHost-Business Source Premier : 저널
EBSCOHost-Business Source Elite : 저널
EBSCOHost-Business Source Corporate : 저널

*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.

이 논문과 함께 이용한 콘텐츠

[논문] 등가정하중법을 이용한 텔레비전 포장재의 구조최적설계

저작권 관리 안내

내보내기 메뉴

내보내기 구분

파일저장
인쇄
메일전송

구성항목

기본정보
상세정보

관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관

저장형식

Text(ASCII format)
Excel format
RefWorks Direct Export
RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley

메일정보

받는사람 (필수): @
보내는사람 (선택): @
제목
내용: KISTI 검색결과 이메일 서비스

안내

총 건의 자료가 검색되었습니다.

다운받으실 자료의 인덱스를 입력하세요. (1-10,000)

검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다.

데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요)

다운로드 파일은 UTF-8 형태로 저장됩니다.
파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오.

Text(ASCII format)
Excel format

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

AI-Helper ※ AI-Helper는 을 사용합니다.

AI-Helper

안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

연합인증

The Three-Dimensional Bin Packing Problem

Abstract ▼ AI-Helper

참고문헌 (22)

이 논문을 인용한 문헌

관련 콘텐츠

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format