Online batch scheduling with kind release times and incompatible families to minimize makespan |
| |
| Authors: | Wenjie Li Shisheng Li Qi Feng |
| |
| Institution: | 1.School of Mathematical Sciences,Luoyang Normal University,Luoyang,People’s Republic of China;2.Department of Information and Computation Science,Zhongyuan University of Technology,Zhengzhou,People’s Republic of China |
| |
| Abstract: | This paper studies online scheduling of jobs with incompatible families on a single unbounded batch machine under the KRT environment, where jobs arrive over time and “KRT” means that in the online setting no jobs can be released when the machine is busy. The goal is to determine a feasible schedule to minimize the makespan. We provide a best online algorithm with a competitive ratio of \(1+\frac{\sqrt{f^{2}-f+1}-1}{f}\), where f is the number of job families. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
