| ON-LINE PROBLEMS OF MINIMIZING MAKESPAN ON A SINGLE BATCH PROCESSING MACHINE WITH NONIDENTICAL JOB SIZES |
| |
| 引用本文： | Shi Yongqiang Yao Enyu. ON-LINE PROBLEMS OF MINIMIZING MAKESPAN ON A SINGLE BATCH PROCESSING MACHINE WITH NONIDENTICAL JOB SIZES[J]. 高校应用数学学报(英文版), 2005, 20(3): 297-304. DOI: 10.1007/s11766-005-0005-9 |
| |
| 作者姓名： | Shi Yongqiang Yao Enyu |
| |
| 作者单位： | Dept. of Math. ,Zhejiang Univ. ,Hangzhou 310027,China. |
| |
| 摘 要： | 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.
|
| 关 键 词： | 过程控制 时序安排 机械容量 优化设计 |
| 收稿时间： | 2005-03-02 |
On-line problems of minimizing makespan on a single batch processing machine with nonidentical job sizes |
| |
| Shi Yongqiang,Yao Enyu. On-line problems of minimizing makespan on a single batch processing machine with nonidentical job sizes[J]. Applied Mathematics A Journal of Chinese Universities, 2005, 20(3): 297-304. DOI: 10.1007/s11766-005-0005-9 |
| |
| Authors: | Shi Yongqiang Yao Enyu |
| |
| Affiliation: | (1) Dept. of Math., Zhejiang Univ., 310027 Hangzhou, China |
| |
| Abstract: | 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. |
| |
| Keywords: | batch processing on-line competitive ratio. |
| 本文献已被 CNKI 维普 SpringerLink 等数据库收录！ |
