TY - GEN
T1 - Competitive design and analysis for machine-minimizing job scheduling problem
AU - Kao, Mong Jen
AU - Chen, Jian Jia
AU - Rutter, Ignaz
AU - Wagner, Dorothea
N1 - Funding Information:
This work was supported in part by National Science Council (NSC), Taiwan, under Grants NSC99-2911-I-002-055-2, NSC98-2221-E-001-007-MY3, and Karlsruhe House of Young Scientists (KHYS), KIT, Germany, under a Grant of Visiting Researcher Scholarship.
PY - 2012
Y1 - 2012
N2 - We explore the machine-minimizing job scheduling problem, which has a rich history in the line of research, under an online setting. We consider systems with arbitrary job arrival times, arbitrary job deadlines, and unit job execution time. For this problem, we present a lower bound 2.09 on the competitive factor of any online algorithms, followed by designing a 5.2-competitive online algorithm. We would also like to point out a false claim made in an existing paper of Shi and Ye regarding a further restricted case of the considered problem. To the best of our knowledge, what we present is the first concrete result concerning online machine-minimizing job scheduling with arbitrary job arrival times and deadlines.
AB - We explore the machine-minimizing job scheduling problem, which has a rich history in the line of research, under an online setting. We consider systems with arbitrary job arrival times, arbitrary job deadlines, and unit job execution time. For this problem, we present a lower bound 2.09 on the competitive factor of any online algorithms, followed by designing a 5.2-competitive online algorithm. We would also like to point out a false claim made in an existing paper of Shi and Ye regarding a further restricted case of the considered problem. To the best of our knowledge, what we present is the first concrete result concerning online machine-minimizing job scheduling with arbitrary job arrival times and deadlines.
UR - http://www.scopus.com/inward/record.url?scp=84871560170&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-35261-4_11
DO - 10.1007/978-3-642-35261-4_11
M3 - Conference contribution
AN - SCOPUS:84871560170
SN - 9783642352607
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 75
EP - 84
BT - Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings
PB - Springer Verlag
T2 - 23rd International Symposium on Algorithms and Computation, ISAAC 2012
Y2 - 19 December 2012 through 21 December 2012
ER -