Feature Column from the AMS

Bin Packing

4. Applications of bin packing

So far we have alluded to only a few applications of bin packing, such as packing trucks with weight capacity C. (Realistic versions of truck packing problems typically go beyond issues of one-dimensional bin packing.) However, you can probably think of a variety of situations where identical bins with the same capacity are to be filled with weights. (Alternatively, read next month's column, which will provide more examples.)

However, there is an important connection between bin packing and another very important collection of operations research questions, often referred to as machine scheduling problems. Consider the problem of scheduling identical machines with tasks that are independent of each other, that is, the tasks can be done by the machines in any order. Each of the tasks has a time that is necessary to complete it on one of the machines. More complex machine scheduling problems have to deal with the problem that often some tasks can not be worked on before other tasks are completed. Suppose one wants to know what is the minimum number of machines which are needed to finish a collection of independent tasks by time T with times to complete the tasks of t₁, t₂, t₃, ...., t_n? As you probably realize this question is bin packing with a very minimal disguise (change t to w; T to C)! For example, suppose one has photocopying jobs of varying numbers of pages that have been brought into a photocopy shop. If the shopkeeper wants the automatic work of the machines to enable her to go home within 3 hours of the start of the photocopy tasks, how many machines would have to be available to do the work, and how should the jobs be assigned to the machines?

Next month, in addition to looking at more applications of bin packing problems we will consider variants of the bin packing problem as well as work that has been done to find good approximate solutions.