Research ArticleOpen AccessGoogle Scholar indexed
On-Line Scheduling for Jobs with Arbitrary Release Times on Parallel Related Uniform Machines
Department of Mathematics, Hunan First Normal University, Changsha, China
Department of Mathematics, Key Laboratory of High Performance Computing and Stochastic Information Processing, Hunan Normal University, Changsha, China
Department of Computer, Hunan Normal University, Changsha, China
- 1 Department of Mathematics, Hunan First Normal University, Changsha, China
- 2 Department of Mathematics, Key Laboratory of High Performance Computing and Stochastic Information Processing, Hunan Normal University, Changsha, China
- 3 Department of Computer, Hunan Normal University, Changsha, China
Intelligent Information Management·Volume 08 (2016)·Pages 98–102·Published 12 July 2016·DOI10.4236/iim.2016.84008
Copy link · social · email
Abstract
A parallel related uniform machine system consists of m machines with different processing speeds. The speed of any machine is independent on jobs. In this paper, we consider online scheduling for jobs with arbitrary release times on the parallel uniform machine system. The jobs appear over list in terms of order. An order includes the processing size and releasing time of a job. For this model, an algorithm with competitive ratio of 12 is addressed in this paper.
KeywordsOnline SchedulingUniform MachineCompetitive RatioApproximation Algorithm
- Cho, Y. and Sahni, S. (1980) Bounds for List Schedules on Uniform Processors. SIAM Journal on Computing, 9, 91-103. http://dx.doi.org/10.1137/0209007
- Epstein, L., Noga, J., Seiden, S.S., Sgall, J. and Woeginger, G.J. (2001) Randomized On-Line Scheduling on Two Uniform Machines. Journal of Scheduling, 4, 71-92. http://dx.doi.org/10.1002/jos.60
- Cai, S.Y. and Yang, Q.F. (2012) Online Scheduling on Three Uniform Machines. Discrete Applied Mathematics, 160, 291-302. http://dx.doi.org/10.1016/j.dam.2011.10.001
- Aspnes, J., Azar, Y., Fiat, A., Plotkin, S. and Waarts, O. (1997) On-Line Routing of Virtual Circuits with Applications to Load Balancing and Machine Scheduling. Journal of the ACM, 44, 486-504. http://dx.doi.org/10.1145/258128.258201
- Berman, P., Charikar, M. and Karpinski, M. (2000) On-Line Load Balancing for Related Machines. Journal of Algorithms, 35, 108-121. http://dx.doi.org/10.1006/jagm.1999.1070
- Li, R.H. and Shi, L.J. (1998) An On-Line Algorithm for Some Uniform Processor Scheduling. SIAM Journal on Computing, 27, 414-422. http://dx.doi.org/10.1137/S0097539799527969
- Cheng, T.C.E., Ng, C.T. and Kotov, V. (2006) A New Algorithm for Online Uniform-Machine Scheduling to Minimize the Makespan. Information Processing Letters, 99, 102-105. http://dx.doi.org/10.1016/j.ipl.2006.02.012
- Li, R.H., Cheng, X.Y. and Zhou, Y.X. (2014) On-Line Scheduling for Jobs with Non-Decreasing Release Times and Similar Lengths on Parallel Machines. Optimization: A Journal of Mathematical Programming and Operations Research, 63, 867-882. http://dx.doi.org/10.1080/02331934.2014.895902
- Li, R.H. and Huang, H.C. (2004) On-Line Scheduling for Jobs with Arbitrary Release Times. Computing, 73, 79-97. http://dx.doi.org/10.1007/s00607-004-0067-1
- Li, R.H. and Huang, H.C. (2007) Improved Algorithm for a Generalized On-Line Scheduling Problem on Identical Machines. European Journal of Operations Research, 176, 643-652. http://dx.doi.org/10.1016/j.ejor.2005.06.061