Abstract
The problem of arranging N unit length weights on a line segment of length N, given a target center of gravity on this line segment, is examined under the assumption that the only information we have about the weights is their order, i.e., a 1 ≥ a 2 ≥ ... ≥ a N . Lower bounds on worst case performance of algorithms for this problem are developed, and algorithms (permutations) which come close to achieving these bounds are provided.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
AgnetisAllessandro (1989) No-wait flow shop scheduling with large lot size, Rap. 16.89, Dipartimento di Informatica e Sistemistica, Universita Degli Studi di Roma “La Sapienza”, Rome, Italy.
Wei-Ping Liu and Jeffrey B. Sidney (revised 1994) Ordinal algorithms for parallel machine scheduling, to appear in Operations Research Letters.
Wei-Ping Liu and Jeffrey B. Sidney (1994) Bin packing using semi-ordinal data, to appear in Operations Research Letters.
MenipazEhud (1984) Essentials of Production and Operations Management, Prentice-Hall, Englewood Cliffs, NJ.
Author information
Authors and Affiliations
Additional information
Communicated by N. Zaguia
This work was partially supported under Natural Sciences and Engineering Research Council (NSERC) of Canada research grant number OGP0002507.
Rights and permissions
About this article
Cite this article
Liu, WP., Sidney, J.B. Ordinal algorithms for packing with target center of gravity. Order 13, 17–31 (1996). https://doi.org/10.1007/BF00383965
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF00383965