Chinese Quarterly Journal of Mathematics ›› 2022, Vol. 37 ›› Issue (4): 403-411.doi: 10.13371/j.cnki.chin.q.j.m.2022.04.008

Previous Articles     Next Articles

Online Parallel-Batch Machines Scheduling with a Single Server

  

  1. 1. School of Mathematics, China University of Mining and Technology, Xuzhou 221116, China; 2. Institute of Technology and Standards Research, China Academy of Information and Communication Technology, Beijing 100191, China; 3. Key Laboratory of Internet of Vehicle Technical Innovation and Testing (CAICT), Ministry of Industry and Information Technology, Beijing 100191, China.
  • Received:2022-11-14 Online:2022-12-30 Published:2022-12-30
  • Contact: FU Ru-yan (1980-), female, native of Shangqiu, Henan, associate professor of China University of Mining and Technology, engages in scheduling; E-mail: furuyan@cumt.edu.cn
  • About author:FU Ru-yan (1980-), female, native of Shangqiu, Henan, associate professor of China University of Mining and Technology, engages in scheduling; LIN Lin (1983-), female, native of Luohe, Henan, senior engineer of China Academy of Information and Communication Technology, engages in internet of vehicle.

Abstract: We consider parallel-batch machines scheduling problem with a single server to minimize the maximum completion time. Jobs arrive over time. Every batch has to be loaded by the sever before being processed on machines. The loading (setup) operation of a batch occurs only when some machine is idle, and the server can perform only one setup operation every time. For some special case, we provide a best possible online algorithm with competitive ratio (√ 5+ 1)/2. For general case, we give another online algorithm with competitive ratio 3. 

Key words: Parallel-batch machines, Server, Online algorithm, Competitive ratio

CLC Number: