Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics

DOI10.1287/MNSC.34.3.266MaRDI QIDQ3779988zbMATH OpenOpenAlexWikidataFDO

Authors George S. Lueker, Alexander H. G. Rinnooy Kan, E. G. jun. Coffman

Publication date 1988

Published in Management Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/mnsc.34.3.266

zbMATH Keywords

average-case performance of heuristicsmakespan schedulingone-dimensional bin packingpackingsequencing

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Deterministic scheduling theory in operations research (90B35) Integer programming (90C10)

Recommendations

• scientific article; zbMATH DE number 903456
• Probabilistic Analysis of Bin Packing Heuristics
• scientific article; zbMATH DE number 52589
• scientific article; zbMATH DE number 176070
• Asymptotic properties of stochastic greedy bin-packing
• Probabilistic behaviour of optimal bin-packing solutions
• scientific article; zbMATH DE number 3943557

Cited in

(20)

• A probabilistic analysis of the next fit decreasing bin packing heuristic
• A note on the average-case behavior of a simple differencing method for partitioning
• Expected performance of the shelf heuristic for 2-dimensional packing
• Average-case performance analysis of an approximation algorithm for maximum subset sum using recurrence relations
• Packing problems
• Packings in two dimensions: Asymptotic average-case analysis of algorithms
• Average performance of greedy heuristics for the integer knapsack problem.
• The modified differencing method for the set partitioning problem with cardinality constraints
• A note on posterior tight worst-case bounds for longest processing time schedules
• FFD bin packing for item sizes with uniform distributions on \([0,\frac12]\).
• Probabilistic Analysis of Bin Packing Heuristics
• Minimum Spillage Sequencing
• scientific article; zbMATH DE number 4079153 (Why is no real title available?)
• scientific article; zbMATH DE number 176070 (Why is no real title available?)
• Average-case analysis of cutting and packing in two dimensions
• Performance of the LPT algorithm in multiprocessor scheduling
• Update on the asymptotic optimality of LPT
• An update on the asymptotic optimality of the longest processing time heuristic
• An analysis of the LPT algorithm for the max-min and the min-ratio partition problems
• Lower bounds and heuristic algorithms for the k_i-partitioning problem

This page was built for publication: Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics

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