Simultaneous Approximation Ratios for Parallel Machine Scheduling Problems

被引：0

作者：

Long Wan

Jin-Jiang Yuan

机构：

[1] Jiangxi University of Finance and Economics,School of Information Technology

[2] Zhengzhou University,School of Mathematics and Statistics

来源：

Journal of the Operations Research Society of China | 2019年 / 7卷

关键词：

Scheduling; Simultaneous approximation ratio; Global fairness; 90B35; 90C27;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

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 study the two variants under various scheduling environments, such as non-preemptive, preemptive or fractional scheduling on identical, related or unrelated machines.

引用

页码：485 / 500

页数：15

共 50 条

[1] Simultaneous Approximation Ratios for Parallel Machine Scheduling Problems
Wan, Long
Yuan, Jin-Jiang
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA, 2019, 7 (03) : 485 - 500
[2] Approximation schemes for parallel machine scheduling problems with controllable processing times
Jansen, K
Mastrolilli, M
COMPUTERS & OPERATIONS RESEARCH, 2004, 31 (10) : 1565 - 1581
[3] Approximation bounds for a general class of precedence constrained parallel machine scheduling problems
Munier, A
Queyranne, M
Schulz, AS
INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, 1998, 1412 : 367 - 382
[4] Approximation bounds for a general class of precedence constrained parallel machine scheduling problems
Queyranne, M
Schulz, AS
SIAM JOURNAL ON COMPUTING, 2006, 35 (05) : 1241 - 1253
[5] Parallel machine scheduling problems: A survey
Mokotoff, E
ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2001, 18 (02) : 193 - 242
[6] Scheduling efficiency on correlated parallel machine scheduling problems
Yang-Kuei Lin
Operational Research, 2018, 18 : 603 - 624
[7] Scheduling efficiency on correlated parallel machine scheduling problems
Lin, Yang-Kuei
OPERATIONAL RESEARCH, 2018, 18 (03) : 603 - 624
[8] Simultaneous Scheduling of Material Handling and Production Processes: Classification and Heuristics for Parallel Machine Problems
Zouhar, Jan
PROCEEDINGS OF THE 29TH INTERNATIONAL CONFERENCE ON MATHEMATICAL METHODS IN ECONOMICS 2011, PTS I AND II, 2011, : 780 - 785
[9] An approximation algorithm for parallel machine scheduling with a common server
Wang, GQ
Cheng, TCE
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2001, 52 (02) : 234 - 237
[10] Approximation algorithms for parallel machine scheduling with linear deterioration
Liu, Ming
Zheng, Feifeng
Wang, Shijin
Xu, Yinfeng
THEORETICAL COMPUTER SCIENCE, 2013, 497 : 108 - 111

← 1 2 3 4 5 →