Operations Research Transactions
• Original Articles • Previous Articles Next Articles
WANG Cheng-Fei, ZHANG Yu-Zhong, BAI Qing-Guo
Received:
Revised:
Online:
Published:
Contact:
Abstract: An online batch scheduling with linear deterioration effect on single machine is considered. Jobs arrive over time. A batch processing machine can handle up to $B$ jobs simultaneously. The actual processing time $p_j$ of Job $J_j$ is assumed to be a linear function of its starting time $t$, i.e., $p_j=b_j+\alpha t$, where $\alpha >0$ is the deterioration ratio, $b_j$ is the basic processing time, which is unknown until it arrives. The processing time of a batch is given by the longest processing time of any job in the batch. For single machine with unbounded capacity to minimize makespan problem, we give an optimal online algorithm, which competitive ratio matches the lower bound of the problem.
Key words: batch scheduling, deterioration effect, competitive, online algorithm
WANG Cheng-Fei, ZHANG Yu-Zhong, MIAO Cui-Xia, BAI Qing-Guo. Online Batch Scheduling with Linear Deterioration Effect[J]. Operations Research Transactions.
0 / / Recommend
Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks
URL: https://www.ort.shu.edu.cn/EN/
https://www.ort.shu.edu.cn/EN/Y2011/V15/I3/107