一类简单线性恶化加工时间的单机调度问题研究

• 作者: 黄安宁
• 来源期刊: 新型工业化
• 关键词: 单机调度 整数规划 恶化加工时间 计算复杂度 完全多项式时间近似方案
• 年，卷（期）: 2017,（10）
• 所属期刊栏目: 设计与研究
• 页码范围: 57-62
• 页数: 6页
• 字数: 3559字
• 语种: 中文
• DOI: 10.19335/j.cnki.2095-6649.2017.10.009

摘要

单机调度是生产管理领域的重要研究方向,对其的研究可追溯到60多年前.近年来,在调度问题中考虑恶化工件的影响,吸引了越来越多研究者的关注.这类工件的处理时间可能随着其加工前的等待时间的增长而增长,大大加大了调度问题的复杂度.本文对可恢复模式下的一类简单线性恶化加工时间的单机调度问题进行了研究.该问题以最小化工件完成时间为目标,本文首先证明了该问题的最优解能通过0-1整数规划获得;然后证明了该问题在一般情况下其复杂度为NP-hard;最后为其给出了一个完全多项式时间近似方案.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄安宁		4	24	1.0	4.0