Minimum Spillage Sequencing

Craig A. Tovey, Gideon Weiss and James R. Wilson
Additional contact information
Craig A. Tovey: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Gideon Weiss: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332 and Tel Aviv University, Tel Aviv, Israel
James R. Wilson: Pritsker and Associates, West Lafayette, Indiana

Management Science, 1988, vol. 34, issue 3, 306-330

Abstract: The minimum spillage sequencing problem, which arises in real-time satellite signal data processing, requires a set of numbers to be arranged so as to minimize the "overflow" of the partial sums above an upper bound. We subject several heuristics to worst-case analysis, average-case analysis, and computational testing. The results demonstrate that the problem, though NP-hard, can be handled effectively. One of the highlights of the analysis is a tight upper bound on the fraction of overflow when the problem is solved to optimality, together with an O(n log n) "safe" heuristic which never exceeds this bound.

Keywords: integer algorithms; heuristics; programming (search for similar items in EconPapers)
Date: 1988
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.34.3.306 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:34:y:1988:i:3:p:306-330

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().