ปัญหาการบรรจุแบบแถบ

Q: ตัวแปร

มีการศึกษารูปแบบต่างๆ ของปัญหาการบรรจุแถบหลายรูปแบบ รูปแบบเหล่านี้เกี่ยวข้องกับรูปทรงเรขาคณิตของวัตถุ มิติของปัญหา ความสามารถในการหมุนของสิ่งของ และโครงสร้างของการบรรจุ [ 4 ]

ปัญหาการบรรจุแถบเป็นปัญหาการลดรูปทรงเรขาคณิต 2 มิติ กำหนดให้ชุดของสี่เหลี่ยมผืนผ้าที่เรียงตัวตามแกนและแถบที่มีความกว้างจำกัดและความสูงอนันต์ กำหนดการบรรจุสี่เหลี่ยมผืนผ้าลงในแถบโดยไม่ทับซ้อนกัน โดยลดความสูงให้น้อยที่สุด ปัญหานี้เป็นปัญหาการตัดและการบรรจุ และจัดอยู่ในประเภทปัญหามิติเปิดตาม Wäscher et al. ^{[ 1 ]}

ปัญหานี้เกิดขึ้นในด้านการจัดตารางเวลา ซึ่งเป็นการจำลองงานที่ต้องการใช้หน่วยความจำส่วนต่อเนื่องกันในช่วงเวลาที่กำหนด อีกตัวอย่างหนึ่งคือในด้านการผลิตทางอุตสาหกรรม ที่ต้องตัดชิ้นส่วนสี่เหลี่ยมผืนผ้าออกจากแผ่นวัสดุ (เช่น ผ้าหรือกระดาษ) ที่มีความกว้างคงที่แต่ความยาวไม่จำกัด และต้องการลดปริมาณวัสดุที่สูญเสียให้น้อยที่สุด

ปัญหานี้ได้รับการศึกษาครั้งแรกในปี พ.ศ. 2523 ^{[ 2 ]}เป็นปัญหา NP-hard อย่างมาก และไม่มีอัลกอริทึมการประมาณค่าแบบพหุนามที่มีอัตราส่วนน้อยกว่า $3/2$ เว้นเสียแต่ว่า $P=NP$ อย่างไรก็ตาม อัตราส่วนการประมาณที่ดีที่สุดที่ทำได้จนถึงปัจจุบัน (โดยอัลกอริทึมเวลาพหุนามโดย Harren et al. ^{[ 3 ]} ) คือ $(5/3+\varepsilon )$ ซึ่งก่อให้เกิดคำถามเปิดว่ามีอัลกอริทึมใดที่มีอัตราส่วนการประมาณค่าหรือไม่ $3/2$ .

คำนิยาม

ตัวอย่างเช่น $I=({\คณิตศาสตร์ {I}},W)$ ปัญหาการบรรจุแถบประกอบด้วยแถบที่มีความกว้าง $W=1$ และความสูงที่ไม่มีที่สิ้นสุด รวมทั้งเซตด้วย ${\คณิตศาสตร์ {I}}$ ประกอบด้วยสิ่งของรูปสี่เหลี่ยมผืนผ้า แต่ละชิ้น $i\in {\mathcal {I}}$ มีความกว้าง $w_{i}\in (0,1]\cap \mathbb {Q}$ และความสูง $h_{i}\in (0,1]\cap \mathbb {Q}$ การจัดเรียงสิ่งของเป็นแผนที่ที่แสดงตำแหน่งมุมล่างซ้ายของสิ่งของแต่ละชิ้น $i\in {\mathcal {I}}$ ไปยังตำแหน่ง $(x_{i},y_{i})\in ([0,1-w_{i}]\cap \mathbb {Q} )\times \mathbb {Q} _{\geq 0}$ ภายในแถบ จุดภายในของสิ่งของที่วางไว้ $i\in {\mathcal {I}}$ เป็นคะแนนจากชุด $\mathrm {inn} (i)=\{(x,y)\in \mathbb {Q} \times \mathbb {Q} |x_{i}<x<x_{i}+w_{i},y_{i}<y<y_{i}+h_{i}\}$ สิ่งของสองชิ้น (ที่วางแล้ว) จะทับซ้อนกันหากมีจุดร่วมภายใน ความสูงของการบรรจุจะกำหนดโดย $\max\{y_{i}+h_{i}|i\in {\mathcal {I}}\}$ เป้าหมายคือการหาวิธีจัดเรียงสิ่งของภายในแถบให้ไม่ทับซ้อนกัน ในขณะเดียวกันก็ลดความสูงของการจัดเรียงให้น้อยที่สุด

นิยามนี้ใช้สำหรับอัลกอริธึมเวลาพหุนามทั้งหมด สำหรับอัลกอริธึมเวลาเสมือนพหุนามและ อัลกอริธึม FPTนิยามจะเปลี่ยนแปลงเล็กน้อยเพื่อความง่ายในการเขียน ในกรณีนี้ ขนาดที่ปรากฏทั้งหมดเป็นจำนวนเต็ม โดยเฉพาะอย่างยิ่งความกว้างของแถบจะกำหนดโดยจำนวนเต็มใดๆที่มากกว่า 1 โปรดทราบว่านิยามทั้งสองนี้เทียบเท่ากัน

ตัวแปร

มีการศึกษารูปแบบต่างๆ ของปัญหาการบรรจุแถบหลายรูปแบบ รูปแบบเหล่านี้เกี่ยวข้องกับรูปทรงเรขาคณิตของวัตถุ มิติของปัญหา ความสามารถในการหมุนของสิ่งของ และโครงสร้างของการบรรจุ^{[ 4 ]}

เรขาคณิต:ในรูปแบบมาตรฐานของปัญหานี้ ชุดของรายการที่กำหนดประกอบด้วยสี่เหลี่ยมผืนผ้า ในกรณีย่อยที่มักพิจารณา รายการทั้งหมดจะต้องเป็นสี่เหลี่ยมจัตุรัส รูปแบบนี้ได้รับการพิจารณาแล้วในเอกสารฉบับแรกเกี่ยวกับการบรรจุแถบ^{[ 2 ]} นอกจากนี้ ยังมีการศึกษารูปแบบที่รูปร่างเป็นวงกลมหรือแม้แต่รูปร่างไม่สม่ำเสมอ ในกรณีหลังนี้เรียกว่า การบรรจุแถบที่ ไม่สม่ำเสมอ

มิติ: หากไม่ได้ระบุไว้เป็นอย่างอื่น ปัญหาการจัดเรียงแถบเป็นปัญหา 2 มิติ อย่างไรก็ตาม ปัญหานี้ได้รับการศึกษาในสามมิติหรือมากกว่านั้นด้วย ในกรณีนี้ วัตถุจะเป็นรูปสี่เหลี่ยมผืนผ้าหลายมิติและแถบนั้นจะเปิดปลายในมิติหนึ่งและถูกจำกัดในมิติที่เหลือ

การหมุน:ในปัญหาการบรรจุแบบแถบคลาสสิกนั้น ไม่อนุญาตให้หมุนสิ่งของ อย่างไรก็ตาม มีการศึกษาถึงรูปแบบต่างๆ ที่อนุญาตให้หมุนได้ 90 องศา หรือแม้แต่ในมุมใดๆ ก็ตาม

โครงสร้าง: ในปัญหาการบรรจุแบบแถบโดยทั่วไป โครงสร้างของการบรรจุไม่สำคัญ อย่างไรก็ตาม มีการใช้งานบางอย่างที่มีข้อกำหนดที่ชัดเจนเกี่ยวกับโครงสร้างของการบรรจุ หนึ่งในข้อกำหนดเหล่านั้นคือความสามารถในการตัดสิ่งของออกจากแถบโดยการตัดขอบชนขอบในแนวนอนหรือแนวตั้ง การบรรจุที่อนุญาตให้มีการตัดแบบนี้เรียกว่าการบรรจุแบบกิโยติน

