Online Parallel-Batch Machines Scheduling with a Single Server

FU Ru-yan, LIN Lin,

doi:10.13371/j.cnki.chin.q.j.m.2022.04.008

Chinese Quarterly Journal of Mathematics >

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

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

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

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

Cite this article

FU Ru-yan, LIN Lin, . Online Parallel-Batch Machines Scheduling with a Single Server[J]. Chinese Quarterly Journal of Mathematics, 2022 , 37(4) : 403 -411 . DOI: 10.13371/j.cnki.chin.q.j.m.2022.04.008

Options

Outlines

模态框（Modal）标题

Abstract

Cite this article