Prepared by:

Joseph Malkevitch

Department of Mathematics and Computing

York College (CUNY)

Jamaica, New York 11451

email: malkevitch@york.cuny.edu

Dear Parents,

The "facts" of Mathematics, unlike those of science, do not have to be revised in light of new empirical discoveries. Once mathematics is proven valid, it remains so. This creates a problem for teachers of mathematics at all grade levels since new mathematical ideas are being discovered all the time and never replace what has come before, only augment it. This especially provides challenges for what new mathematics to teach in the lower grades since youngsters, say in the second grade, do not have a lot of prior mathematical knowledge at their disposal. Thus, it is especially nice, when from time to time, it becomes possible to find use for skills traditionally taught in the lower grades on a topic that is at the frontiers of the kinds of problems mathematicians think about. But what is it precisely that mathematicians do?

If you wanted to give a simple definition of what a mathematician does, to accompany the simple definitions that define the work of a carpenter, pharmacist, or doctor, what definition would you offer? Mathematicians are not experts at balancing check books, nor are they better at arithmetic in general than most people. Mathematicians are experts in the science of studying patterns. For example, they study patterns in numbers, patterns in knots, patterns in data (statistics) and patterns in shapes (geometry), to give but a small sample of what mathematicians study.

One recent new domain of the study of patterns by mathematicians are patterns that are of value in the practice of business. Are there general principles that can be put to work to help governments and business carry out their myriad tasks more efficiently? One example of studying patterns to help businesses is the recent work that has been done on scheduling problems. Problems about scheduling belong to the part of mathematics called Operations Research or Management Science. Management Science is mathematics studied in an effort to make the activities of businesses and governments go more smoothly and in a way that minimizes cost or time.

Scheduling is a ubiquitous problem for us all..As a simple example consider scheduling questions at a hospital. Personnel in such varied positions as nurses and people who arrange to take patients for tests must be provided. The operating rooms must be scheduled in an efficient as well as flexible way and there must be a system to administer both traditional x-rays and CAT scans around the clock. There has to be someone on duty in the pharmacy at all times and a systematic program must exist to give each patient his/her medicines accurately and on time.

How can second graders come to see the role mathematics is playing scheduling? What follows begins with a problem that seems to have little to do with scheduling problems and, yet, there is a connection. Furthermore, rather surprisingly, the skills needed involve only some logical reasoning and a knowledge of adding and subtracting numbers!

Bin Packing

Imagine that you have identical bins, say, of size or capacity 10. You also have items of different sizes that are to be packed into these bins . Obviously, unless all the items to be packed have size at most 10 we can not carry out the process. We are given a large collection of such bins but they are expensive, so we would like to carry out the packing of the items into the bins in a way which uses as few bins as possible. This type of problem is known as bin packing .

Can you think of situations which require solving problems of this kind? Examples include making wooden bookcases by making cuts of different lengths from (costly) boards of a fixed length, packing advertisements of different lengths into fixed length station breaks on radio or television, or taking a large number of pieces of music of different time lengths and recording them on tape cassettes or (audio) compact discs which allow for a fixed amount of recording time. In the last example, the capacity of the bins might be cassettes with 60 minutes of recording time and one might have pieces with times (in minutes) of: 12, 16, 23, 31, 25, 27, 9, 11, 15, 7, 52, 48, 25, 43, 26, 4, 4, 5, 5, 7, 7, 34, and 32. What is the minimum number of cassettes needed to record all the music?

How does one solve bin packing problems? One way would be to use trial and error. This involves trying different clusters of items and checking whether or not they fit into the bins. This might be acceptable if one only required the solution of a few problems of this type. However, if one has thousands of such problems to solve, one needs a systematic method of solving them, ideally a method that is suitable for solution on a computer. Such methods of solving problems are known as algorithms. An algorithm for a problem is a step-by-step description of how to solve problems of a particular type that terminates with an answer in a finite amount of time.

What might an algorithm for solving bin packing problems be? The items to be packed are typically given to us in a list. Using this list we would like to develop an algorithm or procedure which systematically tells us how to go about packing the items as given in the list into the bins, rather than trying to pack them using trial and error:

Here are examples of such procedures. When the addition of an item just fills a bin, that bin is closed. It is convenient to think of the bins as having numbers starting at 1. (Since the bins are displayed vertically, as the items are placed in the bins they fill the bins up from bottom to top.)

1. Next fit: Place the next item in the list into the current bin if it fits; if it does not, close the current bin (though it may not be full) and start a new bin.

2. First fit: Place the next item in the list into the lowest numbered bin that it will fit into. If it will not fit into any bin, open a new one for it.

3. Worst fit: Place the next item in the list into that bin which will leave the largest amount of room left over after the item is placed in the bin. (Here is where being able to subtract comes in handy.)

4. Best fit: Place the next item in the list into that bin which will leave the least room left over after the the item is placed in the bin.

Here is an example that will help illustrate the idea:

Pack 8, 5, 7, 6, 2, 4, 1 into bins of capacity 10, using next fit, first fit, worst fit, and best fit. In the diagrams below, space without a number label is empty space in the bin.

Next fit:

bin 1 bin 2 bin 3 bin 4 bin 5

Figure 1

First fit:

Figure 2

Worst fit:

Figrue 3

Best fit:

Figure 4

