就绪时间受限的负荷单机环境下返工工件重调度方法  

Rescheduling with Release Time to Minimize Sum of Waiting Time Considering Waiting Constraint of Original Loads

作　　者：郭艳东[1,2] 王庆[1] 黄敏[1] 

机构地区：[1]东北大学信息科学与工程学院流程工业综合自动化国家重点实验室,沈阳110819 [2]渤海大学数理学院,锦州121000

出　　处：《自动化学报》2013年第12期2100-2110,共11页Acta Automatica Sinica

基　　金：国家杰出青年科学基金资助项目(71325002;61225012);国家自然科学基金资助项目(71071028;70931001;71021061;71171040);高等学校博士学科点专项科研基金优先发展领域资助课题(20120042130003);高等学校博士学科点专项科研基金资助课题(20110042110024);中央高校基本科研业务费专项资金(N110204003;N120104001)资助~~

摘　　要：研究了返工工件的单机重调度问题.在初始调度中初始工件带有不同的就绪时间,优化目标为最小化初始工件等待时间和;重调度时在满足每个初始工件最大等待时间约束情况下安排返工工件的生产,优化目标为最小化所有工件等待时间和.文中首先建立了RRSM(Rescheduling for reworks on single machine)问题模型,并证明其为NP难问题.然后,提出并证明了三个RRSM问题性质,进而根据诸性质设计了求解RRSM问题的动态插入启发式(Dynamic insert heuristic,DIH)算法.证明了应用DIH算法能在多项式时间内求得两种特殊RRSM问题的最优解.最后,分析了DIH算法解的特点,给出了最优解的判定方法,并通过算例说明了DIH算法的有效性.In this paper, we consider the rescheduling problem to minimize the sum of waiting times of rework jobs and the original loads with release time on a single machine, and the waiting time of each original load is constrained by a value. The problem of rescheduling for reworks on a single machine （RRSM） is formulated and proved to be NP-hard. A dynamic insert heuristic （DIH） Mgorithm of polynomial-time is designed and proved with three properties. With respect to two special cases of the identical processing time of rework jobs or the machine without idle times in the original schedule, the DIH algorithm can obtain an optimal solution. A discrimination condition is proved for the optimal solution and effectiveness of the DIH algorithm is explained by cases with regard to general RRSM problems.

关 键 词：重调度 单机 返工 启发式算法 等待时间 

分 类 号：TH186[机械工程—机械制造及自动化]