Online Scheduling on Two Uniform Unbounded Parallel-Batch Machines to Minimize Makespan

doi:10.1007/s40305-018-0192-8

Journal of the Operations Research Society of China ›› 2019, Vol. 7 ›› Issue (2): 303-319.doi: 10.1007/s40305-018-0192-8

所属专题： Management Science

收稿日期:2017-07-06 修回日期:2017-09-13 出版日期:2019-06-30 发布日期:2019-06-30
通讯作者: Jin-Jiang Yuan, Li-Li Ren, Ji Tian, Ru-Yan Fu E-mail:yuanjj@zzu.edu.cn;lily_8461@126.com;jitian@cumt.edu.cn;furuyan@126.com

Online Scheduling on Two Uniform Unbounded Parallel-Batch Machines to Minimize Makespan

Jin-Jiang Yuan¹, Li-Li Ren¹, Ji Tian², Ru-Yan Fu²

1 School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China;
2 School of Mathematics, China University of Mining and Technology, Xuzhou 221116, Jiangsu, China

Received:2017-07-06 Revised:2017-09-13 Online:2019-06-30 Published:2019-06-30
Contact: Jin-Jiang Yuan, Li-Li Ren, Ji Tian, Ru-Yan Fu E-mail:yuanjj@zzu.edu.cn;lily_8461@126.com;jitian@cumt.edu.cn;furuyan@126.com
Supported by:
The first author was supported by the National Natural Science Foundation of China (No. 11671368) and Natural Science Foundation of Henan Province (No. 15IRTSTHN006). Tian was also supported by Natural Science Foundation of Jiangsu Province (No. BK20130169) and the National Natural Science Foundation of China (No. 61573362).

摘要/Abstract

Abstract: We study an online (over time) scheduling problem on two uniform unbounded parallel-batchmachines with processing speed 1 and v(0 < v ≤1),respectively, to minimize the makespan. We first show that no online algorithm can have a competitive ratio less than 1 + α_L, where α_L=(√5-1)/2 ≈ 0.618 if 0 < v 1/2, and α_L=α₂(v) is the positive root of α³+3α²+(3-1/v)α-1/v=0 if 1/2 < v 1. This lower bound is still valid when all jobs have the same processing times. Then, we provide an online algorithm with a competitive ratio at most min{(√5+1)/2, √2/v}. When the jobs have the same processing times, we present the best possible online algorithm with a competitive ratio 1 + α_L.

Key words: Online scheduling, Uniform parallel-batch machines, Makespan, Competitive ratio

中图分类号:

90B35
90C27

. [J]. Journal of the Operations Research Society of China, 2019, 7(2): 303-319.

Jin-Jiang Yuan, Li-Li Ren, Ji Tian, Ru-Yan Fu. Online Scheduling on Two Uniform Unbounded Parallel-Batch Machines to Minimize Makespan[J]. Journal of the Operations Research Society of China, 2019, 7(2): 303-319.

参考文献 30

