ABSTRACT
Let a 1 , … , a n https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_13958.tif"/> be a given collection of items with sizes s ( a i ) > 0, 1 ≤ i ≤ n . https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_13959.tif"/> In mathematical terms, bin packing is a problem of partitioning the set { a i } https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_13960.tif"/> under a sum constraint: Divide { a i } https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_13961.tif"/> into a minimum number of blocks, called bins, such that the sum of the sizes of the items in each bin is at most a given capacity C > 0 https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_13962.tif"/> . To avoid trivialities, it is assumed that all item sizes fall in ( 0, C ] https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_13963.tif"/> . Research into bin packing and its many variants, which began some 45 years ago [1, 2], continues to be driven by a countless variety of applications in the engineering and information sciences. The following examples give an idea of the scope of the applications:
(Stock cutting) Lumber with a fixed cross section comes in a standard board C https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_13964.tif"/> units in length. The items are demands for pieces that must be cut from such boards. The objective is to minimize the number of boards (bins) used for the pieces { a i } https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_13965.tif"/> , or equivalently, to minimize the trim loss or waste (the total board length used minus the sum of the s ( a i ) https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_13966.tif"/> ). It is easy to see that this type of application extends to industries that supply cable, tubing, cord, tape, and so on, from standard lengths.
492(Television programming) Fixed duration time slots are provided between segments of entertainment programs for the use of commercials. The objective is to minimize the number of time slots (bins) that need to be devoted to a given collection of variable length commercials { a i } https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_13967.tif"/> .
(Transportation) The a i https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_13968.tif"/> are items to be loaded onto a collection of identical transports (e.g., trucks, railway cars, airplanes) with given weight and volume limits. The objective is to minimize the number of transports (bins) needed; if only the weight limit is operative then the s ( a i ) https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_13969.tif"/> denote weights, and if only the volume limit is operative then the s ( a i ) https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_13970.tif"/> represent volumes.
(Computer storage allocation) In this application, the items are files to be stored on a set of identical disks with the constraint that each file must be stored entirely on one disk; and the objective is to minimize the number of disks (bins) needed for the set of files.
