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

Expand
  • 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 date: 2017-07-06

  Revised date: 2017-09-13

  Online published: 2019-06-30

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

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=α2(v) is the positive root of α3+3α2+(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.

Cite this article

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 . DOI: 10.1007/s40305-018-0192-8

References

[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)
Options
Outlines

/