[1]	Lee, C.Y., Uzsoy, R., Martin-Vega, L.A.:Efficient algorithms for scheduling semiconductor burn-in operations. Oper. Res. 40, 764-775(1992)
[2]	Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.:Sequencing and scheduling:algorithms and complexity. In:Graves, S.C., Zipkin, P.H., Rinnooy Kan, A.H.G. (eds.) Logistics of Production and Inventory; Handbooks Operation Research Management Science 4, pp. 445-522. North-Holland, Amsterdam (1993)
[3]	Lee, C.Y., Uzsoy, R.:Minimizing makespan on a single batch processing machine with dynamic job arrivals. Int. J. Prod. Res. 37, 219-236(1999)
[4]	Poon, C.K., Zhang, P.X.:Minimizing makespan in batch machine scheduling. Algorithmica 39, 155-174(2004)
[5]	Brucker, P., Gladky, A., Hoogeveen, H., Kovalyov, M.Y., Potts, C.N., Tautenhahn, T., van de Velde, S.L.:Scheduling a batching machine. J. Sched. 1, 31-54(1998)
[6]	Liu, Z.H., Yu, W.C.:Scheduling one batch processor subject to job release date. Discrete Appl. Math. 105, 129-136(2000)
[7]	Deng, X.T., Poon, C.K., Zhang, Y.Z.:Approximation algorithms in batch processing. J. Comb. Optim. 7, 247-257(2003)
[8]	Zhang, G.C., Cai, X.Q., Wong, C.K.:Online algorithms for minimizing makespan on batch processing machines. Nav. Res. Logist. 48, 241-258(2001)
[9]	Poon, C.K., Yu, W.C.:A flexible online scheduling algorithms for batch machine with infinite capacity. Ann. Oper. Res. 133, 175-181(2005)
[10]	Poon, C.K., Yu, W.C.:On-line scheduling algorithms for a batch machine with finite capacity. J. Comb. Optim. 9, 167-186(2005)
[11]	Zhang, G.C., Cai, X.Q., Wong, C.K.:Optimal online algorithms for scheduling on parallel batch processing machines. ⅡE Trans. 35, 175-181(2003)
[12]	Nong, Q.Q., Cheng, T.C.E., Ng, C.T.:An improved on-line algorithm for scheduling on two unrestrictive parallel batch processing machines. Oper. Res. Lett. 36, 584-588(2008)
[13]	Noga, J., Seiden, S.S.:An optimal online algorithm for scheduling two machines with release times. Theoret. Comput. Sci. 268, 133-143(2001)
[14]	Tian, J., Fu, R.Y., Yuan, J.J.:A best online algorithm for scheduling on two parallel batch machines. Theor. Comput. Sci. 410, 2291-2294(2009)
[15]	Liu, P.H., Lu, X.W., Fang, Y.:A best possible deterministic on-line algorithm forminimizingmakespan on parallel batch machines. J. Sched. 15, 77-81(2012)
[16]	Tian, J., Cheng, T.C.E., Ng, C.T., Yuan, J.J.:Online scheduling on unbounded parallel-batch machines to minimize makespan. Inf. Process. Lett. 109, 1211-1215(2009)
[17]	Fu, R.Y., Tian, J., Yuan, J.J., Lin, Y.X.:On-line scheduling in a parallel batch processing system to minimize makespan using restarts. Theor. Comput. Sci. 374, 196-202(2007)
[18]	Yuan, J.J., Fu, R.Y., Ng, C.T., Cheng, T.C.E.:A best on-line algorithm for unbounded parallel batch scheduling to minimize makespan with restarts. J. Sched. 14, 361-369(2011)
[19]	Cao, J.F., Yuan, J.J., Li, W.J., Bu, H.L.:Online scheduling on batching machines to minimize the total weighted completion time of jobs with precedence constraints and identical processing times. Int. J. Syst. Sci. 42, 51-55(2011)
[20]	Chen, B., Deng, X.T., Zang, W.A.:On-line scheduling a batch processing system to minimize total weighted job completion time. J. Comb. Optim. 8, 85-95(2004)
[21]	Fu, R.Y., Cheng, T.C.E., Ng, C.T., Yuan, J.J.:Online scheduling on two parallel-batching machines with limited restarts to minimize the makespan. Inf. Process. Lett. 110, 444-450(2010)
[22]	Fu, R.Y., Tian, J., Yuan, J.J., He, C.:On-line scheduling on a batch machine to minimize makespan with limited restarts. Oper. Res. Lett. 36, 255-258(2008)
[23]	Fu, R.Y., Tian, J., Yuan, J.J.:On-line scheduling on an unbounded batch machine to minimize makespan of two families of jobs. J. Sched. 12, 91-97(2009)
[24]	Nong, Q.Q., Yuan, J.J.:An on-line algorithm for the bounded p-batch scheduling with chain precedence constraints and unit processing time. Found. Comput. Decis. Sci. 31, 277-290(2006)
[25]	Nong, Q.Q., Yuan, J.J., Fu, R.Y., Lin, L., Tian, J.:The single-machine parallel-batching on-line scheduling problem with family jobs to minimize makespan. Intern. J. Prod. Econ. 111, 435-440(2008)
[26]	Tian, J., Cheng, T.C.E., Ng, C.T., Yuan, J.J.:Online scheduling on unbounded parallel-batch machines with incompatible job families. Theor. Comput. Sci. 412, 2380-2386(2011)
[27]	Tian, J., Fu, R.Y., Yuan, J.J.:On-line scheduling with delivery time on a batch machine. Theor. Comput. Sci. 374, 49-57(2007)
[28]	Tian, J., Wang, Q., Fu, R.Y., Yuan, J.J.:Online scheduling on the unbounded drop-line batch machines to minimize the maximum delivery completion time. Theor. Comput. Sci. 617, 65-68(2016)
[29]	Yuan, J.J., Ng, C.T., Cheng, T.C.E.:Best semi-online algorithms for unbounded parallel batch scheduling. Discrete Appl. Math. 159, 838-847(2011)
[30]	Tian, J., Fu, R.Y., Yuan, J.J.:Online over time scheduling on parallel-batch machines:a survey. J. Oper. Res. Soc. China 2, 445-454(2014)

Online Scheduling on Two Uniform Unbounded Parallel-Batch Machines to Minimize Makespan

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 30

相关文章 4

编辑推荐

Metrics

本文评价