Pushpa Publishing House

Journal Menu

Content

Volume 17 (2018)

Volume 16 (2016)

Volume 15 (2015)

Volume 14 (2015)

Volume 13 (2014)

Volume 12 (2014)

Volume 11 (2013)

Volume 10 (2013)

Volume 9 (2012)

Volume 8 (2012)

Volume 7 (2011)

Volume 6 (2011)

Volume 5 (2010)

Volume 4 (2010)

	Volume 4, Issue 2 Pg 93 - 184 (May 2010)
	Volume 4, Issue 1 Pg 1 - 92 (February 2010)

Volume 3 (2009)

Volume 2 (2008)

Volume 1 (2007)

Advances in Computer Science and Engineering

Advances in Computer Science and Engineering
Volume 4, Issue 2, Pages 173 - 184 (May 2010)

A DISCUSSION ON THE PERFORMANCE OF LIST SCHEDULING JOBS IN A MULTIPLE MACHINES ENVIRONMENT
Cheng-Hsien Hsu and Jiann-Fu Lin

Abstract:
This paper discusses the worst performance ratio of list scheduling jobs in a multiple machines environment. It is known that the complexity of finding an optimal schedule for such a problem is NP-hard. In 2004, Remmy applied List scheduling algorithm to on-line schedule independent jobs in a multiple machines environment, and analyzed the worst performance ratio of the List scheduling (LS) algorithm as 2. However, the analysis of the performance ratio of the LS algorithm is incorrect. In this paper, we first point out the error in Remmy’s analysis and give a counterexample to validate it. To further manifest the incorrectness of the worst performance ratio derived by Remmy, we also provide three recent studies on the worst performance ratio of the LS algorithm for the same problem. Hence, we state that the worst performance ratio of the LS algorithm for on-line scheduling independent non-preemptable jobs to a multiple machines environment should fall between 2 and 3. We also discuss the problem of list scheduling jobs with precedence constraints for the same environment and show the worst performance ratio.

Keywords and phrases: List scheduling algorithm, precedence constraints, performance ratio, multiple machines environment.

Number of Downloads: 281 | Number of Views: 853