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

Special Issue: Management Science

Previous Articles Next Articles

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

CLC Number:

90B35
90C27

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.

TrendMD

References 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

Knowledge

Abstract

Cite this article

share this article

References 30

Related Articles 3

Recommended Articles

Metrics

Comments

[1]	Yong Chen, Guang-Ting Chen, Long-Cheng Liu, Yi-Wei Jiang, Zhi-Yi Tan, An Zhang. Online Scheduling with Unit Processing Times and Processing Set Restrictions [J]. Journal of the Operations Research Society of China, 2019, 7(3): 475-484.
[2]	Wen-Hua Li, Xing Chai. Online Scheduling on Bounded Batch Machines to Minimize the MaximumWeighted Completion Time [J]. Journal of the Operations Research Society of China, 2018, 6(3): 455-466.
[3]	Ji Tian · Ruyan Fu · Jinjiang Yuan. Online Over Time Scheduling on Parallel-Batch Machines: A Survey [J]. Journal of the Operations Research Society of China, 2014, 2(4): 445-.