Multiple Strip Packing and Scheduling Parallel Jobs in Platforms
We consider two strongly related problems, multiple strip packing and scheduling parallel jobs in platforms. In the first one we are given a list of n rectangles with heights and widths bounded by one and N strips of unit width and infinite height. The objective is to find a non-overlapping orthogonal packing without rotations of all rectangles into the strips minimizing the maximum height used. In the scheduling problem we consider jobs instead of rectangles, i.e. we are allowed to cut the rectangles vertically and we may have target areas of different size, called platforms. A platform $P_\ell$ is a collection of $m_\ell$ processors running at speed $s_\ell$ and the objective is to minimize the makespan, i.e. the latest finishing time of a job.