Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (7): 229-231.DOI: 10.3778/j.issn.1002-8331.2010.07.070

• 工程与应用 • Previous Articles     Next Articles

Batch scheduling algorithm based on dynamic programming

ZHONG Xue-ling1,2   

  1. 1.College of Management,Jinan University,Guangzhou 510632,China
    2.Department of Computer,Guangdong University of Finance,Guangzhou 510520,China
  • Received:2008-09-04 Revised:2008-12-19 Online:2010-03-01 Published:2010-03-01
  • Contact: ZHONG Xue-ling



  1. 1.暨南大学 管理学院,广州 510632
    2.广东金融学院 计算机系,广州 510520
  • 通讯作者: 钟雪灵

Abstract: This paper studies the batch scheduling problem of minimizing maximum earliness on single machine.The feasibility of the problem is considered primarily since each job must be completed processing before or on its deadline.If the problem is feasible,there will exist an optimal schedule in which the jobs are sequenced according to an Earliest Deadline(ED) rule.It also provides an On3) dynamic programming algorithm to batch the sequence optimally.

Key words: batch scheduling, deadline, earliness, dynamic programming

摘要: 研究了在给定截止期限(deadline)下的单机分批(batch)排序问题,目标函数是最大提前完工时间。由于工件不能延迟,因此先讨论了问题可行解的存在。当问题有可行解时,证明了工件按最早截止期限(Earliest Deadline,ED)规则的排序是一个最优排序,接着给出一个时间复杂度为On3)的动态规划算法来获得最优分批。

关键词: 分批排序, 截止期限, 提前完工时间, 动态规划

CLC Number: