Multi-Capacity Bin Packing Algorithms with Applications to Job Scheduling Under Multiple Constraints.
1999-05-25
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Multi-Capacity Bin Packing Algorithms with Applications to Job Scheduling Under Multiple Constraints.
Published Date
1999-05-25
Publisher
Type
Report
Abstract
In past massively parallel processing systems, such as the TMC CM-5 and the CRI T3E, the scheduling problem consisted of allocating a single type of resource among the waiting jobs; the processing node. A job was allocated the minimum number of nodes required to meet its largest resource requirement (e.g. memory, CPUs, I/O channels, etc.). Single capacity bin-packing algorithms were applied to solve this problem. Recent systems, such as the SUN E10000 and SGI 02K, are made up of pools of independently allocatable hardware and software resources such as shared memory, large disk farms, distinct I/O channels, and software licenses. In order to make efficient use of all the available system resources, the scheduling algorithm must be able to maintain a job working set which fully utilizes all resources. At the core of this scheduling problem is a d-capacity bin-packing problem where each system resource is represented by a capacity in the bin and the requirements of each waiting job are represented by the d-capacities of an time in the input list. Previous work in d-capacity bin-packing algorithms analyzed extensions of single capacity bin-packing. These extended algorithms are oblivious to the additional capacities, however, and do not scale well with increasing d. We provide new packing algorithms which use the additional capacity information to provide better packing and show how these algorithms might lead to better multi-resource allocation and scheduling solutions.
Keywords
Description
Related to
Replaces
License
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Leinberger, William; Karypis, George; Kumar, Vipin. (1999). Multi-Capacity Bin Packing Algorithms with Applications to Job Scheduling Under Multiple Constraints.. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/215380.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.