ความแข็ง

ปัญหาการบรรจุแบบแถบ (Strip Packing Problem) ประกอบด้วยปัญหาการบรรจุแบบกล่อง (Bin Packing Problem)เป็นกรณีพิเศษเมื่อสิ่งของทั้งหมดมีความสูงเท่ากันคือ 1 ด้วยเหตุนี้ ปัญหานี้จึงเป็นปัญหา NP-hard อย่างมาก และไม่มีอัลกอริทึมประมาณค่า แบบเวลาพหุนามใด ที่มีอัตราส่วนการประมาณค่าน้อยกว่า $3/2$ เว้นเสียแต่ว่า $P=NP$ นอกจากนี้ เว้นแต่ว่า $P=NP$ ไม่มี อัลกอริทึม เวลาเสมือนพหุนามใดที่มีอัตราส่วนการประมาณค่าที่น้อยกว่า $5/4$ [ ⁵^]ซึ่งสามารถพิสูจน์ได้โดยการลดจาก^{ปัญหา} 3-partition ที่สมบูรณ์แบบ NP อย่างมาก โปรดทราบว่าขอบเขตล่างทั้งสอง $3/2$ และ $5/4$ นอกจากนี้ยังใช้ได้กับกรณีที่อนุญาตให้หมุนรายการได้ 90 องศา ยิ่งไปกว่านั้น Ashok et al. ^{[ 6 ]} ได้พิสูจน์แล้ว ว่าการบรรจุแบบแถบนั้นยากแบบ W[1]เมื่อกำหนดพารามิเตอร์ด้วยความสูงของการบรรจุที่เหมาะสมที่สุด

คุณสมบัติของคำตอบที่เหมาะสมที่สุด

มีขอบเขตล่างที่ไม่สำคัญสองประการสำหรับคำตอบที่เหมาะสมที่สุด ประการแรกคือความสูงของสิ่งของที่ใหญ่ที่สุด กำหนดให้ $h_{\max }(I):=\max\{h(i)|i\in {\mathcal {I}}\}$ ดังนั้นจึงถือได้ว่า

$OPT(I)\geq h_{\max }(I)$ .

ขอบเขตล่างอีกประการหนึ่งกำหนดโดยพื้นที่รวมของสิ่งของ กำหนด $\mathrm {AREA} ({\mathcal {I}}):=\sum _{i\in {\mathcal {I}}}h(i)w(i)$ ดังนั้นจึงถือว่า

$OPT(I)\geq \mathrm {AREA} ({\mathcal {I}})/W$ .

ขอบเขตล่างสองค่าต่อไปนี้คำนึงถึงข้อเท็จจริงที่ว่าสิ่งของบางอย่างไม่สามารถวางติดกันในแถบได้ และสามารถคำนวณได้ใน ${\mathcal {O}}(n\log(n))$ [ ⁷^] สำหรับขอบล่างแรก ให้ถือว่ารายการต่างๆ เรียงลำดับตามความสูงที่ไม่เพิ่มขึ้น^{กำหนด} $k:=\max\{i:\sum _{j=1}^{k}w(j)\leq W\}$ สำหรับแต่ละ $l>k$ กำหนด $i(l)\leq k$ ดัชนีแรกเช่นนั้น $w(l)+\sum _{j=1}^{i(l)}w(j)>W$ ดังนั้นจึงถือได้ว่า

$OPT(I)\geq \max\{h(l)+h(i(l))|l>k\wedge w(l)+\sum _{j=1}^{i(l)}w(j)>W\}$ [ ⁷^]

สำหรับขอบล่างที่สอง ให้แบ่งเซตของรายการออกเป็นสามเซต ให้ $\alpha \in [1,W/2]\cap \mathbb {N}$ และกำหนด ${\mathcal {I}}_{1}(\alpha ):=\{i\in {\mathcal {I}}|w(i)>W-\alpha \}$ , ${\mathcal {I}}_{2}(\alpha ):=\{i\in {\mathcal {I}}|W-\alpha \geq w(i)>W/2\}$ , และ ${\mathcal {I}}_{3}(\alpha ):=\{i\in {\mathcal {I}}|W/2\geq w(i)>\alpha \}$ ดังนั้นจึงถือได้ว่า

$OPT(I)\geq \max _{\alpha \in [1,W/2]\cap \mathbb {N} }{\Bigg \{}\sum _{i\in {\mathcal {I}}_{1}(\alpha )\cup {\mathcal {I}}_{2}(\alpha )}h(i)+\left({\frac {\sum _{i\in {\mathcal {I}}_{3}(\alpha )h(i)w(i)-\sum _{i\in {\mathcal {I}}_{2}(\alpha )}(Ww(i))h(i)}}{W}}\right)_{+}{\Bigg \}}$ [ ⁷^]ที่ $(x)_{+}:=\max\{x,0\}$ สำหรับแต่ละคน $x\in \mathbb {R}$ .

ในทางกลับกัน Steinberg ^{[ 8 ]}ได้แสดงให้เห็นว่าความสูงของโซลูชันที่เหมาะสมที่สุดสามารถถูกจำกัดไว้ด้านบนโดย

$OPT(I)\leq 2\max\{h_{\max }(I),\mathrm {AREA} ({\mathcal {I}})/W\}.$

กล่าวโดยละเอียดกว่านั้น เขาได้แสดงให้เห็นว่า เมื่อกำหนด $W\geq w_{\max }({\mathcal {I}})$ และ $H\geq h_{\max }(I)$ จากนั้นจึงนำสิ่งของเหล่านั้นมา ${\คณิตศาสตร์ {I}}$ สามารถวางไว้ภายในกล่องที่มีความกว้างได้ $W$ และความสูง $H$ ถ้า

$WH\geq 2\mathrm {AREA} ({\mathcal {I}})+(2w_{\max }({\mathcal {I}})-W)_{+}(2h_{\max }(I)-H)_{+}$ , ที่ไหน $(x)_{+}:=\max\{x,0\}$ .

อัลกอริทึมการประมาณค่าในเวลาพหุนาม

เนื่องจากปัญหานี้เป็นปัญหา NP-hard จึงมีการศึกษาอัลกอริทึมประมาณค่า สำหรับปัญหานี้ วิธีการเชิงฮิวริสติก ส่วนใหญ่ มีอัตราส่วนการประมาณค่าระหว่าง $3$ และ $2$ การค้นหาอัลกอริทึมที่มีอัตราส่วนต่ำกว่า $2$ ดูเหมือนจะซับซ้อน และความซับซ้อนของอัลกอริธึมที่เกี่ยวข้องจะเพิ่มขึ้นตามเวลาการทำงานและคำอธิบาย อัตราส่วนการประมาณค่าที่น้อยที่สุดที่ทำได้จนถึงขณะนี้คือ $(5/3+\varepsilon )$ .

ภาพรวมของการประมาณค่าด้วยเวลาพหุนาม
ปี	ชื่อ	การรับประกันโดยประมาณ	แหล่งที่มา
1980	จัดชิดซ้ายจากล่างขึ้นบน (BL)	$3OPT(I)$	เบเกอร์และคณะ^{[ 2 ]}
1980	Next-Fit Decreasing-Height (NFDH)	$2OPT(I)+h_{\max }(I)\leq 3OPT(I)$	คอฟฟ์แมนและคณะ^{[ 9 ]}
	การปรับความสูงแบบ First-Fit Decreasing-Height (FFDH)	$1.7OPT(I)+h_{\max }(I)\leq 2.7OPT(I)$
	สปลิตฟิต (SF)	$1.5OPT(I)+2h_{\max }(I)$
