An optimal online algorithm for the parallel-batch scheduling with job processing time compatibilities |
| |
| Authors: | Ruyan Fu Ji Tian Shisheng Li Jinjiang Yuan |
| |
| Affiliation: | 1.School of Mathematics,China University of Mining and Technology,Xuzhou,People’s Republic of China;2.Department of Information and Computation Science,Zhongyuan University of Technology,Zhengzhou,People’s Republic of China;3.School of Mathematics and Statistics,Zhengzhou University,Zhengzhou,People’s Republic of China |
| |
| Abstract: | We consider the online (over time) scheduling on a single unbounded parallel-batch machine with job processing time compatibilities to minimize makespan. In the problem, a constant (alpha >0) is given in advance. Each job (J_{j}) has a normal processing time (p_j). Two jobs (J_i) and (J_j) are compatible if (max {p_i, p_j} le (1+alpha )cdot min {p_i, p_j}). In the problem, mutually compatible jobs can form a batch being processed on the machine. The processing time of a batch is equal to the maximum normal processing time of the jobs in this batch. For this problem, we provide an optimal online algorithm with a competitive ratio of (1+beta _alpha ), where (beta _alpha ) is the positive root of the equation ((1+alpha )x^{2}+alpha x=1+alpha ). |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