In this particular example, it is not difficult to see that one can not pack these items in fewer than 4 bins and, thus, we have achieved several different optimal packings. (If one add the values of the items to be packed: 8 + 5 + 7 + 6 + 2 + 4 + 1 one gets 33. Now 33 divided by 10 is 3.3 which means that one can not possibility pack these items into only 3 bins.) In general, there is no guarantee that any of these 4 algorithms will yield an optimal solution. (In fact, it is fun to produce examples which show that for a particular list which one might create, next fit, say, yields an optimal solution, while the other three methods do not. This is the type of "entertainment" that mathematicians enjoy!) It may surprise you to learn that no one knows any procedure (algorithm) for solving bin packing problems that always guarantees a minimum number of bins and that is fast and easy to carry out. (One can always try all the different possibilities, "brute force," to obtain an answer, but this is not practical for even modest sized problems because it would take too long.)

In our discussion of the four procedures above, although next fit requires more bins, it does not require as much memory (human or computer), since it is not necessary to keep track of how much space is left in many bins, since one only examines one bin at a time. This is a "baby" example. Realistic examples might have millions of items to pack into hundreds or thousands of bins, and for such problems the trade off between time and space issues (using memory to keep track of how much room is left in the many partially filled bins) can be significant.

If you experiment with problems similar to this one and with different sized bins and longer lists of items to pack, you will notice a problem that often occurs. Large or medium size items occurring late in a list are hard to pack since there is little room left over in the partially filled bins to accommodate them. This suggests a different approach to solving bin packing problems. First sort the items in the list in decreasing order (i.e. largest items down to smallest items) and then use one of the four algorithms described above, using the newly generated decreasing time list. Sorting numbers by size is something 2nd graders should practice. Bin packing provides a meaningful context. (The sorted list for the problem above is: 8, 7, 6, 5, 4, 2, 1.) This gives rise to four new algorithms: next fit decreasing, first fit decreasing, worst fit decreasing and best fit decreasing. Usually, this approach will use fewer bins (but not always!) but there is a price to pay. One needs to sort what are sometimes very long lists first, which can be time consuming. (Is the trade-off between the extra time to sort worth the fact that often fewer bins will be needed?) Although first fit or best fit decreasing do not always give optimal answers, there work remarkably well on most problems.

I began this discussion with commenting on the role mathematics is playing in scheduling problems. Though some of the many applications of bin packing were mentioned above, what does bin packing have to do with scheduling?

Machine Scheduling Independent Tasks

The problem of scheduling processors to accomplish a collection of tasks is extremely complicated, even in the simple case we look at here, where the processors are all identical. Some of the complications that are involved are that the tasks may have a complex collection of requirements for the order in which they can be done. For example, before one can put up the walls of a house, the foundation must be poured. In some rare cases, however, the tasks are independent of one another, and, thus, can be scheduled in any order whatsoever. (One example is processing jobs at a photocopy shop after the shop has closed for the day, and all jobs are to be finished by the morning.) Suppose we have a collection of independent tasks (each requiring a specific amount of time) which we would like to schedule so that they are completed by a fixed time W. We can think of this problem as a bin packing problem!. The items to be packed are the tasks with their different times to accomplish, and the bins play the role of the processors. The fact that each processor must finish no later than a particular time corresponds to the (fixed) capacity of the bins. The goal is to find the minimum number of bins that will be required, which corresponds in the scheduling context to finding the minimum number of machines necessary to finish all the tasks by the fixed time W (the capacity of the bins.)

Practicing arithmetic

The skills needed to solve bin packing problems are some logical thinking skills, being able to compare sizes of numbers, and skill at basic addition and subtraction. Mathematics educators are beginning to see a pattern of increased interest in mathematics for many students when contexts are provided for doing basic mathematics rather than merely doing long collections of problems without any suggestions of the reason one might ever have to carry out problems of this kind. Bin packing offers a nice "playground" for seeing the applicability of some simple mathematics while at the same time offering the opportunity for practicing basic arithmetic skills.

Practice:

Here is a problem that will give you a chance to check that you and your child understand the 8 different algorithms.

Items to pack:

6,6,5,5,5,4,4,4,4,2,2,2,2,3,3,7,7,5,5,8,8,4,4,5

Bin size: 10

(Partial answers: next fit 17 bins; first fit 14 bins; worst fit 14 bins; first fit decreasing 13 bins.) 13 bins is optimal.

Experiments: (If you have children at home who are in higher grades you might encourage them to read these notes and try out these questions.)

1. Once you have mastered the 8 algorithms involved you can try experiments with other bin sizes. What happens when the bin size is 9? What happens when the bin size is 11? Experiments of these kinds provide interesting practice at arithmetic, estimation (will the number of bins go up or down when the bin size is changed from 10 to 9 or 11, and can you estimate by how much?), and logical thinking.

2. If you double the capacity of the bins will you halve the number of bins necessary?

3. If you halve the capacity of the bins will you double the number of bins necessary? (Can you always carry out the packing in this case?)

4. Can you find an example where next fit requires fewer bins than first fit?

Can you find an example where first fit requires fewer bins than next fit?

5. Can you find an example where first fit requires fewer bins than worst fit?

Can you find an example where worst fit requires fewer bins than first fit?

6. Try making up a few problems of your own and exploring new algorithms of your invention to solve bin packing!

1. Graham, R., Combinatorial scheduling theory. In Lynn Steen (ed.), Mathematics Today, Springer-Verlag, New York, 1978.

2. Graham, R., The combinatorial mathematics of scheduling, Scientific American, March, 1978, pp. 124-132.

3. Malkevitch, J., (et al.), For All Practical Purposes, 4th edition (also earlier editions), W.H. Freeman, New York, 1997, pp. 102-106.

Some of this work was prepared with partial support from the National Science Foundation (Grant Number: DUE 9555401) to the Long Island Consortium for Interconnected Learning (administered by SUNY at Stony Brook, Alan Tucker, Project Director).

Figure 5