带有可控性维护的单机调度问题研究  

Single machine scheduling with controllable maintenance

作　　者：张丽华[1] 涂菶生[2] 

机构地区：[1]沈阳师范大学数学与系统工程学院,辽宁沈阳110034 [2]南开大学信息技术科学学院,天津300071

出　　处：《吉林大学学报（信息科学版）》2004年第4期303-305,共3页Journal of Jilin University（Information Science Edition）

基　　金：国家自然科学基金资助项目(69674013);国家攀登计划资助项目(970211017)

摘　　要：为在附加费用不大的条件下,通过最小化工件完成时间之和来减小work-in-process中的库存,尽可能使工件按期交付,在将工件调度与机器维护统一进行考虑的模型基础上,提出了带有预防性维护的单机调度问题,并对其进行了建模。将机器的维护周期适当放宽,以便在保证总的附加费用不超出预先给定的一个常数的前提下,实现工件的完成时间和的最小化。对工件加工允许中断的情况给出时间复杂度为O(n*ln(n));对工件加工不允许中断的情况给出一个启发式算法,其时间复杂度为O(n2)。由该启发式算法很容易得到问题的可行解,从而为问题的进一步研究打下了基础。To decrease the work-in-process inventory by minimizing the total job time within appropriate additional fees, thus to meet the due dates of jobs, a single machine scheduling problem with preventive maintenance is given.A model of this problem is built,which bases on integrating the machine maintenance and job processing. The maximum allowed continuously working time of the machine is prolonged, so that the minimization of the total job time can be realized under the premise of the total additional fees not beyond a predetermined constant, and two types of processing cases are considered: preemptive and nonpreemptive. For the preemptive case, an optimal algorithm in O(n*ln(n)) time is proposed, and for the nonpreemptive case, a heuristics algorithm in O(n^2) time is given. A feasible scheduling can easily be obtained by the heuristics algorithm, so the work of this paper will become a well basement for the further study.

关 键 词：调度 维护 启发式算法 

分 类 号：F224[经济管理—国民经济]