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

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

黄安宁

【期刊名称】《新型工业化》 【年(卷),期】2017(007)010

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

【关键词】单机调度;整数规划;恶化加工时间;计算复杂度;完全多项式时间近似方案

【作者】黄安宁

【作者单位】重庆旗能电铝有限公司,重庆401420 【正文语种】中文 【中图分类】 【相关文献】

1.具有简单线性恶化加工时间的Flow shop调度问题 [J], 赵传立; 张庆灵; 唐恒永

2.一类线性加工时间单机调度问题 [J], 赵传立; 张庆灵; 唐恒永

3.一类基于开工时间恶化效应和基于位置学习效应的单机调度问题的求解 [J], 徐海燕

4.具有线性恶化加工时间的调度问题 [J], 赵传立; 张庆灵; 唐恒永 5.工件加工时间线性恶化的单机成组加工问题 [J], 金霁

以上内容为文献基本信息，获取文献全文请下载