Research ArticleOpen AccessGoogle Scholar indexed
Better Algorithm of Ordinal Online Schedule for Jobs with Similar Sizes on Two Machines
Key Laboratory of Computing and Stochastic Mathematics (Ministry of Education), Department of Mathematics, School of Mathematics and Statistics, Hunan Normal University, Changsha, China
Key Laboratory of Computing and Stochastic Mathematics (Ministry of Education), Department of Mathematics, School of Mathematics and Statistics, Hunan Normal University, Changsha, China
College of Information Science and Engineering, Hunan Normal University, Changsha, China
- 1 Key Laboratory of Computing and Stochastic Mathematics (Ministry of Education), Department of Mathematics, School of Mathematics and Statistics, Hunan Normal University, Changsha, China
- 2 Key Laboratory of Computing and Stochastic Mathematics (Ministry of Education), Department of Mathematics, School of Mathematics and Statistics, Hunan Normal University, Changsha, China
- 3 College of Information Science and Engineering, Hunan Normal University, Changsha, China
American Journal of Operations Research·Volume 09 (2019)·Pages 235–243·Published 14 August 2019·DOI10.4236/ajor.2019.95015
Copy link · social · email
Abstract
Ordinal online schedule for jobs with similar sizes in on two parallel machines system is considered. Firstly it is proved that the worst case performance ratio of the existing algorithm P 2 cannot be improved even if the job processing times are known in for any . Then a better algorithm named S is developed and its worst case performance ratio is given for .
KeywordsSemi-Online Scheduling<i>P<sub>m</sub></i>AlgorithmS AlgorithmWorst Performance Ratio
- Graham R.L. (1969) Bounds on Multiprocessing Timing Anomalies. SIAM Journal on Applied Mathematics, 17, 416-429. https://doi.org/10.1137/0117039
- 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.
- 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.
- He, Y. and Zhang, G. (1999) Semi on-Line Scheduling on Two Identical Machines. Computing, 62, 179-187. https://doi.org/10.1007/s006070050020
- 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
- Lin, L. and Tan, Z. (2014) Inefficiency of Nash Equilibrium for Scheduling Games with Constrained Jobs: A Parametric Analysis. Theoretical Computer Science, 521, 123-134. https://doi.org/10.1016/j.tcs.2013.11.012
- Gupta, S., Dalal, U.D. and Mishra, V.N. (2014) Novel Analytical Approach of Conventional Mapping Scheme with Discrete Hartley Transform in OFDM System. American Journal of Operations Research, 4, 281-292. https://doi.org/10.4236/ajor.2014.45027
- Liu, W.P., Sidney, J.B. and Vliet, A.V. (1996) Ordinal Algorithms for Parallel Machine Scheduling. Operations Research Letters, 18, 223-232. https://doi.org/10.1016/0167-6377(95)00058-5