Motivated by the problem to approximate all feasible schedules by one schedule in a given scheduling environment, we introduce in this paper the concepts of strong simultaneous approximation ratio and weak simultaneous approximation ratio. Then we studythetwovariantsundervariousschedulingenvironments,suchasnon-preemptive, preemptive or fractional scheduling on identical, related or unrelated machines.
Long Wan, Jin-Jiang Yuan
. Simultaneous Approximation Ratios for Parallel Machine Scheduling Problems[J]. Journal of the Operations Research Society of China, 2019
, 7(3)
: 485
-500
.
DOI: 10.1007/s40305-019-00253-0
[1] Csirik, J., Kellerer, H., Woeginger, G.:The exact LPT-bound of maximizing the minimum completion time. Oper. Res. Lett. 11, 281-287(1992)
[2] Deuermeyer, B.L., Friesen, D.K., Langston, A.M.:Scheduling to maximize the minimum processor finish time in a multiprocessor system. SIAM J. Discrete Math. 3, 190-196(1982)
[3] Graham, R.L.:Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45, 1563-1581(1966)
[4] Graham, R.L.:Bounds for multiprocessing timing anomalies. SIAM J. Appl. Math. 17, 416-429(1969)
[5] McNaughton, R.:Scheduling with deadlines and loss functions. Manag. Sci. 6, 1-12(1959)
[6] Bhargava, R., Goel, A., Meyerson, A.:Using approximate majorization to characterize protocol fairness. In:Proceedings of the 2001 ACM Special Interest Group for the computer systems performance evaluation community. International Conference on Measurement and Modeling of Computer Systems, pp. 330-331. ACM, New York (2001)
[7] Goel, A., Meyerson, A., Plotkin, S.:Combining fairness with throughput:online routing with multiple objectives. J. Comput. Syst. Sci. 63, 62-79(2001)
[8] Goel, A., Meyerson, A., Plotkin, S.:Approximate majorization and fair online load balancing. ACM Trans. Algorithms 1, 338-349(2005)
[9] Kleinberg, J., Rabani, Y., Tardos, É.:Fairness in routing and load balancing. J. Comput. Syst. Sci. 63, 2-20(2001)
[10] Kumar, A., Kleinberg, J.:Fairness measures for resource allocation. SIAM J. Comput. 36, 657-680(2006)
