A Note on DP Algorithm for Batching Scheduling to Minimize Maximum Lateness

LIN Hao, HE Cheng

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

Chinese Quarterly Journal of Mathematics >

2018 , Vol. 33 >Issue 2: 206 - 211

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

A Note on DP Algorithm for Batching Scheduling to Minimize Maximum Lateness

Expand

School of Science, Henan University of Technology

LIN Hao(1974-), male, native of Taisan, Guangdong, an associate professor of Henan University of Technology, M.S., engages in network optimization; He Cheng(1975-), female, native of Xinyang, Henan, an associate professor of Henan University of Technology, Ph D., engages in the scheduling theory and its applications.

Accepted date: 2016-01-23

Online published: 2020-10-09

Supported by

Supported by NSFC(11571323; 11201121)； NSFSTDOHN(162300410221)； NSFEDOHN(2013GGJS-079)；

Fold

Abstract

In parallel-batching machine scheduling, all jobs in a batch start and complete at the same time, and the processing time of the batch is the maximum processing time of any job in it. For the unbounded parallel-batching machine scheduling problem of minimizing the maximum lateness, denoted 1|p-batch|L_max, a dynamic programming algorithm with time complexity O（n²） is well known in the literature.Later, this algorithm is improved to be an O（n log n） algorithm. In this note, we present another O（n log n） algorithm with simplifications on data structure and implementation details.

Key words： Batching scheduling; Parallel-batching machine; Maximum lateness; Polynomial algorithm

Cite this article

LIN Hao, HE Cheng . A Note on DP Algorithm for Batching Scheduling to Minimize Maximum Lateness[J]. Chinese Quarterly Journal of Mathematics, 2018 , 33(2) : 206 -211 . DOI: 10.13371/j.cnki.chin.q.j.m.2018.02.012

Options

Outlines

模态框（Modal）标题

Abstract

Cite this article