数学季刊 >

2022 , Vol. 37 >Issue 4: 403 - 411

DOI: https://doi.org/10.13371/j.cnki.chin.q.j.m.2022.04.008

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

展开
  • 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.
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.

收稿日期: 2022-11-14

  网络出版日期: 2022-12-30

收起

Online Parallel-Batch Machines Scheduling with a Single Server

Expand
  • 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.
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.

Received date: 2022-11-14

  Online published: 2022-12-30

Fold

摘要

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

本文引用格式

付乳燕, 林琳 . 带有单个服务器的多台平行批处理机在线排序问题[J]. 数学季刊, 2022 , 37(4) : 403 -411 . DOI: 10.13371/j.cnki.chin.q.j.m.2022.04.008

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

Options
文章导航

/

〈 〉

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