关于最小化最大延迟的分批排序问题的一个动态规划算法的注解

林浩, 何程

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

数学季刊 >

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

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

关于最小化最大延迟的分批排序问题的一个动态规划算法的注解

展开

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.

录用日期: 2016-01-23

网络出版日期: 2020-10-09

基金资助

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

收起

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

Expand

School of Science, Henan University of Technology

Accepted date: 2016-01-23

Online published: 2020-10-09

Supported by

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

Fold

摘要

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.

关键词： Batching scheduling; Parallel-batching machine; Maximum lateness; Polynomial algorithm

本文引用格式

林浩, 何程 . 关于最小化最大延迟的分批排序问题的一个动态规划算法的注解[J]. 数学季刊, 2018 , 33(2) : 206 -211 . DOI: 10.13371/j.cnki.chin.q.j.m.2018.02.012

Abstract

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

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract