Operations Research Transactions >
2019 , Vol. 23 >Issue 1: 111 - 118
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2019.01.013
Online batch scheduling problem on uniform machines with agreeable processing times
Received date: 2017-12-18
Online published: 2019-03-15
We study the online batch scheduling problem on two uniform machines, where the batch capacity is unbounded. When the arrival times and the processing times of jobs are agreeable, two scheduling models whose objectives are to minimize the makespan and flow-time are developed and they are expressed as Q2|ri < rj⇒ pi ≤ pj, B=∞, on-line|Cmax and Q2|ri < rj⇒ pi ≥ pj, B=∞, on-line|Fmax. Without loss of generality, the speeds of the two machines are assumed to be 1 and s,s ≥ 1. We propose an on-line algorithm and prove the competitive ratios of the algorithm are not more than s+α and 1+1/α, respectively, where α is the positive root of α2+sα-1=0. Moreover, for the former scheduling model, we prove that the competitive ratio of the algorithm is not more than 1.618, when s=1.
PENG Nannan, ZHANG Yuzhong, BAI Qingguo, WANG Chengfei . Online batch scheduling problem on uniform machines with agreeable processing times[J]. Operations Research Transactions, 2019 , 23(1) : 111 -118 . DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.013
[1] Zhang G C, Cai X Q, Wong C K. On-line algorithm for minimizing makespan on batch processing machines[J]. Naval Research Logistics, 2001, 48(3):241-258.
[2] Ridouard F, Ricard P, Marineau P. On-line scheduling on a batch processing machine with unbounded batch size to minimizing the makespan[J]. European Journal of Operation Research, 2008, 189(3):1327-1342.
[3] 焦成文, 李文华. 工件按加工长度不增序到达的最小化最大流程在线分批排序[J]. 运筹学学报, 2013, 17(4):96-102.
[4] 王成飞, 张玉忠. 提前预知信息的在线分批排序问题[J]. 运筹学学报, 2016, 20(1):84-90.
[5] 张玉忠, 柏庆国, 徐健腾. 工件有尺寸且分两批到达的单机分批排序[J]. 运筹学报, 2006, 10(4):99-105.
[6] Fu R Y, Cheng T C E, Ng C T, et al. An optimal online algorithm for single parallel-batch machine scheduling with incompatible job families to minimize makespan[J]. Operations Research Letters, 2013, 41(3):216-219.
[7] Li W J. A best possible online algorithm for the parallel-machine scheduling to minimize the maximum weighted completion time[J]. Asia-Pacific Journal of Operational Research, 2015, 32(4):1-10.
[8] Li W H, Gao J, Yuan J J. Online-list scheduling on a single bounded parallel-batch machine to minimize makespan[J]. Asia-Pacific Journal of Operational Research, 2015, 32(4):1-15.
[9] Liu P H, Lu X W, Fang Y. A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines[J]. Journal of Scheduling, 2012, 15(1):77-81.
[10] Liu P H, Lu X W. Online unbounded batch scheduling on parallel machines with delivery times[J]. Journal of Combinatorial Optimization, 2015, 29(1):228-236.
[11] Liu H L, Yuan J J, Li W J. Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart[J]. Journal of Combinatorial Optimization, 2016, 31(4):1609-1622.
[12] Zhou H, Jiang Y W, Zhou P. Total completion time minimization scheduling on two hierarchical uniform machines[J]. Theoretical Computer Science, 2017, 702:65-76.
[13] Cao Q, Liu Z H. Semi-online scheduling with bounded job sizes on two uniform machines[J].Theoretical Computer Science, 2016, 652:1-17.
[14] Deng X T, Poon C K, Zhang Y Z. Approximation algorithms in batch processing[J]. Journal of Combinatorial Optimization, 2003, 7(3):247-257.
[15] Zhang G C, Cai X Q, Wong C K. Optimal on-line algorithms for scheduling on parallel batch processing machines[J]. ⅡE Transactions, 2003, 35(2):175-181.
[16] Ma R, Wan L, Wei L J, et al. Online bounded-batch scheduling to minimize total weighted completion time on parallel machines[J]. International Journal of Production Economics, 2014, 156:31-38.
/
| 〈 |
|
〉 |
