机器有使用限制的混合恶化排序问题的复杂性  

THE COMPLEXITY OF SCHEDULING WITH MIXED DETERIORATION AND AVAILABILITY CONSTRAINTS

作　　者：张玉忠[1] 苗翠霞[2] 

机构地区：[1]曲阜师范大学管理学院,日照276826 [2]曲阜师范大学数学科学学院,曲阜273165

出　　处：《系统科学与数学》2015年第6期685-694,共10页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金(11201259,61340045);教育部博士点专项基金(20123705110003,20123705120001);山东省国内访问学者资助课题

摘　　要：考虑了机器具有使用限制的混合恶化排序问题.其中部分工件的加工时间是固定常数,另一部分的是其开工时间的简单线性函数,工件是不可中断的.文章目标是极小化最大完工时间.对于单机问题,证明了问题是一般意义下的NP-难的,给出了一个4/3-近似算法,并证明了算法界是紧的.对于平行机问题,证明了问题是强NP-难的.In this paper,we consider the scheduling problem in which the machines have availability constraints and the processing times of some jobs are constant,while others are simple linear increasing functions of their starting times.The objective is to minimize the makespan for non-resumable jobs.For the single-machine issue,we show that this problem is NP-hard in the ordinary sense,provide a 4/3-approximation algorithm and show that the bound is tight.For the parallel-machine issue,we show that this problem is NP-hard in the strong sense.

关 键 词：混合恶化 使用限制 NP-难 近似算法 

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