1980		$2OPT(I)+h_{\max }(I)/2\leq 2.5OPT(I)$	สลีเตอร์^{[ 10 ]}
1981	อัลกอริทึมการแบ่ง (SP)	$3OPT(I)$	โกลัน^{[ 11 ]}
1981	อัลกอริทึมแบบผสม	$(4/3)OPT(I)+7{\frac {1}{18}}h_{\max }(I)$	โกลัน^{[ 11 ]}
1981	ขึ้น-ลง (UD)	$(5/4)OPT(I)+6{\frac {7}{8}}h_{\max }(I)$	เบเกอร์และคณะ^{[ 12 ]}
พ.ศ. 2537	การติดตั้งแบบกลับด้าน	$2OPT(I)$	Schiermeyer ^{[ 13 ]}
พ.ศ. 2540		$2OPT(I)$	สไตน์เบิร์ก^{[ 8 ]}
2000		$(1+\varepsilon )OPT(I)+{\mathcal {O}}(1/\varepsilon ^{2})h_{\max }(I)$	เคนยอน, เรมิลา^{[ 14 ]}
2009		$1.9396OPT(I)$	แฮร์เรน, แวน สตี^{[ 15 ]}
2009		$(1+\varepsilon )OPT(I)+h_{\max }(I)$	แจนเซน, โซลิส-โอบา^{[ 16 ]}
2011		$(1+\varepsilon )OPT(I)+{\mathcal {O}}(\log(1/\varepsilon )/\varepsilon )h_{\max }(I)$	Bougeret et al. ^{[ 17 ]}
2012		$(1+\varepsilon )OPT(I)+{\mathcal {O}}(\log(1/\varepsilon )/\varepsilon )h_{\max }(I)$	สวิริเดนโก^{[ 18 ]}
2014		$(5/3+\varepsilon )OPT(I)$	Harren et al. ^{[ 3 ]}

จัดชิดซ้ายจากล่างขึ้นบน (BL)

อัลกอริทึมนี้ได้รับการอธิบายครั้งแรกโดย Baker et al. ^{[ 2 ]}โดยทำงานดังนี้:

อนุญาต $L$ เป็นลำดับของสิ่งของรูปสี่เหลี่ยมผืนผ้า อัลกอริทึมจะวนซ้ำลำดับนั้นตามลำดับที่กำหนด สำหรับสิ่งของแต่ละชิ้นที่พิจารณา $r\in L$ โดยจะค้นหาตำแหน่งล่างสุดที่จะวาง แล้วเลื่อนไปทางซ้ายให้มากที่สุดเท่าที่จะเป็นไปได้ ดังนั้นจึงวางตำแหน่งนั้น $r$ ที่พิกัดล่างสุดซ้ายสุดที่เป็นไปได้ $(x,y)$ ในแถบนั้น

อัลกอริทึมนี้มีคุณสมบัติดังต่อไปนี้:

