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

所属专题: Management Science

• • 上一篇    下一篇

  

  • 收稿日期:2018-07-31 修回日期:2019-01-08 出版日期:2019-09-30 发布日期:2019-10-08
  • 通讯作者: Jin-Jiang Yuan, Long Wan E-mail:yuanjj@zzu.edu.cn;cocu3328@163.com
  • 基金资助:
    The first author was supported by the National Natural Science Foundation of China (Nos. 11601198 and 71761015). The second author was supported by the National Natural Science Foundation of China (No. 11671368).

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

中图分类号: