到达时间与工期同序并带有不可用区间的串行批处理机问题

• 作者: 赵玉芳 陈状状 何欣怡
• 来源期刊: 沈阳师范大学学报（自然科学版）
• 学科: 数学
• 关键词: 串行批处理机 不可用区间 到达时间与工期同序 动态规划
• 年，卷（期）: 2022,（1）
• 所属期刊栏目: 运筹学与控制论|Operations Research and Cybernetics
• 页码范围: 35-41
• 页数: 7页
• 分类号: O223
• 语种: 中文
• DOI: 10.3969/j.issn.1673-5862.2022.01.007

摘要

在制造业中,对串行批处理机的研究有重要的现实意义.考虑了机器带有不可用区间的单机串行批处理机问题.其中,工件的到达时间与工期是同序的.串行批处理机的容量为无限,工件带有2种不同的到达时间,分别为0或r,每批开始加工之前的安装时间固定且相同,在安装时间及不可用区间之内机器不能加工工件.批的加工时间为批内工件的加工时间之和,批的完工时间为批内最后一个工件加工完成的时间.同一批中工件的开始加工时间和完工时间分别相同,为该批的开始加工时间和完工时间.按时完工批按批EDD序排序.首先分析了问题的最优解性质,然后给出了动态规划算法并分析其时间复杂性,最后用数值例子验证了算法的正确性.