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

作　　者：LIN Hao HE Cheng 

机构地区：[1]School of Science, Henan University of Technology, Zhengzhou, Henan 450001

出　　处：《Chinese Quarterly Journal of Mathematics》2018年第2期206-211,共6页数学季刊（英文版）

基　　金：Supported by NSFC(11571323; 11201121);NSFSTDOHN(162300410221);NSFEDOHN(2013GGJS-079)

摘　　要：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^2) 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.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^2） 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 

分 类 号：O221.7[理学—运筹学与控制论]