Bin-packing adjustable rectangles and applications to task scheduling on partitionable parallel computers

The problem of packing adjustable rectangles into a rectangular bin with minimum height is investigated. In this problem, the length and width of each rectangle can be changed, based on certain reshaping rules, before being packed into the bin. The problem is called packing adjustable rectangle (PAR) problem. One application of this problem is scheduling independent tasks on partitionable parallel computers. The paper investigated reshaping rules for reshaping rectangles, which are suitable to the task scheduling problem. Based on these rules, asymptotically optimal algorithms to solve the PAR problem are developed and presented