高校应用数学学报B辑
高校應用數學學報B輯
고교응용수학학보B집
APPLIED MATHEMATICS A JOURNAL OF CHINESE UNIVERSITIES
2005年
3期
297-304
,共8页
batch processing%on-line%competitive ratio
The on-line problem of scheduling on a batch processing machine with nonidentical job sizes to minimize makespan is considered.The batch processing machine can process a number of jobs simultaneously as long as the total size of these jobs being processed does not exceed the machine capacity.The processing time of a batch is given by the longest processing time of any job in the batch.Each job becomes available at its arrival time, which is unknown in advance,and its processing time becomes known upon its arrival.The paper deals with two variants: the case only with two distinct arrival times and the general case.For the first case, an on-line algorithm with competitive ratio 119/44 is given.For the latter one, a simple algorithm with competitive ratio 3 is given.For both variants the better ratios can be obtained if the problem satisfies proportional assumption.
