数学季刊 ›› 2022, Vol. 37 ›› Issue (4): 403-411.doi: 10.13371/j.cnki.chin.q.j.m.2022.04.008

• • 上一篇    下一篇

带有单个服务器的多台平行批处理机在线排序问题

  

  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.
  • 收稿日期:2022-11-14 出版日期:2022-12-30 发布日期:2022-12-30
  • 通讯作者: 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
  • 作者简介: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.

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.

PDF (PC)

50

摘要： 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. 

关键词: Parallel-batch machines, Server, Online algorithm, Competitive ratio

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

中图分类号: 

版权所有 © 《数学季刊》编辑部
地址：河南省开封市明伦街85号河南大学数学季刊编辑部
电话：0371-23881698　E-mail: sxjk@henu.edu.cn　QQ: 2454327236
本系统由北京玛格泰克科技发展有限公司设计开发　技术支持：support@magtech.com.cn