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

Research on the Single Machine Scheduling with Simple Linear Deterioration

作　　者：黄安宁 HUANG An-ning(Chongqing Qineng Electricity&Aluminum Co.,Ltd.,Chongqing 401420,China)

机构地区：[1]重庆旗能电铝有限公司,重庆401420

出　　处：《新型工业化》2017年第10期57-62,共6页The Journal of New Industrialization

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

摘　　要：单机调度是生产管理领域的重要研究方向,对其的研究可追溯到60多年前。近年来,在调度问题中考虑恶化工件的影响,吸引了越来越多研究者的关注。这类工件的处理时间可能随着其加工前的等待时间的增长而增长,大大加大了调度问题的复杂度。本文对可恢复模式下的一类简单线性恶化加工时间的单机调度问题进行了研究。该问题以最小化工件完成时间为目标,本文首先证明了该问题的最优解能通过0-1整数规划获得;然后证明了该问题在一般情况下其复杂度为NP-hard;最后为其给出了一个完全多项式时间近似方案。Single machine scheduling is an important research direction in production management area.Its research can be dated back to more than 60 years ago.In recent years,considering the effects of deteriorating jobs has attracted more and more researchers’attention.These jobs’processing time increases with the increase of the waiting time before the processing starts,which largely increase the complexity of machine scheduling problem.This paper investigates one type of single machine scheduling problem with simple linear deterioration to minimize the makespan.The machine is subject to a machine availability constraint.Job interrupted by machine unavailability can resume their processing.This paper shows firstly that the investigated problem can be solved by 0-1 integer programming,then proves that the problem is NP-hard and there exists a fully polynomial time approximation scheme for it.

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

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