有公共交货期的单机分批排序问题（英文）  

Scheduling with a Common Due Date on a Single Batch Processing Machine

作　　者：刘丽丽[1] 任韩[2,3] 唐国春[4] 

机构地区：[1]上海第二工业大学应用数学系,上海201209 [2]华东师范大学数学系,上海200062 [3]上海市核心数学与实践重点实验室,上海200062 [4]上海第二工业大学经济管理学院,上海201209

出　　处：《重庆师范大学学报（自然科学版）》2017年第2期1-5,共5页Journal of Chongqing Normal University:Natural Science

基　　金：National Natural Science Foundation of China(No.11601316);The Discipline "Applied Mathematics" of Shanghai Second Polytechnic University(No.XXKPY1604)~~

摘　　要：【目的】单机分批排序问题有着广泛的应用背景,很多问题是NP-困难的。有公共交货期的单机分批排序问题是一个非常重要的研究方向。【方法】利用组合最优化的方法,研究工件有公共交货期的最小化误工工件个数和总延误的单机分批排序问题。【结果】对于最小化误工工件个数问题提出了一个多项式时间算法,对于最小化总延误提出了一个伪多项式时间的动态规划算法。【结论】对于其他有公共交货期的分批排序问题的研究提供了重要的研究方法。[Purposes]Scheduling problems on a single batch processing machine have a wide range of practical applications,and most of them are NP-hard.Single machine batch scheduling problems with common due date is a very important research direction.[Methods]By using the combinatorial optimization methods,the problems of scheduling jobs with a common due date on a single batch processing machine to minimize the number of tardy jobs and the total tardiness are studied.[Findings]A polynomial time algorithm is presented for minimizing the number of tardy jobs and a pseudo-polynomial time dynamic programming algorithm is proposed for minimizing the total tardiness.[Conclusions]The research methods can be applied to solve other batch scheduling problems with a common due date.

关 键 词：批处理 公共交货期 动态规划 

分 类 号：O223[理学—运筹学与控制论]