อัตราส่วนการประมาณค่าของอัลกอริทึมนี้ไม่สามารถจำกัดด้วยค่าคงที่ได้ กล่าวโดยละเอียดกว่านั้น พวกเขาแสดงให้เห็นว่าสำหรับแต่ละ $M>0$ มีรายการอยู่ $L$ ของสิ่งของรูปสี่เหลี่ยมผืนผ้าที่เรียงลำดับตามความกว้างจากน้อยไปมาก ดังนี้ $BL(L)/OPT(L)>M$ , ที่ไหน $BL(L)$ คือความสูงของการบรรจุที่สร้างขึ้นโดยอัลกอริทึม BL และ $OPT(L)$ คือความสูงของวิธีแก้ปัญหาที่เหมาะสมที่สุดสำหรับ $L$ [ ²^]
หากเรียงลำดับสินค้าตามความกว้างที่ลดลงแล้ว $BL(L)/OPT(L)\leq 3$ [ ²^]
ถ้าสิ่งของทั้งหมดเป็นรูปสี่เหลี่ยมจัตุรัสและเรียงลำดับตามความกว้างที่ลดลงแล้ว $BL(L)/OPT(L)\leq 2$ [ ²^]
สำหรับใดๆ $\delta >0$ มีรายการอยู่ $L$ ของสี่เหลี่ยมผืนผ้าที่เรียงลำดับตามความกว้างที่ลดลง โดยที่ $BL(L)/OPT(L)>3-\delta$ [ ²^]
สำหรับใดๆ $\delta >0$ มีรายการอยู่ $L$ ของสี่เหลี่ยมจัตุรัสที่เรียงลำดับตามความกว้างที่ลดลง โดยที่ $BL(L)/OPT(L)>2-\delta$ [ ²^]
สำหรับแต่ละรายการ $\varepsilon \in (0,1]$ มีกรณีหนึ่งที่ประกอบด้วยเฉพาะรูปสี่เหลี่ยมจัตุรัส โดยที่ลำดับของรูปสี่เหลี่ยมจัตุรัสแต่ละแบบ $L$ มีอัตราส่วนของ $BL(L)/OPT(L)>{\frac {12}{11+\varepsilon }}$ กล่าวคือ มีบางกรณีที่ BL ไม่พบค่าที่เหมาะสมที่สุด แม้ว่าจะวนซ้ำลำดับที่เป็นไปได้ทั้งหมดของรายการก็ตาม^{[ 2 ]}ในปี 2024 ขอบเขตล่างนี้ได้รับการปรับปรุงโดย Hougardy และ Zondervan เป็น $BL(L)/OPT(L)>{\frac {4}{3+\varepsilon }}$ [ ¹⁹^]
ในปี 2025 ฮูการ์ดีและซอนเดอร์แวนได้สร้างลำดับของสี่เหลี่ยมผืนผ้า (เรียกว่า ${\mathcal {FQW}}$ (การเรียงลำดับ) โดยที่ $BL(L)/OPT(L)\leq {\frac {13}{6}}$ [ ²⁰^]

Next-fit decreasing-height (NFDH)

ตัวอย่างการประยุกต์ใช้ NFDH และ FFDH กับกรณีเดียวกัน

อัลกอริทึมนี้ได้รับการอธิบายครั้งแรกโดย Coffman et al. ^{[ 9 ]}ในปี 1980 และทำงานดังนี้:

อนุญาต ${\mathcal {I}}$ กำหนดให้เป็นเซตของสิ่งของรูปสี่เหลี่ยมผืนผ้า ก่อนอื่น อัลกอริทึมจะเรียงลำดับสิ่งของตามลำดับความสูงที่ไม่เพิ่มขึ้น จากนั้น เริ่มต้นที่ตำแหน่ง $(0,0)$ อัลกอริทึมจะวางสิ่งของต่างๆ ติดกันในแถบจนกว่าสิ่งของชิ้นถัดไปจะทับซ้อนกับขอบด้านขวาของแถบ เมื่อถึงจุดนี้ อัลกอริทึมจะกำหนดระดับใหม่ที่ด้านบนของสิ่งของที่สูงที่สุดในระดับปัจจุบัน และวางสิ่งของต่างๆ ติดกันในระดับใหม่นี้

อัลกอริทึมนี้มีคุณสมบัติดังต่อไปนี้:

ระยะเวลาการทำงานสามารถจำกัดได้โดย ${\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|))$ และหากสินค้าได้รับการจัดเรียงไว้แล้ว แม้กระทั่งโดย ${\mathcal {O}}(|{\mathcal {I}}|)$ .
สำหรับสินค้าทุกชุด ${\mathcal {I}}$ ซึ่งจะทำให้เกิดการบรรจุที่มีความสูง $NFDH({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }\leq 3OPT({\mathcal {I}})$ , ที่ไหน $h_{\max }$ ความสูงสูงสุดของสิ่งของใน ${\mathcal {I}}$ [ ⁹^]
สำหรับทุกๆ $\varepsilon >0$ มีเซตของสี่เหลี่ยมผืนผ้าอยู่ ${\mathcal {I}}$ โดยที่ $NFDH({\mathcal {I}}|)>(2-\varepsilon )OPT({\mathcal {I}}).$ ^{[ 9 ]}
บรรจุภัณฑ์ที่ได้จะเป็นแบบตัดด้วยเครื่องตัดแบบกิโยติน ซึ่งหมายความว่าสามารถแยกชิ้นส่วนได้โดยการตัดขอบชนขอบในแนวนอนหรือแนวตั้งตามลำดับ

การปรับความสูงแบบลดหลั่นตามความเหมาะสมครั้งแรก (FFDH)

อัลกอริทึมนี้ ซึ่งอธิบายครั้งแรกโดย Coffman et al. ^{[ 9 ]}ในปี 1980 ทำงานคล้ายกับอัลกอริทึม NFDH อย่างไรก็ตาม เมื่อวางรายการถัดไป อัลกอริทึมจะสแกนระดับจากล่างขึ้นบนและวางรายการในระดับแรกที่พอดี ระดับใหม่จะถูกเปิดก็ต่อเมื่อรายการนั้นไม่พอดีกับระดับก่อนหน้าใดๆ เท่านั้น

อัลกอริทึมนี้มีคุณสมบัติดังต่อไปนี้:

ระยะเวลาการทำงานสามารถจำกัดได้โดย ${\mathcal {O}}(|{\mathcal {I}}|^{2})$ เนื่องจากมีอย่างมากที่สุด $|{\mathcal {I}}|$ ระดับต่างๆ
สำหรับสินค้าทุกชุด ${\mathcal {I}}$ มันสร้างการบรรจุที่มีความสูง $FFDH({\mathcal {I}})\leq 1.7OPT({\mathcal {I}})+h_{\max }\leq 2.7OPT({\mathcal {I}})$ , ที่ไหน $h_{\max }$ ความสูงสูงสุดของสิ่งของใน ${\mathcal {I}}$ [ ⁹^]
อนุญาต $m\geq 2$ สำหรับชุดสินค้าใดๆ ก็ตาม ${\mathcal {I}}$ และแถบที่มีความกว้าง $W$ โดยที่ $w(i)\leq W/m$ สำหรับแต่ละคน $i\in {\mathcal {I}}$ โดยถือว่า $FFDH({\mathcal {I}})\leq \left(1+1/m\right)OPT({\mathcal {I}})+h_{\max }$ นอกจากนี้ สำหรับแต่ละ $\varepsilon >0$ มีชุดสิ่งของดังกล่าวอยู่จริง ${\mathcal {I}}$ กับ $FFDH({\mathcal {I}})>\left(1+1/m-\varepsilon \right)OPT({\mathcal {I}})$ [ ⁹^]
หากสิ่งของทั้งหมดใน ${\mathcal {I}}$ เป็นรูปสี่เหลี่ยมจัตุรัส จึงถือว่า $FFDH({\mathcal {I}})\leq (3/2)OPT({\mathcal {I}})+h_{\max }$ นอกจากนี้ สำหรับแต่ละ $\varepsilon >0$ มีเซตของสี่เหลี่ยมจัตุรัสอยู่ ${\mathcal {I}}$ โดยที่ $FFDH({\mathcal {I}})>\left(3/2-\varepsilon \right)OPT({\mathcal {I}})$ [ ⁹^]
บรรจุภัณฑ์ที่ได้จะเป็นแบบตัดด้วยเครื่องตัดแบบกิโยติน ซึ่งหมายความว่าสามารถแยกชิ้นส่วนได้โดยการตัดขอบชนขอบในแนวนอนหรือแนวตั้งตามลำดับ

อัลกอริทึมการแบ่งและปรับให้เหมาะสม (SF)

อัลกอริทึมนี้ได้รับการอธิบายครั้งแรกโดย Coffman et al. ^{[ 9 ]} สำหรับชุดรายการที่กำหนด ${\mathcal {I}}$ และแถบที่มีความกว้าง $W$ วิธีการทำงานมีดังนี้:

กำหนด $m\in \mathbb {N}$ จำนวนเต็มที่มากที่สุดที่ทำให้สี่เหลี่ยมผืนผ้าที่กำหนดมีความกว้าง $W/m$ หรือน้อยกว่านั้น
แบ่ง ${\mathcal {I}}$ แบ่งเป็นสองชุด ${\mathcal {I}}_{wide}$ และ ${\mathcal {I}}_{narrow}$ โดยที่ ${\mathcal {I}}_{wide}$ ประกอบด้วยสิ่งของทั้งหมด $i\in {\mathcal {I}}$ ด้วยความกว้าง $w(i)>W/(m+1)$ ในขณะที่ ${\mathcal {I}}_{narrow}$ ประกอบด้วยสิ่งของทั้งหมดที่มี $w(i)\leq W/(m+1)$ .
คำสั่ง ${\mathcal {I}}_{wide}$ และ ${\mathcal {I}}_{narrow}$ โดยที่ความสูงไม่เพิ่มขึ้น
บรรจุสิ่งของลงใน ${\mathcal {I}}_{wide}$ โดยใช้อัลกอริธึม FFDH
จัดเรียงลำดับชั้น/ชั้นวางที่สร้างโดย FFDH ใหม่ โดยให้ชั้นวางทั้งหมดที่มีความกว้างรวมมากกว่า $W(m+1)/(m+2)$ อยู่ด้านล่างของส่วนที่แคบกว่า
ซึ่งทำให้ได้พื้นที่สี่เหลี่ยมผืนผ้า $R$ ของกับ $W/(m+2)$ ถัดจากชั้นวางที่แคบกว่า ซึ่งไม่มีสิ่งของใดๆ วางอยู่
ใช้ขั้นตอนวิธี FFDH ในการจัดเรียงสิ่งของลงในกล่อง ${\mathcal {I}}_{narrow}$ โดยใช้พื้นที่ $R$ เช่นกัน.

อัลกอริทึมนี้มีคุณสมบัติดังต่อไปนี้:

สำหรับสินค้าทุกชุด ${\mathcal {I}}$ และสิ่งที่เกี่ยวข้อง $m$ โดยถือว่า $SF({\mathcal {I}})\leq (m+2)/(m+1)OPT({\mathcal {I}})+2h_{\max }$ [ ⁹^{] โปรด}^ทราบว่าสำหรับ $m=1$ โดยถือว่า $SF({\mathcal {I}})\leq (3/2)OPT({\mathcal {I}})+2h_{\max }$
สำหรับแต่ละรายการ $\varepsilon >0$ มีชุดสิ่งของอยู่ ${\mathcal {I}}$ โดยที่ $SF({\mathcal {I}})>\left((m+2)/(m+1)-\varepsilon \right)OPT({\mathcal {I}})$ [ ⁹^]

อัลกอริทึมของสลีเตอร์

สำหรับชุดรายการที่กำหนด ${\mathcal {I}}$ และแถบที่มีความกว้าง $W$ วิธีการทำงานมีดังนี้:

ค้นหารายการทั้งหมดที่มีความกว้างมากกว่า $W/2$ แล้ววางซ้อนกันไว้ที่ด้านล่างของแถบ (ในลำดับแบบสุ่ม) เรียกความสูงรวมของสิ่งของเหล่านี้ว่า... $h_{0}$ สิ่งของอื่นๆ ทั้งหมดจะถูกวางไว้ด้านบน $h_{0}$ .
จัดเรียงสิ่งของที่เหลือทั้งหมดตามลำดับความสูงจากน้อยไปมาก สิ่งของจะถูกจัดวางตามลำดับนี้
พิจารณาเส้นแนวนอนที่ $h_{0}$ เปรียบเสมือนชั้นวางของ โดยอัลกอริทึมจะวางสิ่งของลงบนชั้นวางนี้เรียงลำดับจากสูงไปต่ำ จนกว่าจะไม่มีสิ่งของเหลืออยู่ หรือจนกว่าจะวางสิ่งของชิ้นต่อไปไม่ได้
ลากเส้นแนวตั้งที่ $W/2$ ซึ่งจะตัดแถบนั้นออกเป็นสองส่วนเท่าๆ กัน
อนุญาต $h_{l}$ เป็นจุดที่สูงที่สุดที่ถูกปกคลุมด้วยสิ่งของใดๆ ในครึ่งซีกซ้าย และ $h_{r}$ จุดที่สอดคล้องกันบนครึ่งขวา ลากเส้นตรงแนวนอนสองเส้นที่มีความยาวเท่ากัน $W/2$ ที่ $h_{l}$ และ $h_{r}$ ลากเส้นแบ่งครึ่งซ้ายและขวาของแถบ เส้นทั้งสองนี้จะสร้างชั้นวางใหม่ ซึ่งอัลกอริทึมจะวางสิ่งของลงไป ดังเช่นในขั้นตอนที่ 3 เลือกครึ่งที่มีชั้นวางต่ำกว่า และวางสิ่งของลงบนชั้นวางนั้นจนกว่าจะไม่มีสิ่งของอื่นวางได้อีก ทำซ้ำขั้นตอนนี้จนกว่าจะไม่มีสิ่งของเหลืออยู่

อัลกอริทึมนี้มีคุณสมบัติดังต่อไปนี้:

ระยะเวลาการทำงานสามารถจำกัดได้โดย ${\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|))$ และหากสินค้าได้รับการจัดเรียงไว้แล้ว แม้กระทั่งโดย ${\mathcal {O}}(|{\mathcal {I}}|)$ .
สำหรับสินค้าทุกชุด ${\mathcal {I}}$ มันสร้างการบรรจุที่มีความสูง $A({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }/2\leq 2.5OPT({\mathcal {I}})$ , ที่ไหน $h_{\max }$ ความสูงสูงสุดของสิ่งของใน ${\mathcal {I}}$ [ ¹⁰^]

อัลกอริทึมการแบ่ง (SP)

อัลกอริทึมนี้เป็นส่วนขยายของแนวทางของ Sleator และได้รับการอธิบายครั้งแรกโดย Golan ^{[ 11 ]} โดยจะวางรายการตามลำดับความกว้างที่ไม่เพิ่มขึ้น แนวคิดหลักคือการแบ่งแถบออกเป็นแถบย่อยในขณะที่วางรายการบางรายการ เมื่อใดก็ตามที่เป็นไปได้ อัลกอริทึมจะวางรายการปัจจุบัน $i$ วางเคียงข้างกับสิ่งของที่วางไว้แล้ว $j$ ในกรณีนี้ ระบบจะแบ่งแถบย่อยที่เกี่ยวข้องออกเป็นสองส่วน ส่วนหนึ่งประกอบด้วยรายการแรก $j$ และอีกอันหนึ่งบรรจุสิ่งของปัจจุบัน $i$ หากเป็นไปไม่ได้ ระบบจะวางตำแหน่งใหม่ $i$ วางทับบนสิ่งของที่วางไว้แล้ว และไม่แบ่งแถบย่อยออก

อัลกอริทึมนี้สร้างเซตเอสของแถบย่อย สำหรับแต่ละแถบย่อยs ∈ Sเราทราบว่ามันคือมุมล่างซ้ายs.xpositionและs.ypositionความกว้างของมันs.widthเส้นแนวนอนที่ขนานกับขอบบนและขอบล่างของสิ่งของที่วางไว้ชิ้นสุดท้ายภายในแถบย่อยนี้s.upperและs.ล่างรวมถึงความกว้างของมันด้วยs.itemWidth.

ฟังก์ชัน Split Algorithm (SP) รับอินพุตเป็นรายการต่างๆ ฉันความกว้างของแถบวผลลัพธ์: การบรรจุสิ่งของ เรียงลำดับ I ตามลำดับความกว้างจากน้อยไปมาก; กำหนดรายการว่าง S ของแถบย่อย; กำหนดแถบย่อยใหม่ s โดยกำหนดค่า s.xposition = 0, s.yposition = 0, s.width = W, s.lower = 0, s.upper = 0, s.itemWidth = W; เพิ่ม s ลงใน S; ในขณะที่ I ยังไม่ว่างเปล่าให้เรียกใช้ i := I.pop(); เพื่อลบรายการที่กว้างที่สุดออกจาก I กำหนดลิสต์ใหม่ S_2 ซึ่งประกอบด้วยซับสตริปทั้งหมดที่มีความกว้าง s - ความกว้างของรายการ s ≥ ความกว้างของรายการ i; S_2 ประกอบด้วยแถบย่อยทั้งหมดที่ i พอดีกับสิ่งของที่วางไว้แล้วหากS_2ว่างเปล่าในกรณีนี้ ให้วางสิ่งของนั้นทับสิ่งของอื่น ค้นหาแถบย่อย s ใน S ที่มีค่า s.upper น้อยที่สุดนั่นคือแถบย่อยที่บรรจุสิ่งของน้อยที่สุด วาง i ที่ตำแหน่ง (s.xposition, s.upper); อัปเดต s: s.lower := s.upper; s.upper := s.upper+i.height; s.itemWidth := i.width; ในกรณี นี้ให้วางสิ่งของนั้นไว้ข้างๆ อีกสิ่งของหนึ่งในระดับเดียวกัน แล้วแบ่งแถบย่อยที่เกี่ยวข้อง ณ ตำแหน่งนั้น หาค่า s ∈ S_2 ที่มีค่า s.lower น้อยที่สุด วาง i ที่ตำแหน่ง (s.xposition + s.itemWidth, s.lower); ลบ s ออกจาก S; กำหนดแถบย่อยใหม่สองแถบคือ s1 และ s2 ด้วย s1.xposition = s.xposition, s1.yposition = s.upper, s1.width = s.itemWidth, s1.lower = s.upper, s1.upper = s.upper, s1.itemWidth = s.itemWidth; s2.xposition = s.xposition + s.itemWidth, s2.yposition = s.lower, s2.width = s.width - s.itemWidth, s2.lower = s.lower, s2.upper = s.lower + i.height, s2.itemWidth = i.width; S.add(s1,s2); ฟังก์ชันส่งกลับ สิ้นสุด

อัลกอริทึมนี้มีคุณสมบัติดังต่อไปนี้:

ระยะเวลาการทำงานสามารถจำกัดได้โดย ${\mathcal {O}}(|{\mathcal {I}}|^{2})$ เนื่องจากจำนวนแถบย่อยมีขอบเขตจำกัด $|{\mathcal {I}}|$ .
สำหรับชุดสินค้าใดๆ ก็ตาม ${\mathcal {I}}$ มันถือว่า $SP({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }\leq 3OPT({\mathcal {I}})$ [ ¹¹^]
สำหรับใดๆ $\varepsilon >0$ มีชุดสิ่งของอยู่ชุดหนึ่ง ${\mathcal {I}}$ โดยที่ $SP({\mathcal {I}})>(3-\varepsilon )OPT({\mathcal {I}})$ [ ¹¹^]
สำหรับใดๆ $\varepsilon >0$ และ $C>0$ มีชุดสิ่งของอยู่ชุดหนึ่ง ${\mathcal {I}}$ โดยที่ $SP({\mathcal {I}})>(2-\varepsilon )OPT({\mathcal {I}})+C$ [ ¹¹^]

การติดตั้งแบบย้อนกลับ (RF)

อัลกอริทึมนี้ได้รับการอธิบายครั้งแรกโดย Schiermeyer ^{[ 13 ]} คำอธิบายของอัลกอริทึมนี้ต้องการสัญลักษณ์เพิ่มเติมบางอย่าง สำหรับรายการที่วางไว้ $i\in {\mathcal {I}}$ โดยมุมล่างซ้ายของมันถูกระบุด้วย $(a_{i},c_{i})$ และมุมบนขวาโดย $(b_{i},d_{i})$ .

เมื่อกำหนดชุดสิ่งของแล้ว ${\mathcal {I}}$ และแถบความกว้าง $W$ วิธีการทำงานมีดังนี้:

เรียงซ้อนสี่เหลี่ยมผืนผ้าทั้งหมดที่มีความกว้างมากกว่า $W/2$ เรียงซ้อนกัน (ในลำดับแบบสุ่ม) ที่ด้านล่างของแถบ กำหนดให้เป็น $H_{0}$ ความสูงของกองนี้ สิ่งของอื่นๆ จะถูกบรรจุไว้ด้านบน $H_{0}$ .
จัดเรียงสิ่งของที่เหลือตามลำดับความสูงจากน้อยไปมาก และพิจารณาสิ่งของตามลำดับนี้ในขั้นตอนต่อไป ให้ $h_{\max }$ ให้มีความสูงเท่ากับสิ่งของที่สูงที่สุดในบรรดาสิ่งของที่เหลืออยู่เหล่านี้
วางสิ่งของทีละชิ้นเรียงชิดซ้ายบนชั้นวางที่กำหนดไว้ $H_{0}$ จนกว่าจะไม่มีสิ่งของอื่นใดวางบนชั้นนี้ได้ หรือจนกว่าจะไม่มีสิ่งของเหลืออยู่แล้ว เรียกชั้นวางนี้ว่าชั้นแรก
อนุญาต $h_{1}$ ให้ความสูงเท่ากับความสูงของสิ่งของที่ยังไม่ได้แกะกล่องที่สูงที่สุด กำหนดชั้นวางใหม่ที่ $H_{0}+h_{\max }+h_{1}$ อัลกอริทึมจะจัดเรียงสิ่งของลงบนชั้นวางนี้จากขวาไปซ้าย โดยจัดวางให้ชิดขวาจนส่วนบนของสิ่งของสัมผัสกับชั้นวางนี้ เรียกชั้นวางนี้ว่าชั้นวางระดับย้อนกลับที่สอง
จัดวางสิ่งของลงบนชั้นวางทั้งสองชั้นโดยใช้หลักการจัดวางแบบ First-Fit กล่าวคือ วางสิ่งของไว้ที่ชั้นแรกหากพอดี และวางไว้ที่ชั้นที่สองหากไม่พอดี ทำเช่นนี้ต่อไปจนกว่าจะไม่มีสิ่งของเหลือ หรือจนกว่าความกว้างรวมของสิ่งของในชั้นที่สองจะมีขนาดอย่างน้อย $W/2$ .
เลื่อนระดับย้อนกลับที่สองลงมาจนกว่าสิ่งของจากระดับนั้นจะสัมผัสกับสิ่งของจากระดับแรก กำหนด $H_{1}$ เนื่องจากตำแหน่งแนวตั้งใหม่ของชั้นวางที่เลื่อนออกไป $f$ และ $s$ เป็นคู่สิ่งของที่สัมผัสกันที่ถูกต้องที่สุดด้วย $f$ วางไว้ที่ชั้นแรกและ $s$ ในระดับย้อนกลับที่สอง กำหนด $x_{r}:=\max(b_{f},b_{s})$ .
ถ้า $x_{r}<W/2$ $x_{r}<W/2$ แล้ว $s$ $s$ คือสี่เหลี่ยมผืนผ้าชิ้นสุดท้ายที่วางอยู่ในระดับย้อนกลับที่สอง เลื่อนสิ่งของอื่นๆ ทั้งหมดจากระดับนี้ลงไปอีก (ในปริมาณเท่ากันทั้งหมด) จนกว่าชิ้นแรกจะสัมผัสกับสิ่งของจากระดับแรก อีกครั้งที่อัลกอริทึมจะกำหนดคู่สิ่งของที่สัมผัสกันทางด้านขวาสุด $f'$ $f'$ และ $s'$ $s'$ . กำหนด $h_{2}$ $h_{2}$ เนื่องจากชั้นวางถูกเลื่อนลงมาเป็นปริมาณหนึ่ง
1. ถ้า $h_{2}\leq h(s)$ จากนั้นเปลี่ยน $s$ ไปทางซ้ายจนกระทั่งสัมผัสกับสิ่งอื่นหรือขอบของแถบ กำหนดระดับที่สามที่ด้านบนสุดของ $s'$ .
2. ถ้า $h_{2}>h(s)$ จากนั้นเปลี่ยน $s$ กำหนดระดับที่สามที่ด้านบนสุดของ $s'$ . สถานที่ $s$ จัดวางชิดซ้ายในระดับที่สามนี้ โดยให้สัมผัสกับสิ่งของจากระดับแรกทางด้านซ้าย
จัดเรียงสิ่งของต่อไปโดยใช้หลักการจัดวางแบบ First-Fit แต่ละระดับถัดไป (เริ่มจากระดับที่สาม) จะถูกกำหนดโดยเส้นแนวนอนที่ลากผ่านด้านบนของสิ่งของที่ใหญ่ที่สุดในระดับก่อนหน้า โปรดทราบว่าสิ่งของชิ้นแรกที่วางในระดับถัดไปอาจไม่แตะขอบของแถบด้วยด้านซ้าย แต่สิ่งของจากระดับแรกหรือสิ่งของจากระดับถัดไปอาจแตะขอบได้ $s$ .

อัลกอริทึมนี้มีคุณสมบัติดังต่อไปนี้:

ระยะเวลาการทำงานสามารถจำกัดได้โดย ${\mathcal {O}}(|{\mathcal {I}}|^{2})$ เนื่องจากมีอย่างมากที่สุด $|{\mathcal {I}}|$ ระดับต่างๆ
สำหรับสินค้าทุกชุด ${\mathcal {I}}$ มันสร้างการบรรจุที่มีความสูง $RF({\mathcal {I}})\leq 2OPT({\mathcal {I}})$ [ ¹³^]

อัลกอริทึมของสไตน์เบิร์ก (ST)

อัลกอริทึมของสไตน์เบิร์กเป็นอัลกอริทึมแบบเรียกซ้ำ โดยกำหนดชุดของสิ่งของรูปสี่เหลี่ยมผืนผ้ามาให้ ${\mathcal {I}}$ และพื้นที่เป้าหมายรูปสี่เหลี่ยมผืนผ้าที่มีความกว้าง $W$ และความสูง $H$ โดยเสนอหลักเกณฑ์การลดขนาดสี่ข้อ ซึ่งจะจัดวางสิ่งของบางส่วนและเหลือพื้นที่สี่เหลี่ยมผืนผ้าขนาดเล็กกว่าที่มีคุณสมบัติเหมือนเดิมสำหรับสิ่งของที่เหลืออยู่ พิจารณาสัญลักษณ์ต่อไปนี้: กำหนดชุดของสิ่งของ ${\mathcal {I}}$ เราใช้สัญลักษณ์แทนด้วย $h_{\max }({\mathcal {I}})$ ความสูงของสิ่งของที่สูงที่สุดใน ${\mathcal {I}}$ , $w_{\max }({\mathcal {I}})$ ความกว้างของรายการที่ใหญ่ที่สุดที่ปรากฏใน ${\mathcal {I}}$ และโดย $\mathrm {AREA} ({\mathcal {I}}):=\sum _{i\in {\mathcal {I}}}w(i)h(i)$ พื้นที่ทั้งหมดของสิ่งของเหล่านี้ สไตน์เบิร์กแสดงให้เห็นว่าถ้า

$h_{\max }({\mathcal {I}})\leq H$ , $w_{\max }({\mathcal {I}})\leq W$ , และ $\mathrm {AREA} ({\mathcal {I}})\leq W\cdot H-(2h_{\max }({\mathcal {I}})-h)_{+}(2w_{\max }({\mathcal {I}})-W)_{+}$ , ที่ไหน $(a)_{+}:=\max\{0,a\}$ ,

จากนั้นจึงสามารถวางสิ่งของทั้งหมดไว้ภายในพื้นที่เป้าหมายที่มีขนาดที่กำหนดได้ $W\times H$ กฎการลดขนาดแต่ละข้อจะสร้างพื้นที่เป้าหมายที่เล็กลงและชุดย่อยของรายการที่จะต้องจัดวาง เมื่อเงื่อนไขข้างต้นเป็นจริงก่อนเริ่มกระบวนการ ปัญหาย่อยที่สร้างขึ้นก็จะมีคุณสมบัตินี้เช่นกัน

ขั้นตอนที่ 1 : สามารถนำไปใช้ได้หาก $w_{\max }({\mathcal {I}}')\geq W/2$ .

ค้นหาสินค้าทั้งหมด $i\in {\mathcal {I}}$ ด้วยความกว้าง $w(i)\geq W/2$ และนำออกจาก ${\mathcal {I}}$ .
เรียงลำดับตามความกว้างที่ไม่เพิ่มขึ้น และจัดวางไว้ชิดซ้ายที่ด้านล่างของพื้นที่เป้าหมาย $h_{0}$ คือความสูงรวมของพวกเขา
ค้นหาสินค้าทั้งหมด $i\in {\mathcal {I}}$ ด้วยความกว้าง $h(i)>H-h_{0}$ นำออกจาก ${\mathcal {I}}$ และนำไปใส่ไว้ในชุดใหม่ ${\mathcal {I}}_{H}$ .
ถ้า ${\mathcal {I}}_{H}$ หากว่างเปล่า ให้กำหนดพื้นที่เป้าหมายใหม่เป็นพื้นที่ด้านบน $h_{0}$ กล่าวคือ มันมีความสูง $H-h_{0}$ และความกว้าง $W$ แก้ปัญหาที่ประกอบด้วยพื้นที่เป้าหมายใหม่นี้และชุดรายการที่ลดลงโดยใช้วิธีใดวิธีหนึ่งต่อไปนี้
ถ้า ${\mathcal {I}}_{H}$ ถ้าไม่ว่างเปล่า ให้เรียงลำดับตามความสูงที่ไม่เพิ่มขึ้น และวางสิ่งของเรียงชิดขวาทีละชิ้นในมุมบนขวาของพื้นที่เป้าหมาย $w_{0}$ ให้ความกว้างทั้งหมดของรายการเหล่านี้ กำหนดพื้นที่เป้าหมายใหม่ที่มีความกว้าง $W-w_{0}$ และความสูง $H-h_{0}$ ในมุมบนซ้าย แก้ปัญหาที่ประกอบด้วยพื้นที่เป้าหมายใหม่นี้และชุดรายการที่ลดลงโดยใช้วิธีใดวิธีหนึ่ง

ขั้นตอนที่ 2 : สามารถนำไปใช้ได้หากตรงตามเงื่อนไขต่อไปนี้: $w_{\max }({\mathcal {I}})\leq W/2$ , $h_{\max }({\mathcal {I}})\leq H/2$ และมีสิ่งของที่แตกต่างกันสองอย่าง $i,i'\in {\mathcal {I}}$ กับ $w(i)\geq W/4$ , $w(i')\geq W/4$ , $h(i)\geq H/4$ , $h(i')\geq H/4$ และ $2(\mathrm {AREA} ({\mathcal {I}})-w(i)h(i)-w(i')h(i'))\leq (W-\max\{w(i),w(i')\})H$ .

