数学季刊 ›› 2018, Vol. 33 ›› Issue (2): 206-211.doi: 10.13371/j.cnki.chin.q.j.m.2018.02.012

• • 上一篇    下一篇

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

  

  1. School of Science, Henan University of Technology
  • 接受日期:2016-01-23 出版日期:2018-06-30 发布日期:2020-10-09
  • 作者简介: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.
  • 基金资助:
    Supported by NSFC(11571323; 11201121)； NSFSTDOHN(162300410221)； NSFEDOHN(2013GGJS-079)；

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

  1. School of Science, Henan University of Technology
  • Accepted:2016-01-23 Online:2018-06-30 Published:2020-10-09
  • About author: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.
  • Supported by:
    Supported by NSFC(11571323; 11201121)； NSFSTDOHN(162300410221)； NSFEDOHN(2013GGJS-079)；

PDF (PC)

145

摘要： 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|Lmax, a dynamic programming algorithm with time complexity O（n2） 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

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|Lmax, a dynamic programming algorithm with time complexity O（n2） 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

中图分类号: 

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