Journal of the Operations Research Society of China ›› 2019, Vol. 7 ›› Issue (3): 485-500.doi: 10.1007/s40305-019-00253-0

Special Issue: Management Science

Previous Articles     Next Articles

Simultaneous Approximation Ratios for Parallel Machine Scheduling Problems

Long Wan1, Jin-Jiang Yuan2   

  1. 1 School of Information Technology, Jiangxi University of Finance and Economics, Nanchang 310013, China;
    2 School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China
  • Received:2018-07-31 Revised:2019-01-08 Online:2019-09-30 Published:2019-10-08
  • Contact: Jin-Jiang Yuan, Long Wan E-mail:yuanjj@zzu.edu.cn;cocu3328@163.com

Abstract: 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.

Key words: Scheduling, Simultaneous approximation ratio, Global fairness

CLC Number: