Batch scheduling algorithm based on dynamic programming

doi:10.3778/j.issn.1002-8331.2010.07.070

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-ling^1，2

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，2

1.暨南大学管理学院，广州 510632
2.广东金融学院计算机系，广州 510520

通讯作者: 钟雪灵

Abstract

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 O（n³） dynamic programming algorithm to batch the sequence optimally.

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

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

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

CLC Number:

TP301

ZHONG Xue-ling^1，2. Batch scheduling algorithm based on dynamic programming[J]. Computer Engineering and Applications, 2010, 46(7): 229-231.

钟雪灵^1，2. 基于动态规划的分批排序算法[J]. 计算机工程与应用, 2010, 46(7): 229-231.

[1]	XU Yangyang，LI Wei，WANG Jie. Optimization of Robot Delay Using Events and Deadline Control [J]. Computer Engineering and Applications, 2021, 57(17): 260-268.
[2]	ZHOU Ruimin, LI Hui. Path Planning of Mobile Robot Based on Improved Dynamic Programming Algorithm [J]. Computer Engineering and Applications, 2020, 56(21): 20-24.
[3]	CHEN Junjie, TONG Shurong, NIE Yafei, ZHANG Jingwen. R&D Program Scheduling and Staff Assignment with Hierarchical Levels of Competency [J]. Computer Engineering and Applications, 2019, 55(3): 209-218.
[4]	LIAN Wei. Globally Optimal Shape Matching Algorithm Using Tree Representation [J]. Computer Engineering and Applications, 2019, 55(1): 217-225.
[5]	ZHU Danhong, LIN Qingxiang, ZHANG Dong. Deadline-aware of congestion control algorithm based on SDN data center network [J]. Computer Engineering and Applications, 2018, 54(3): 68-73.
[6]	ZHANG Yu, CUI Yaodong, LIANG Zehua. Two-dimensional cutting stock problem of multiple logs [J]. Computer Engineering and Applications, 2018, 54(19): 266-270.
[7]	XIAO Hongde. Calculation of minimum count of money and determination of money denomination [J]. Computer Engineering and Applications, 2018, 54(16): 266-270.
[8]	FAN Lingling1，2, LIN Baojun2，3, CHEN Yong3. Key data between satellites once fault-tolerant scheduling algorithm [J]. Computer Engineering and Applications, 2017, 53(14): 61-64.
[9]	SUN Peishuang, HAN Qirui. Improved optimal stitching line applied to image stitching [J]. Computer Engineering and Applications, 2016, 52(21): 218-221.
[10]	FANG Gang1, ZHANG Shemin2. 3-gram statistical language model optimization to expression vector design [J]. Computer Engineering and Applications, 2016, 52(15): 60-64.
[11]	ZHANG Xingong, WANG Hui, BAI Shikun. Two-agent scheduling on single machine to minimize number of tardy jobs [J]. Computer Engineering and Applications, 2016, 52(14): 32-36.
[12]	CUI Xuetao, ZHANG Xihuang. Mechanisms for energy efficiency based on reliability under cloud computing [J]. Computer Engineering and Applications, 2016, 52(1): 42-47.
[13]	LI Huiguang, LI Feng, SHAO Nuan, SHA Xiaopeng, WANG Shuai. Segment-based stereo matching method with ground control points [J]. Computer Engineering and Applications, 2015, 51(23): 160-163.
[14]	ZHANG Yu, XU Hongze, CHEN Jianqiang,ZHANG Luning. Research on optimization strategy of train route control in metallurgical enterprises [J]. Computer Engineering and Applications, 2015, 51(17): 250-254.
[15]	SHEN Lu1，2, JI Yun1, JI Dongbao3, LI Ping4. Pattern matching with variable length wildcards [J]. Computer Engineering and Applications, 2015, 51(15): 43-47.

Batch scheduling algorithm based on dynamic programming

基于动态规划的分批排序算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics