数学季刊 ›› 2018, Vol. 33 ›› Issue (2): 206-211.doi: 10.13371/j.cnki.chin.q.j.m.2018.02.012
摘要: 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.
中图分类号: