The FFD algorithm for the bin packing problem with kernel items

DOI10.1007/S11766-998-0027-1MaRDI QIDQ1272734zbMATH OpenOpenAlexFDO

Authors Enyu Yao, Guochuan Zhang

Publication date 17 May 1999

Published in Applied Mathematics. Series B (English Edition) (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11766-998-0027-1

zbMATH Keywords

bin packingfirst-fit-decreasingworst case performance ratiosFFD algorithmkernel items

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Recommendations

• The Asymptotic Worst-Case Behavior of the FFD Heuristic for Small Items
• A simple proof of the inequality \(\text{FFD}(L)\leq {11 \over 9} \text{OPT}(L)+1\), \(\forall L\) for the FFD bin-packing algorithm
• The proof of \(\text{FFD}(L)\leq\frac{11}9\text{OPT}(L)+\frac79\)

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 563208 (Why is no real title available?)
• A new proof for the first-fit decreasing bin-packing algorithm
• A new version of on-line variable-sized bin packing
• A simple proof of the inequality \(\text{FFD}(L)\leq {11 \over 9} \text{OPT}(L)+1\), \(\forall L\) for the FFD bin-packing algorithm
• Assembly line balancing as generalized bin packing

Cited in

(3)

• The Asymptotic Worst-Case Behavior of the FFD Heuristic for Small Items
• An algorithm for constructing an admissible solution to the bin packing problem with fuzzy constraints
• Max-min bin packing algorithm and its application in nano-particles filling

This page was built for publication: The FFD algorithm for the bin packing problem with kernel items

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1272734)