หา $i$ และ $i'$ และนำออกจาก ${\mathcal {I}}$ .
วางแผ่นที่กว้างกว่าไว้ที่มุมล่างซ้ายของพื้นที่เป้าหมาย และวางแผ่นที่แคบกว่าชิดซ้ายไว้ด้านบนของแผ่นแรก
กำหนดพื้นที่เป้าหมายใหม่ทางด้านขวาของทั้งสองรายการนี้ โดยให้มีความกว้างตามที่กำหนด $W-\max\{w(i),w(i')\}$ และความสูง $H$ .
วางสิ่งของที่เหลือลงใน ${\mathcal {I}}$ เข้าสู่พื้นที่เป้าหมายใหม่โดยใช้วิธีใดวิธีหนึ่ง

ขั้นตอนที่ 3 : สามารถนำไปใช้ได้หากตรงตามเงื่อนไขต่อไปนี้: $w_{\max }({\mathcal {I}})\leq W/2$ , $h_{\max }({\mathcal {I}})\leq H/2$ , $|{\mathcal {I}}|>1$ และเมื่อเรียงลำดับรายการตามความกว้างที่ลดลง จะมีดัชนีอยู่ $m$ ดังนั้นเมื่อกำหนด ${\mathcal {I'}}$ ในฐานะคนแรก $m$ สิ่งของที่บรรจุอยู่ภายในนั้น $\mathrm {AREA} ({\mathcal {I}})-WH/4\leq \mathrm {AREA} ({\mathcal {I'}})\leq 3WH/8$ รวมถึง $w(i_{m+1})\leq W/4$

ชุด $W_{1}:=\max {W/2,2\mathrm {AREA} ({\mathcal {I'}})/H}$ .
กำหนดพื้นที่เป้าหมายรูปสี่เหลี่ยมผืนผ้าใหม่สองพื้นที่ โดยพื้นที่หนึ่งอยู่ที่มุมล่างซ้ายของพื้นที่เดิม และมีความสูง $H$ และความกว้าง $W_{1}$ และอีกด้านทางซ้ายที่มีความสูง $H$ และความกว้าง $W-W_{1}$ .
ใช้วิธีการใดวิธีการหนึ่งเพื่อจัดวางสิ่งของเหล่านั้น ${\mathcal {I'}}$ เข้าสู่พื้นที่เป้าหมายใหม่แห่งแรกและรายการต่างๆ ในนั้น ${\mathcal {I}}\setminus {\mathcal {I'}}$ ไปยังอันที่สอง

โปรดทราบว่าขั้นตอนที่ 1 ถึง 3 มีเวอร์ชันสมมาตรเมื่อสลับความสูงและความกว้างของรายการและพื้นที่เป้าหมาย

ขั้นตอนที่ 4 : สามารถนำไปใช้ได้หากตรงตามเงื่อนไขต่อไปนี้: $w_{\max }({\mathcal {I}})\leq W/2$ , $h_{\max }({\mathcal {I}})\leq H/2$ และมีสิ่งของอยู่ชิ้นหนึ่ง $i\in {\mathcal {I}}$ โดยที่ $w(i)h(i)\geq \mathrm {AREA} ({\mathcal {I}})-WH/4$ .

วางสิ่งของ $i$ ในมุมล่างซ้ายของพื้นที่เป้าหมาย แล้วลบออก ${\mathcal {I}}$ .
กำหนดพื้นที่เป้าหมายใหม่ทางด้านขวาของรายการนี้ โดยให้มีความกว้างตามที่กำหนด $W-w(i)$ และความสูง $H$ และนำสิ่งของที่เหลือไปวางไว้ในบริเวณนี้โดยใช้วิธีใดวิธีหนึ่ง

อัลกอริทึมนี้มีคุณสมบัติดังต่อไปนี้:

ระยะเวลาการทำงานสามารถจำกัดได้โดย ${\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|)^{2}/\log(\log(|{\mathcal {I}}|)))$ [ ⁸^]
สำหรับสินค้าทุกชุด ${\mathcal {I}}$ มันสร้างการบรรจุที่มีความสูง $ST({\mathcal {I}})\leq 2OPT({\mathcal {I}})$ [ ⁸^]

อัลกอริทึมการประมาณค่าแบบเวลาพсевโดพหุนาม

เพื่อปรับปรุงขอบเขตล่างของ $3/2$ สำหรับอัลกอริทึมเวลาพหุนาม ได้มีการพิจารณาอัลกอริทึมเวลาพсевдоพหุนามสำหรับปัญหาการบรรจุแถบ เมื่อพิจารณาอัลกอริทึมประเภทนี้ ขนาดของชิ้นส่วนและแถบทั้งหมดจะถูกกำหนดเป็นจำนวนเต็ม นอกจากนี้ ความกว้างของแถบ $W$ อนุญาตให้ปรากฏเป็นพหุนามในเวลาการทำงาน โปรดทราบว่าในกรณีนี้จะไม่ถือว่าเป็นเวลาการทำงานแบบพหุนามอีกต่อไป เนื่องจากความกว้างของแถบต้องการขนาดการเข้ารหัสเท่ากับ $\log(W)$ .

อัลกอริทึมเวลาเสมือนพหุนามที่พัฒนาขึ้นมาส่วนใหญ่ใช้วิธีการเดียวกัน แสดงให้เห็นว่าแต่ละวิธีแก้ปัญหาที่ดีที่สุดสามารถลดรูปและแปลงเป็นวิธีแก้ปัญหาที่มีโครงสร้างจำนวนคงที่ได้ จากนั้นอัลกอริทึมจะวนซ้ำโครงสร้างทั้งหมดเหล่านี้และวางรายการไว้ภายในโดยใช้การเขียนโปรแกรมเชิงเส้นและแบบไดนามิกอัตราส่วนที่ดีที่สุดที่ทำได้จนถึงขณะนี้คือ $(5/4+\varepsilon )OPT(I)$ [ ²¹^]ในขณะที่ไม่มีอัลกอริทึมเวลาพсевдопоминомил ที่มีอัตราส่วนที่ดี^กว่า $5/4$ เว้นเสียแต่ว่า $P=NP$ ^{[ 5 ]}

ภาพรวมของการประมาณค่าเวลาแบบพсевдоพหุนาม
ปี	อัตราส่วนการประมาณค่า	แหล่งที่มา	ความคิดเห็น
2010	$(3/2+\varepsilon )$	Jansen, Thöle ^{[ 22 ]}
2016	$(7/5+\varepsilon )$	Nadiradze, Wiese ^{[ 23 ]}
2016	$(4/3+\varepsilon )$	กัลเวซ, แกรนโดนี, อิงกาลา, ข่าน^{[ 24 ]}	รวมถึงการหมุน 90 องศาด้วย
2017	$(4/3+\varepsilon )$	แจนเซน เรา^{[ 25 ]}
2019	$(5/4+\varepsilon )$	แจนเซน เรา^{[ 21 ]}	รวมถึงสำหรับการหมุน 90 องศาและงานขึ้นรูปต่อเนื่องด้วย

อัลกอริทึมออนไลน์

ในรูปแบบการบรรจุแบบแถบออนไลน์สินค้าจะทยอยมาถึงตามเวลา เมื่อสินค้ามาถึง จะต้องนำไปวางทันที ก่อนที่จะทราบว่ามีสินค้าชิ้นต่อไปมาถึงหรือไม่ มีอัลกอริทึมออนไลน์สองประเภทที่ได้รับการพิจารณา ในรูปแบบแรก ไม่อนุญาตให้เปลี่ยนแปลงการบรรจุเมื่อวางสินค้าไปแล้ว ในรูปแบบที่สอง สามารถบรรจุสินค้าใหม่ได้เมื่อมีสินค้าชิ้นต่อไปมาถึง รูปแบบนี้เรียกว่าแบบจำลองการย้ายตำแหน่ง

คุณภาพของอัลกอริทึมออนไลน์วัดได้จากอัตราส่วนการแข่งขัน (สัมบูรณ์)

$\mathrm {sup} _{I}A(I)/OPT(I)$ ,

ที่ไหน $A(I)$ สอดคล้องกับคำตอบที่สร้างขึ้นโดยอัลกอริธึมออนไลน์และ $OPT(I)$ สอดคล้องกับขนาดของคำตอบที่เหมาะสมที่สุด นอกจากอัตราส่วนการแข่งขันสัมบูรณ์แล้ว ยังมีการศึกษาอัตราส่วนการแข่งขันเชิงอะซิมโทติกของอัลกอริธึมออนไลน์ด้วย ตัวอย่างเช่น $I$ กับ $h_{\max }(I)\leq 1$ มันถูกนิยามว่า

$\lim \mathrm {sup} _{OPT(I)\rightarrow \infty }A(I)/OPT(I)$ .

โปรดทราบว่าอินสแตนซ์ทั้งหมดสามารถปรับขนาดได้ดังนี้ $h_{\max }(I)\leq 1$ .

ภาพรวมของอัลกอริธึมออนไลน์โดยไม่ต้องย้ายข้อมูล
ปี	อัตราส่วนการแข่งขัน	อัตราส่วนการแข่งขันเชิงอะซิมโทติก	แหล่งที่มา
พ.ศ. 2526	6.99	$\approx 1.7$	เบเกอร์และชวาร์ซ^{[ 26 ]}
พ.ศ. 2540		$1.69+\varepsilon$	Csirik และ Woeginger ^{[ 27 ]}
2007	6.6623		ฮูริงค์และเปาโลส^{[ 28 ]}
2009	6.6623		เย่ ฮั่น และจาง^{[ 29 ]}
2007		$1.58889$	ฮัน และคณะ^{[ 30 ]} + เซเดน^{[ 31 ]}

กรอบงานของ Han et al. ^{[ 30 ]}สามารถนำไปใช้ได้ในสภาพแวดล้อมออนไลน์หากอัลกอริทึมการบรรจุถังออนไลน์เป็นของคลาส Super Harmonic ดังนั้น อัลกอริทึมการบรรจุถังออนไลน์ Harmonic++ ของ Seiden ^{[ 31 ]}จึงหมายถึงอัลกอริทึมสำหรับการบรรจุแถบออนไลน์ที่มีอัตราส่วนเชิงเส้นกำกับ 1.58889

ภาพรวมของขีดจำกัดล่างสำหรับอัลกอริธึมออนไลน์โดยไม่ต้องย้ายข้อมูล
ปี	อัตราส่วนการแข่งขัน	อัตราส่วนการแข่งขันเชิงอะซิมโทติก	แหล่งที่มา	ความคิดเห็น
พ.ศ. 2525	$2$		บราวน์ เบเกอร์ และแคทเซฟ^{[ 32 ]}
2006	2.25		โยฮันเนส^{[ 33 ]}	นอกจากนี้ยังใช้ได้กับปัญหาการจัดตารางงานแบบขนานด้วย
2007	2.43		ฮูริงค์และเปาโลส^{[ 34 ]}	นอกจากนี้ยังใช้ได้กับปัญหาการจัดตารางงานแบบขนานด้วย
2009	2.457		เคิร์นและพอลลัส^{[ 35 ]}
2012		$1.5404$	บาโลห์และเบเกซี^{[ 36 ]}	ขอบล่างเนื่องจากปัญหาการบรรจุลงถังที่เป็นพื้นฐาน
2016	2.618		หยู เหมา และเซียว^{[ 37 ]}

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

5

[ 6 ]

7

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

19

20

21

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ 32 ]

[ 33 ]

[ 34 ]

[ 35 ]

[ 36 ]

[ 37 ]

ปัญหาการบรรจุแบบแถบ

คำนิยาม

ตัวแปร

ความแข็ง

คุณสมบัติของคำตอบที่เหมาะสมที่สุด

อัลกอริทึมการประมาณค่าในเวลาพหุนาม

จัดชิดซ้ายจากล่างขึ้นบน (BL)

Next-fit decreasing-height (NFDH)

การปรับความสูงแบบลดหลั่นตามความเหมาะสมครั้งแรก (FFDH)

อัลกอริทึมการแบ่งและปรับให้เหมาะสม (SF)

อัลกอริทึมของสลีเตอร์

อัลกอริทึมการแบ่ง (SP)

การติดตั้งแบบย้อนกลับ (RF)

อัลกอริทึมของสไตน์เบิร์ก (ST)

อัลกอริทึมการประมาณค่าแบบเวลาพсевโดพหุนาม

อัลกอริทึมออนไลน์

ข้อมูลสำคัญจากบทความ