APPROXIMATION ALGORITHMS FOR 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 nonoverlapping 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_l is a collection of m_l processors running at speed se and the objective is to minimize the makespan, i.e., the latest finishing time of a job.