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

摘要：

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

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

所属期刊栏目：7

分类号：O22;TP3

资助基金：四川省科技计划项目2017G1357;成都市社科规划项目2017Z32

在线出版日期：2018-01-12（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：57-62