Bin packing with restricted piece sizes

Coffman et al. have recently shown that a large number of bin-packing problems can be solved in polynomial time if the piece sizes are drawn from the power set of an arbitrary positive integer q (i.e., the piece sizes are drawn from the set {1,q,q²,q³,...}). This article shows that these problems remain NP-hard if the piece sizes are drawn from the power set of an arbitrary positive rational number r. It also shows that the running time of the ∈-approximation scheme recently proposed by Hochbaum and Shmoys for the multiprocessor scheduling problem can be reduced from O((n/∈)exp(1/∈)²) time to O((n/∈)exp((1/∈)log(1/∈))) time.