Bin Packing and Machine Scheduling
4. Bin packing and machine scheduling
In describing scheduling problems we will sometimes refer to identical or parallel machines. Some machines, in fact, are pretty close to identical (but even for identical machines they may have different "ages" and be in different places in their repair cycles when actually used). However, when one has human processors it's rarely the case that they are truly identical. Carpenters are still not cloned but we will treat human processors with a particular expertise as if they have the same skills. This is an example of a modeling assumption.
How is bin packing connected with machine scheduling? Suppose that we have tasks which take differing times to complete which can be performed in any order on identical machines. Our goal is to determine the minimum number of machines needed to finish the tasks by a fixed time. The fixed desired completion time corresponds to the capacity of the bins, and weights can be thought of as the times to do the tasks. When we find the minimum number of bins needed to pack the weights we are finding the minimum number of machines needed to finish by the desired time!
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance