Research ArticleOpen AccessGoogle Scholar indexed
Ordinal Semi On-Line Scheduling for Jobs with Arbitrary Release Times on Identical Parallel Machines
Key Laboratory of High Performance Computing and Stochastic Information Processing, Department of Mathematics, Hunan Normal University, Changsha, China
Key Laboratory of High Performance Computing and Stochastic Information Processing, Department of Mathematics, Hunan Normal University, Changsha, China
Department of Computer, Hunan Normal University, Changsha, China
- 1 Key Laboratory of High Performance Computing and Stochastic Information Processing, Department of Mathematics, Hunan Normal University, Changsha, China
- 2 Key Laboratory of High Performance Computing and Stochastic Information Processing, Department of Mathematics, Hunan Normal University, Changsha, China
- 3 Department of Computer, Hunan Normal University, Changsha, China
Intelligent Information Management·Volume 09 (2017)·Pages 245–254·Published 1 November 2017·DOI10.4236/iim.2017.96014
Copy link · social · email
Abstract
In this paper, we investigate the problem of semi-on-line scheduling n jobs on m identical parallel machines under the assumption that the ordering of the jobs by processing time is known and the jobs have arbitrary release times. Our aim is to minimize the maximum completion time. An ordinal algorithm is investigated and its worst case ratio is analyzed.
KeywordsScheduleAlgorithmWorst Case RatioParallel Machines
- Graham, R.L. (1969) Bounds on Multiprocessing Timing Anomalies. SIAM Journal on Applied Mathematics, 17, 416-429. https://doi.org/10.1137/0117039
- Li, R.H. and Huang, H.C. (2004) On-Line Scheduling for Jobs with Arbitrary Release Times. Computing, 73, 79-97. https://doi.org/10.1007/s00607-004-0067-1
- Kellerer, H., Kotov, V., Speranza, M.G. and Tuza, Z. (1997) Semi On-Line Algorithms for the Partition Problem. Operations Research Letters, 21, 235-242. https://doi.org/10.1016/S0167-6377(98)00005-4
- He, Y. and Zhang, G. (1999) Semi On-Line Scheduling on Two Identical Machines. Computing, 62, 179-187. https://doi.org/10.1007/s006070050020
- He, Y. and Dósa, G. (2005) Semi-Online Scheduling Jobs with Tightly-Grouped Processing Times on Three Identical Machines. Discrete Applied Mathematics, 150, 140-159. https://doi.org/10.1016/j.dam.2004.12.005
- Cheng, T.C.E., Kellerer, H. and Kotov, V. (2012) Algorithms Better Than LPT for Semi-Online Scheduling with Decreasing Processing Times. Operations Research Letters, 40, 349-352. https://doi.org/10.1016/j.orl.2012.05.009
- Li, R.H. and Huang, H.C. (2007) List Scheduling for Jobs with Arbitrary Release Times and Similar Lengths. Journal of Scheduling, 10, 365-373. https://doi.org/10.1007/s10951-007-0042-8
- Seiden, S., Sgall, J. and Woeginger, G.J. (20000 Semi-Online Scheduling with Decreasing Job Sizes. Operations Research Letters, 27, 215-227.
- 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.
- Liu, W.P., Sidney, J.B. and Vliet, A. (1996) Ordinal Algorithm for Parallel Machine Scheduling. Operations Research Letters, 18, 223-232. https://doi.org/10.1016/0167-6377(95)00058-5
- Tan, Z.Y. and He, Y. (2001) Semi Online Scheduling with Ordinal Data on Two Uniform Machines. Operations Research Letters, 28, 221-231. https://doi.org/10.1016/S0167-6377(01)00071-2
- He, Y. and Tan, Z.Y. (2002) Ordinal-Online Scheduling for Maximizing the Minimum Machine Completion Time. Journal of Combinatorial Optimization, 6, 199-206. https://doi.org/10.1023/A:1013855712183