A Fast Branch-and-Bound Algorithm with an Improved Lower Bound for Solving the Multiprocessor Scheduling Problem

Taiwan, ROC December 17-December 20

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/ICPADS.2002.1183469

Ninth International Conference on Par ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Satoshi Fujita Articles by Masayuki Masukawa Articles by Shigeaki Tagashira

	ASCII Text	x
	Satoshi Fujita, Masayuki Masukawa, Shigeaki Tagashira, "A Fast Branch-and-Bound Algorithm with an Improved Lower Bound for Solving the Multiprocessor Scheduling Problem," Parallel and Distributed Systems, International Conference on, pp. 611, Ninth International Conference on Parallel and Distributed Systems (ICPADS'02), 2002.

	BibTex	x
	@article{ 10.1109/ICPADS.2002.1183469, author = {Satoshi Fujita and Masayuki Masukawa and Shigeaki Tagashira}, title = {A Fast Branch-and-Bound Algorithm with an Improved Lower Bound for Solving the Multiprocessor Scheduling Problem}, journal ={Parallel and Distributed Systems, International Conference on}, volume = {0}, year = {2002}, issn = {1521-9097}, pages = {611}, doi = {http://doi.ieeecomputersociety.org/10.1109/ICPADS.2002.1183469}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Parallel and Distributed Systems, International Conference on TI - A Fast Branch-and-Bound Algorithm with an Improved Lower Bound for Solving the Multiprocessor Scheduling Problem SN - 1521-9097 SP EP A1 - Satoshi Fujita, A1 - Masayuki Masukawa, A1 - Shigeaki Tagashira, PY - 2002 KW - Branch-and-bound algorithm KW - multiprocessor scheduling problem KW - lower bound on the execution time KW - quadratic algorithm VL - 0 JA - Parallel and Distributed Systems, International Conference on ER -

Satoshi Fujita, Hiroshima University

Masayuki Masukawa, Hiroshima University

Shigeaki Tagashira, Hiroshima University

This paper proposes a fast branch-and-bound algorithm for solving the multiprocessor scheduling problem. The key point of our method is the proposal of an efficient quadratic algorithm for calculating the Fernandez and Bussell?s lower bound. In the following, we discuss about the trade-off between the cost for calculating a lower bound and the size of pruned subtrees. Several experiments are conducted to evaluate the goodness of the proposed method.

Index Terms:

Branch-and-bound algorithm, multiprocessor scheduling problem, lower bound on the execution time, quadratic algorithm

Citation:

Satoshi Fujita, Masayuki Masukawa, Shigeaki Tagashira, "A Fast Branch-and-Bound Algorithm with an Improved Lower Bound for Solving the Multiprocessor Scheduling Problem," icpads, pp.611, Ninth International Conference on Parallel and Distributed Systems (ICPADS'02), 2002

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.